How hash tables are used to quickly locate a data record?
What kind of hash table? There are several.
The basic idea is to make some sort of hash or scramble of the key, and turn that into an array index. This means, best-case, it only has to do one step to find the data -- create the hash, check the array, done. The drawback is, of course, it's possible for two values to try and use the same index. There are various ways of coping with this.
Thanks corona for the reply.
I just wanted to know a basic conceptual logic of how hast table helps in making the search faster.
Imagine it like a gargantuan bucket sort... Not really a sort, it's cheating -- every possible element gets its own slot in memory. If you know what you want, you know where it is by definition. There's no hunting at all, you just reach in and grab it.
Now shrink it down to a manageable size. It can't hold every possible element any more. But, if you're storing only a few, you can still find the ones you want the very first try nearly every time. There might be a few overlaps, but that can be handled fairly gracefully.
Compare this to an unsorted list, where on average you'll have to search through n/2 elements to find the one you want. or a binary tree, where you need to check log(n) times to find it.
1 Like
Thanks coronna for clearing the doubts.