This article mainly talks about the reason why "the storage efficiency of hash tables is generally not exceeding 50%.
Hash Table is often used to frequently search for key/value mode. (Find pattern, such as match search)
The biggest advantage of hash tables is that they look up quickly, but collisions may occur during storage.
Most hash tables use open addressing to solve collision. At this time, the time complexity calculation formula for search is:
1/( 1 - n/m )
Where n and m represent the stored records and the length of the hash table, namely the loading factor (load factor )
Therefore, if the hash table is half full, that is, n/m >= 1/2, the number of searches per time may be >= 2
Therefore, in order to ensure the advantages of Hash Table in the key/value search mode, its storage efficiency will generally not exceed 50%.
The above is the brief discussion of the reasons why hash table storage efficiency generally does not exceed 50%. I hope everyone supports me~