Geek Answers Handbook

Internal methods of operation of the HashMap put () and get () methods (only basic logic)

When we put the key example, we say that the “key” and the instance of the value say “value” in the HashMap class using the put() method, which makes the HashMap class internally. How does it return the value back when we say hashMap.get(key) ?

Change Here I do not want to receive detailed information, trying to understand the big picture and the role of the equals() and hashcode() methods in put() and get() operations.

+4
source share
3 answers

If you are talking about a higher image, this is similar to below. Here I refer to the element as key Map

When placing items.

  • Calculate hashcode key
  • If a basket with this hashcode present, use the equals method when searching for the key in the keys in this basket to determine if the item should be added or replaced.
  • If not, then create a new basket (replay) and add this item to it.

Receive:

  • Get hashcode key
  • Go to basket
  • An iteration using equals on the key will return this item from this basket to you.
+14
source

This is what is done in IBM jdk 1.6 (I believe that it is almost the same for all vendors)

EDIT

Regarding equals and hashcode , you might be interested to see this post.

END OF EDITING

  /** * Maps the specified key to the specified value. * * @param key * the key * @param value * the value * @return the value of any previous mapping with the specified key or null * if there was no mapping */ @Override public V put(K key, V value) { return putImpl(key, value); } V putImpl(K key, V value) { Entry<K,V> entry; if(key == null) { entry = findNullKeyEntry(); if (entry == null) { modCount++; if (++elementCount > threshold) { rehash(); } entry = createHashedEntry(null, 0, 0); } } else { int hash = key.hashCode(); int index = hash & (elementData.length - 1); entry = findNonNullKeyEntry(key, index, hash); if (entry == null) { modCount++; if (++elementCount > threshold) { rehash(); index = hash & (elementData.length - 1); } entry = createHashedEntry(key, index, hash); } if ((cache != null) && (hash >> CACHE_BIT_SIZE == 0) && (key instanceof Integer)) { cache[hash] = value; } } V result = entry.value; entry.value = value; return result; }
+1
source

From java 8 onwords, there has been a performance improvement for HashMap objects, where there are many conflicts in the keys, using balanced trees rather than linked lists to store records in the map. The main idea is that after the number of elements in the hash bucket exceeds a certain threshold, this bucket will switch from using a linked list of records to a balanced tree. In the case of high hash collisions, this will improve worst case performance from O(n) to O(log n).

Basically, when the bucket gets too large (currently: TREEIFY_THRESHOLD = 8 ), the HashMap dynamically replaces it with a special implementation of the tree map. This method, and not the pessimistic O(n) , is much better than O(log n) .

The bunkers (elements or nodes) of TreeNodes can pass and be used like any other, but additionally support quick search during overpopulation. However, since the vast majority of boxes are not overpopulated during normal use, checking for tree boxes may be delayed by tabular methods.

Letters

Tree (that is, bins whose elements are all TreeNodes ) are ordered mainly with hashCode, but in the case of links, if two elements have the same " class C implements Comparable<C> ", enter them compareTo() > used to streamline.

Because TreeNodes approximately two times larger than regular nodes, we only use them when there are enough nodes in the boxes. And when they get too small (due to deletion or resizing), they are converted back to regular mailboxes (currently: UNTREEIFY_THRESHOLD = 6 ). When used with a well-distributed user hashCodes tree baskets are rarely used.

Link to java doc

Collection Improvements

+1
source

More articles:


All Articles