Hashing advantages/disadvantages

This is a discussion on Hashing advantages/disadvantages within the C Programming forums, part of the General Programming Boards category; We just learned in class about hashing and searching. Our teacher spent very little time on this though. It seems ...

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    13

    Hashing advantages/disadvantages

    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!

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,175
    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.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    13
    Are the coding techniques used to implement advanced/complicated? I'm just wondering why he only spent like 10 minutes on it.

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,175
    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.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Little endian and Bit endian advantages and disadvantages
    By nkrao123@gmail. in forum C Programming
    Replies: 4
    Last Post: 09-11-2011, 05:40 AM
  2. Replies: 3
    Last Post: 03-08-2008, 06:02 AM
  3. advantages and disadvantages in c
    By cnu_sree in forum C Programming
    Replies: 4
    Last Post: 11-06-2007, 09:29 AM
  4. Advantages/Disadvantages of Using C C++ for distributed App Programmin!
    By ahms83 in forum Networking/Device Communication
    Replies: 1
    Last Post: 05-11-2004, 01:14 AM
  5. functions (advantages/disadvantages)
    By aramsahai in forum C++ Programming
    Replies: 3
    Last Post: 04-30-2004, 10:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21