Hash table is a key-valued data storage structure. We can find the corresponding value by inputting the value to be searched, that is, key.
The idea of hashing is simple: if all keys are integers, you can use a simple unordered array: the key is the index, and the value is the corresponding value, so that you can quickly access the value of any key. This is the case for simple keys, and we extend it to handle more complex types of keys.
There are two steps to using hash lookup:
-
A hash function is used to convert the searched key into an index of the array. Ideally, different keys would be converted to different index values, but there are cases where we need to deal with multiple keys hashed to the same index value. So the second step in hash lookup is to handle conflicts. There are many ways to deal with hash collision, and the most common one is the zipper method. That is, a linked list is used to hold multiple objects with the same hash value during collision.
-
A hash table is a classic example of a tradeoff between time and space. If there are no memory limitations, you can use the key as the index of the array directly. Then all search time complexity is O(1); If there is no time limit, we can use an unordered array and do a sequential lookup, which requires very little memory. Hash tables use a moderate amount of time and space to find a balance between these two extremes. You just need to adjust the hash function algorithm to make a choice in time and space.
