HashMap details in Java

When can element in HashMap be lost?

Let's say that not a primitive is used as a key, but an object with several fields. After adding an element to the HashMap, one field of the object that acts as a key is changed, which is involved in calculating the hash code. As result, when trying to find a given element by the original key, the correct bucket will be accessed, but equals will no longer find the specified key in the list of elements. Nevertheless, even if equals is implemented in such a way that changing this field of the object does not affect the result, then after increasing the size of the buckets and recalculating the hash codes of the elements, the specified element, with the changed field value, with a high degree of probability will end up in a completely different bucket and then it will be completely lost.

Why can't byte[] be used as key in HashMap?

The hash code of an array does not depend on the elements stored in it, but is assigned when the array is created (the method for calculating the hash code of an array is not overridden and is calculated using the standard Object.hashCode() based on the address of the array). Equals are not overridden for arrays, and pointers are compared. This leads to the fact that access to the element saved with the key-array will not work when using another array of the same size and with the same elements, access can be done only in one case - when using the same reference to the array that was used to save element.

Role of equals() and hashCode() in a HashMap

hashCode allows you to define a bucket to search for an item, and equals is used to compare the keys of the items in the bucket list and the key to find.

Maximum number of hashCode() values

The number of values follows from the signature int hashCode() and is equal to the range of type int - 2^32.

Worst get(key) method running time for a key that is in a HashMap and isn't in a HashMap

O(N). The worst case is a search for a key in a HashMap, degenerated into a list due to the coincidence of keys by hashCode(), and to find out whether an element is stored with a specific key, it may be necessary to iterate over the entire list.

How many transitions occur at the time HashMap.get(key) is called on the key that is in the table?

  • the key is null: 1 - the only getForNullKey() method is executed.
  • any key other than null: 4 - calculation of the key hash code; determination of the bucket number; search for a value; return value.

How many new objects are created when you add a new item to the HashMap?

One new static nested class Entry<K,V>.

How and when does the number of buckets increase in the HashMap?

In addition to capacity, HashMap also has a loadFactor field, on the basis of which the maximum number of occupied buckets capacity * loadFactor is calculated. By default loadFactor = 0.75. Upon reaching the limit, the number of buckets is doubled and a new "location" is calculated for all stored items, taking into account the new number of buckets.

Meaning of the parameters in the constructor of HashMap(int initialCapacity, float loadFactor)

initialCapacity - the initial size of the HashMap, the number of buckets in the hash table at the time of its creation.

loadFactor - HashMap fill factor, when exceeded, the number of buckets increases and automatic rehashing occurs. It is equal to the ratio of the number of already stored elements in the table to its size.

Will HashMap work if all the keys being added have the same hashCode()?

Yes, it will, but in this case the HashMap degenerates into a linked list and loses its advantages.

How to iterate over all Map keys?

Use the keySet() method, which returns a set of Set<K> keys.

How to iterate over all Map values?

Use the values() method, which returns a Collection<V> of values.

How to iterate over all key-value pairs in a Map?

Use the entrySet() method, which returns a set of Set<Map.Entry<K,V>> key-value pairs.

Read also:


Comments

Post a Comment

Popular posts from this blog

Methods for reading XML in Java

Image
DOM (Document Object Model) - object - reads XML, recreating it in memory in the form of an object structure, while the XML document is represented as a set of tags - nodes. Each node can have an unlimited number of child nodes. Each child can also contain several levels of descendants or none at all. Thus, the result is a kind of tree. Pluses: Easy to program. If there are many objects in XML with cross-references to each other, it is enough to go through the document twice: first time create objects without references and fill in the name-object dictionary, the second time - restore links. If an error occurs in XML, a half-created XML structure remains in memory, which will be automatically destroyed. Suitable for both reading and writing. Minuses: Low speed. Wastes a lot of memory. SAX (Simple API for XML) - event-driven - reads an XML document, responding to emerging events (opening or closing tag, string, attribute) by calling the event handlers provided by the appl...
Read more

XML, well-formed XML and valid XML

Image
XML, the eXtensible Markup Language, is a language with a simple formal syntax, well suited for creating and manipulating documents with programs, and at the same time easy to read and create documents by humans. XML is extensible, it does not fix the markup used in documents, and the developer is free to create markup in accordance with the needs of a particular area, being limited only by the syntax rules of the language. DTD A DTD, Document Type Definition, is a predefined set of rules that defines the relationships between elements and attributes. For example, the DTD for HTML says that the DIV tag must be inside the BODY tag and can appear multiple times, TITLE - in HEAD and only once, and SCRIPT - both there and there as many times as you want. A DTD is usually described directly in the document as a formulation line starting with <!DOCTYPE ... > or in a separate file. Difference between well-formed XML and valid XML Depending on the level of compliance, the document...
Read more

ArrayList and LinkedList in Java, memory usage and speed

Image
How much extra memory is needed when calling ArrayList.add()? If there is enough space in the array to accommodate a new element, then no additional memory is required. Otherwise, a new array is created, 1.5 times larger than the existing one (this is true for JDK above 1.7, in earlier versions the size of the increase is different). How much extra memory is allocated when you call LinkedList.add()? One new instance of the nested Node class is created. How much memory to store one byte primitive in LinkedList? Each LinkedList element stores a link to the previous element, the next element, and a data link. private static class Node<E> { E item; Node<E> next; Node<E> prev; //... } For 32-bit systems, each link is 32 bits (4 bytes). The object (header) of the nested Node class itself takes 8 bytes. 4 + 4 + 4 + 8 = 20 bytes, and since the size of each object in Java is a multiple of 8, so we get 24 bytes. A byte primitive occupies 1 by...
Read more