Explain Hash Table in simple terms

Posted on 2009-02-11
Last Modified: 2012-05-06
Hi Experts,

Can you give me a step by step explanation of how a hash table works and how to implement it with a single linked list.

Please be as specific and explain with simple terms.



p.s. In addition, if you want to put a link to supplement your explanation that would be ok. But please explain first.
Question by:datopdogg7
    LVL 18

    Accepted Solution

    Before explain hash table, lets explain hash.
    Hash is a number or a small set of numbers, calculated from a large set of numbers.
    Supose you have a phonebook, composed by names and phone numbers and for each name you have a hash number. For example, if we add the code of the characters of each name, probably we have different results for all the names.
    A=1,  B=2, ..., Z=26
    JOHN -->  10 + 15 + 8 + 14 = 47
    ANNE -->  1 + 14 + 14 + 5 = 34
    There are special algorithms to calculate hash numbers such that they are unique values or with few chances of equal hash numbers for different names.
    Now suppose we have a phonebook where we have hash numbers as keys, something like:
    01       0
    02       0
    33       0
    34       2337=3431
    35       0
    47       2344-7839

    In a common phonebook we have the names in alphabetic order and respectives numbers associated to them. If we want a phone number, the searching algorithm will scan the list in a character by character basis, until finding the name, then returning the phone number associated to such name.
    In our hash oriented phonebook the algorithm gets the name, say JOHN, calculates its hash number, 34 and returns the phone number at register 34. No searching.
    Easy to understand that the second algorithm is faster than the first one. There is a price to that: a lot of cells will be empty, and the database size is larger that the one of the traditional phonebook. Hash tables waste more memory and disk space, because the table is sparse. Optimized hashing can reduce the database size, but it will be larger than the traditional one.
    Probably you will ask if different names can have the same hash number. Yes, it happens, but there are techniques to solve the collisions.
    Now suppose we have much more data than a single phone number, say, for each name we have a street addres, security number, credit card number, e-mail, father's name, etc. We can't waste disk space with so large empty records, so we use a trick: we have a hash table as below:
    01       0
    02       0
    33       0
    34       1
    35       0
    47       2
    such that if we want JONH's data, the algorithm returns "2", not the data. Then we use such number, 2, as a key number in another table, as below:
    1      JONH     2344-7839      4532 Rodeo Street    VISA 12345678
    2      MARY     2337=3431      1234 Durango Rd     MC  98765432
    3      etc.
    and find the data we are looking for.
    That way, the hash table, which wastes space with empty registers, is small because stores just small key numbers. The real data is in a dense table, so no wasting room in the large data records.
    By using hash tables, we find data very quickly and with the described trick, by wasting very few disk room.

    Author Comment

    Thanks Jose,
    Explanation was very concise.
    I am going to pose another question about the same topic, can you please look for it?



    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Looking for New Ways to Advertise?

    Engage with tech pros in our community with native advertising, as a Vendor Expert, and more.

    Suggested Solutions

    Title # Comments Views Activity
    has22 challenge 11 55
    EvenOdd challenge 10 67
    squareUp  challenge 22 80
    mapAB Challlenge 35 46
    Windows Script Host (WSH) has been part of Windows since Windows NT4. Windows Script Host provides architecture for building dynamic scripts that consist of a core object model, scripting hosts, and scripting engines. The key components of Window…
    Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
    This video teaches viewers about errors in exception handling.
    The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…

    760 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    7 Experts available now in Live!

    Get 1:1 Help Now