A hash table is a collection structure that contains a map and a set and if you just have a key and you don’t have an accompanying value, you can use a HashSet structure (C++ STL set) and if you have a key, you have an accompanying value, You can use the HashMap structure (C++ STL map) with or without accompanying data is the only difference between a HashMap and a Hashset. The underlying actual structure is the same thing, both using red-black tree hashing solutions

1. Open addressing: if an element exists at the specified location, the next element stored at the specified location is moved, if it is still occupied. And so on until you find a suitable location. There are many ways to address this, but this is just one simple example. ThreadLocal in Java is an open addressing method

2. Linked list method: In Java HashMap, each element is not only an Entry object, but also the head node of a linked list. Each Entry object points to its next Entry node through a pointer. When a new Entry is mapped to a conflicting array location, it is simply inserted into the corresponding linked list

Hash table expansion

1. When multiple elements are inserted and a single column is expressed to a certain degree of saturation, the probability of conflicts in key mapping positions will gradually increase; Such a large number of elements will be crowded into the subscript positions of the same array, resulting in a long linked list, which has a significant impact on the performance of subsequent insert and query operations

For a HashMap in JDK, there are two factors that affect capacity expansion: 1. Capacity: the current length; 2. Loadfactor: indicates the loadfactor. The default value is 0.75f

HashMap. Size >= Capacity * LoadFactor

What exactly does the capacity expansion operation do?

1. Expand and create a new array with empty entries twice as long

2. Rehash: Iterates over the previous Entry array and rehash all the elements into the new array. This is because the rules of the Hash change after the length increases, redistributing the previous entries as evenly as possible

  • When multiple entries are hashed into the subscript of the same array, HashMap converts the list of entries into a red-black tree structure to improve insertion and lookup efficiency