From blog.csdn.net/lljhi10/art…
Hash tables are arrays based storage. It consists mainly of hash functions and arrays.
When storing data, a function is used to calculate the address of the data, and then store the data in an array at the specified location. This function is the hash function, and this array is the hash table.
The advantage of hash table is that, compared with simple array and linked list, it can find the position of the element in the first time, which is the time complexity of 0(1). This makes it much faster to query, delete, and insert than arrays and linked lists. Because their time is order n.
A hash conflict is when the hash function’s address is occupied by another element, that is, the location is occupied. Good hash functions try to avoid hash collisions. One of the ways to resolve hash conflicts is open addressing (conflict, continue to find the next block of storage address is not occupied), hash function method, chain address method.
Hash functions use chained addresses, which are arrays plus lists, and hashmaps use chained addresses. Chained addresses are basically just arrays when there are no hash collisions. But when a conflict occurs, it adds a linked list to the memory location of the current array found by the hash function.