Shulou(Shulou.com)06/02 Report--

This article shows you how to use the source code to analyze Java HashMap examples, the content is concise and easy to understand, can definitely brighten your eyes, through the detailed introduction of this article, I hope you can get something.

Introduction

HashMap is often used in key-value pair storage, so how does it implement key-value storage?

One Entry

Entry is an internal interface in the Map interface, which is the key to the implementation of key-value pair storage. In HashMap, there is an implementation class for Entry, called Entry. The Entry class is simple and contains key,value, an externally introduced hash, and a reference to the next Entry object, similar to the note node in the linked list in the data structure.

The properties and constructors of the Entry class:

Final K key; V value; Entry next; int hash; / * * Creates new entry. * / Entry (int h, K k, V v, Entry n) {value = v; next = n; key = k; hash = h;}

Initialization of two HashMap

/ / HashMap construction method public HashMap (int initialCapacity, float loadFactor) {if (initialCapacity)

MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor = MAXIMUM_CAPACITY? MAXIMUM_CAPACITY: (number > 1)? Integer.highestOneBit ((number-1) = toSize int capacity = roundUpToPowerOf2 (toSize); threshold = (int) Math.min (capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry [capacity]; initHashSeedAsNeeded (capacity);}

In put and other methods, when it is found that the array is not initialized, the InflateTable method is called for initialization, and the input parameter is the initially set InitialCapacity. In real time, he will call the roundUpToPowerOf2 method to return a power of 2 that is larger than the initial capacity (one of the reasons is that it is convenient to get the location of the array where the Entry is located).

Four put method

Public V put (K key, V value) {if (table = = EMPTY_TABLE) {inflateTable (threshold);} if (key = = null) return putForNullKey (value); int hash = hash (key); int I = indexFor (hash, table.length); for (Entry e = table [I]; e! = null; e = e.next) {Object k; if (e.hash = hash & (k = e.key) = key | | key.equals (k)) {V oldValue = e.value E.value = value; e.recordAccess (this); return oldValue;}} modCount++; addEntry (hash, key, value, I); return null;} private V putForNullKey (V value) {for (Entry e = table [0]; e! = null; e = e.next) {if (e.key = = null) {V oldValue = e.value; e.value = value; e.recordAccess (this); return oldValue;}} modCount++ AddEntry (0, null, value, 0); return null;} void addEntry (int hash, K key, V value, int bucketIndex) {if ((size > = threshold) & & (null! = table [bucketIndex])) {resize (2 * table.length); hash = (null! = key)? Hash (key): 0; bucketIndex = indexFor (hash, table.length);} createEntry (hash, key, value, bucketIndex);} void createEntry (int hash, K key, V value, int bucketIndex) {Entry e = table [bucketIndex]; table [bucketIndex] = new Entry (hash, key, value, e); size++;}

In the put method

1. First of all, it determines whether the array is empty, and if it is empty, the array is initialized.

two。 Next, determine whether key is null, and if it is null, use the second method to put the key-value pair.

3. Next, hash the key to get a value, and then process the value (the IndexFor method) to get the position in the array.

4. The next step is to traverse the linked list at the location of the array. If the hash of the key is the same as the hash passed in the key and (the key memory address is equal or the equals method is equal), it means that the value in the linked list is updated and the old value is returned.

5. If none of the above methods work, the third method is called to create a new Entry object.

In the putForNullKey method, we see that it is specifically set for the null value, and the hash of the null value is always 0, so the Entry object whose key is NULL must be in the zero position of the array. Similarly, if it is found, it is updated, and if not found, it is added.

Calling the addEntry method means adding an Entry to the array linked list, so it is determined at the beginning whether the number of Entry that already exists exceeds the actual capacity. If it exceeds it, the resize square method is called to double the size of the array, and note that the Entry already stored will be rearranged after the expansion, because the IndexFor method is related to the length of the array when it was originally stored. The fourth method is then called.

The createEntry method is simple: put the chain header that was originally stored in the array into the new Entry, and then put the new Entry into the array. From this we can see that HashMap does not guarantee the order problem.

The principle of get method is consistent with that of contains method and put method, that is, the position of the chain header in the array is obtained by hash of key, and then the existence of value is judged by equals method.

Five others

/ / hash method final int hash (Object k) {int h = hashSeed; if (0! = h & & k instanceof String) {return sun.misc.Hashing.stringHash42 ((String) k);} h ^ = k.hashCode (); / / This function ensures that hashCodes that differ only by / / constant multiples at each bit position have a bounded / / number of collisions (approximately 8 at default load factor). H ^ = (h > 20) ^ (h > 12); return h ^ (h > 7) ^ (h > 4);}

The final return value in the hash method is related to the hashCode method of key.

Summary

The final size of the initialized array will be a power greater than or equal to the minimum of 2 of the initial capacity you pass in.

The reason why key is null or value is null can be stored in HashMap is that separate operations are performed on null values.

What each Entry has in common in the linked list in the table array is that the hash (key.hashCode) part of key is the same.

Note the override of key's hashCode and equals methods when you want two key to map an object, because the condition for determining key equality is (hashCode equality + (memory equality or equals equality).

The earliest stored key-value pair is at the end of the linked list.

When no linked list exists in the array, the HashMap performance is O (1). And the worst is O (threshould).

The above content is how to use source code to analyze Java HashMap examples. Have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.