Hashing advantages/disadvantages

[nkbxwb]

We just learned in class about hashing and searching. Our teacher spent very little time on this though. It seems like he just threw it in on the last lesson before the final.

From what he lectured about in class, it seems to be super efficient for searching. I was wondering if this is true in practice, or is there some huge disadvantage of hashing to search?

Thanks!

[itsme86]

For very small data sets it can actually be slower, but yes, generally speaking it is extremely efficient. Downsides can be increased memory requirements for storing the hash table and the trouble of finding a good hashing algorithm.

[nkbxwb]

Are the coding techniques used to implement advanced/complicated? I'm just wondering why he only spent like 10 minutes on it.

[itsme86]

As far as the table goes, it's usually implemented as an array of linked lists where the hash value of the object is the index into the array. Coming up with a good algorithm for calculating the hash is a more advanced topic and usually involves some math concepts.

[iMalc]

A common good yet basic hash is FNV-1a. It is used in all sorts of stuff.

Downsides that nobody else mentioned yet is that the data is not stored in sorted order so if you want to output the data in order then you have to do extra work. Also, there is always a tiny chance that performance can degrade to being linear, but it all depends on how good the hash is and luck.

The most basic hashing system is something you are probably already familiar with. E.g. in a library books may be sorted by the author. All those whose last names start with A will be grouped together and all those with B grouped and so on. The hash there simply takes the first letter and throws the rest away. It's faster than if you had to first do a binary search on the first letter because you can instead walk straight up to the right section.