This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

Hash table

Also known as a hash table, a data structure that directly accesses a memory location based on a Key; Access the records by computing a function on the key and mapping the data required for the query to a location in the table, which speeds up lookupingCopy the code

advantages

1. No matter how much data is in a hash table, search, insert, delete (and sometimes delete) takes a near-constant time of 0(1). In practice, it only takes a few machine instructions.

Hash tables are very fast. Computer programs that need to find thousands of records per second usually use hash tables (such as a spell checker). Hash tables are significantly faster than trees, which usually require order (N) time. Hash tables are not only fast, but also relatively easy to implement programmatically.

3. If you don’t need to traverse the data in order, and you can predict the size of the data in advance. So hash tables are unmatched in terms of speed and ease of use.

disadvantages

It is based on arrays, which are difficult to extend once created, and performance degrades badly when some hash tables are almost full, so programmers must be aware of how much data will be stored in the table (or be prepared to periodically move data to larger hash tables, a time-consuming process).

The internal structure

Take Java’s HashMap as an example

The bottom layer is array + linked list (Java8 + red-black tree) to store data.

Hash conflict

Hash collisions occur when the Key is used to hash the index of the underlying array. The need to resolve such conflicts led to the introduction of linked list storage. The values in the array are all the head nodes of a linked list. When hash conflicts occur, they are added to the corresponding list at the corresponding position. When the length of the list exceeds 8, they are converted into a red-black tree.