HashMap in Java

Work of HashMap

HashMap consists of buckets. Technically speaking, "buckets" are array elements that hold references to lists of items. When a new key-value pair is added, it calculates the key hash-code, on the basis of which the bucket number (array cell number), into which the new element will fall, is calculated. If the bucket is empty, then a link to the newly added element is saved in it, but if there is already an element there, then there is a sequential transition through the links between the elements in the chain, in search of the last element, from which the link to the newly added element is placed. If an element with the same key was found in the list, then it is replaced.

According to Knuth and Cormen, there are two main hash table implementations: open addressing and chaining based.

HashMap is implemented using chaining method i.e. each cell of the array (bucket) has its own linked list, and when a collision occurs, a new element is added to this list.

For the chaining method, the fill factor can be greater than 1, and with an increase in the number of elements, performance decreases linearly. It is convenient to use such tables if the number of stored elements is not known in advance, or there can be a lot of them, which leads to large values of the fill factor.

Among the methods of open addressing implementation are distinguished:

  • linear probing;
  • quadratic probing;
  • double hashing.

Disadvantages of structures with open addressing method:

  • The number of elements in the hash table cannot exceed the size of the array. As the number of elements increases and the fill factor increases, the performance of the structure drops sharply, so rehashing must be performed.
  • It is difficult to organize the removal of an item.
  • The first two open addressing methods lead to the problem of primary and secondary constellation.

Advantages of an open address hash table:

  • no costs for creating and storing list objects;
  • ease of organization of serialization/deserialization of an object.

How does a HashMap work when trying to store two elements in it by keys with the same hashCode(), but for which equals() == false?

The hashCode() value is used to calculate the index of the array cell to which this element will be added. Before adding, a check is made for the presence of elements in this cell. If elements with this hashCode() are already present, but their equals() methods are not equal, then the element will be added to the end of the list.

What is the initial number of buckets in the HashMap?

The default constructor is 16, using constructors with parameters, you can set an arbitrary initial number of buckets.

What is the estimate of the time complexity of operations on elements from a HashMap? Does the HashMap guarantee the specified item fetch complexity?

In general, the operations of adding, searching, and removing elements take constant time.

This complexity is not guaranteed, since if the hash function distributes the items evenly across the buckets, the time complexity will be no worse than the Logarithmic time O(log(N)), and in the case where the hash function constantly returns the same value, the HashMap will turn into a linked list with complexity O(n).

Is it possible for a HashMap to degenerate into a list even with keys having different hashCode()?

This is possible if the method that determines the buckets number will return the same values.

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