The underlying structure of HashMap is array + single linked list. A HashMap stores key-value pairs and stores them in map.Entry. Map.Entry stores the hashcode of the key, the value value, and a reference to the next Entry object, next. HashMap implements the Map interface. The most commonly used method is PUT (K key, V value) Get (Object key). The principle of put is to check whether the key value is null. If the current key is not zero, hashCode is applied to the key and bits are changed to hashCode. The reason for doing this is to avoid hash collisions. Finally, the value hash is remainder to the length of the array, but considering the high efficiency of bitwise operation, here the hash value is ampersand with the length of the array -1 (for example, if the length of the array is 8, then the length of the array -1 is 7, binary nine tails 0111), so the low value is reserved. After getting the index of the value to be inserted in the array, if there is a value at that position in the array and the Entry at that position has the same hash value as the inserted value, and the key value is the same (” == “or equals), then the value at that position is replaced directly with the value to be inserted. If the index position is null or the entries at the index position do not satisfy the same hash value and the same key value (” == “or equals equal) then the inserted value is directly inserted into the array at the index position. If there is an Entry object at the index position, The next node is then moved backwards as the Entry is inserted.
The get method also performs a bit operation based on the hashcode of the key and retrieves the index, then iterates through the array and list values at that position. If there is an Entry’s Hashcode that is the same as and equal to the key (” == “or equals), the value is returned. Otherwise null is returned. HashMap allows key-value pairs to be null.
HashTable and HashMap implement the Map interface, which is based on the structure of array + single linked list and stores key-value pairs. The more important methods are put and GET methods in the Map interface. The put method of HashTable is the same as that of HashMap except that if the value of HashMap is null, it will throw an exception. If the key is not null, the rest of the method is the same as that of HashMap. If hashCode is the same and key is the same (” == “or equals is the same) then replace value directly. Otherwise, a new Entry object is added to index and the original value is the next of the inserted object. In contrast to HashMap, HashTable does not allow null key-value pairs because any null pair throws an exception. HashTable is thread-safe, and a public method has the synchronize modifier.
Based on the above understanding, we can know that the data stored in the HashMap is unordered, that is, the values printed by the iterator of the HashMap are not in the same order as the values put in. LinkedHashMap allows the same order of input and output. LinkedHashMap inherits HashMap and implements the Map interface, so it also has put and get methods. LinkedHashMap’s data structure is also an array + linked list data structure, but LinkeHashMap maintains a dual linked list running on all items. This list of links defines an iteration order, which can be sequential insert or access order. The default is sequential insert sort. If you specify an access order, the call to get moves the accessed elements to the end of the doubly connected list. LinkedHashMap allows key-values to be stored as null, and key-value pairs are also enclosed by Map.Entry, but two variables are added: Entry<K,V>before,after table the previous and next node of the Entry in the double-linked list.
LinkedHashMap has the same put method as HashMap. The more key HashCode evaluates the index of the key-value pair in the array. If the index position has a value and the hashCode is the same as the inserted value and the key is the same (” == “or equals is the same) then replace the value directly. If the index value does not meet the above conditions, insert a new value at the corresponding position, and add the value to the end of the double-linked list, and adjust the after and before points of the Entry. If the value already exists in the double-linked list then the double-linked list removes the previous value and adds the value to the end of the double-linked list. If you want to enter the values in the LinkedHashMap in accessOrder, accessOrder is true when the object is constructed, and after the get method, you do the above to put the Entry object at the end of the double-linked list. If this value is set to false, the logic of inserting the tail of the double-linked list is not performed.
The feature of a HashSet is that it is not allowed to store the same value. The reason is that the underlying of a HashSet is a HashMap, and the value stored in a HashSet is the Vaule value of a HashMap, while the key is an Object Object. Therefore, the same key is stored in the same display.