How does a hash table work
In: Technology
A “hash” is an algorithm, piece of code, etc that converts something (text, object) into a number. For example my name, “DeHackEd” might hash to a number like 25872. Note that this number does have a range limit and there’s no guarantee that every number is unique. Some people will have the same number.
So from that number we can set up a system where we can say that each object gets stored into a slot based on its number. For example if we store users by name and there are 10,000 slots available then I would be designated slot 5872 based on my hash number above (and the number range available since my hash number is higher than the number of slots available)
When searching for information for the user “DeHackEd”, the fact that there are 10,000 possible slots and who know how many users are being saved doesn’t matter. If I’m in there at all then I’m definitely in slot 5872. So a search is extremely fast. If the number of stored items is kept in the 10,000 range as well then realistically the size of the list doesn’t matter to how long a search takes. At worst all users who go into the same slot need to be checked but if the number 10,000 was selected wisely then that should be a very short list.
The biggest downside is that inexact matches are hard. If you want all users whose names begin with the letter “D” then the hash is useless and you must go through the entire table entry by entry looking for matches. Also the size (in our example, 10000) should be chosen wisely. If you are storing 1 million entries then on average each cell would hold 100 user accounts which is going to start eating into the performance advantages of a hashtable. Furthermore you need a strategy of how to deal with users sharing the same slot – using something else like a sorted list or a small RB tree might be a good idea.
Latest Answers