1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hash Tables Linear Probing and Double Hashing

  1. Feb 27, 2012 #1
    1. The problem statement, all variables and given/known data
    Consider a hash table T with 11 entries and the hash function h(x) = x mod 11. Show the result of hashing the keys 10,16,11,43,33,13,14,12,3, and 22, assuming collisions are handled by
    (a) open addressing with linear probing
    (b) double hashing using a secondary hash function h′(x) = 5−(x mod 5)


    2. Relevant equations



    3. The attempt at a solution

    I believe I have the correct answer, I just want to double-check since I'm having difficulties.

    Using a table I have:
    Key ---- h(x) ---- h'(x) ---- probes LP ---- probes DH
    10 ---- 10 ---- ---- 10 ---- 10
    16 ---- 05 ---- ---- 5 ---- 5
    11 ---- 00 ---- ---- 0 ---- 0
    43 ---- 10 ---- 2 ---- 10, 0, 1 ---- 10,2
    33 ---- 00 ---- 2 ---- 0, 1, 2 ---- 0, 2, 3
    13 ---- 02 ---- 2 ---- 2,3 ---- 2,2,3,4
    14 ---- 03 ---- 1 ---- 3,4 ---- 3,1
    12 ---- 01 ---- 3 ---- 1,2,3,4,5,6 ---- 1,3,4,5,6
    03 ---- 03 ---- 2 ---- 3,4,5,6,7 ---- 3,2,3,4,5,6,7
    22 ---- 00 ---- 3 ---- 0,1,2,3,4,5,6,7,8 ---- 0,3,4,5,6,7,8
     
  2. jcsd
  3. Feb 28, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    The linear probe interval isn't specified. Are you supposed to assume it's 1? The contents of the hash table is not specified, so how are you supposed to know when collisions have occurred, or are you just supposed to list a set of indexes for the collision sequence for each key, or are you supposed to assume that the hash table is initially empty and the list of keys you're given are going to be stored in the hash table in the listed key order?
     
  4. Feb 28, 2012 #3
    We're supposed to assume the interval is 1. I'm not sure I understand what you mean but you know a collision occurs when both keys have the same h(x) like keys 10 and 43 both have h(x) as 10
     
  5. Feb 28, 2012 #4

    rcgldr

    User Avatar
    Homework Helper

    I understand that, but are you just supposed to list the order in probes would take place if the hash table was completely filled (no empty slots), or are you supposed to list the probes that would take place if the hash table was initially empty and you stored that list of 10 keys into the hash table, leaving one empty slot when done?
     
    Last edited: Feb 28, 2012
  6. Feb 28, 2012 #5
    We're supposed to list the probes by the place is should initially be at. if that spot is filled then we advance to the next spot until we find an empty spot
     
  7. Feb 28, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    Looks like it's the case where you're adding those 10 keys in order to an initially empty table, in which case your answer appears to be correct. Note, you can put [ code ] and [ /code ] (without the spaces) around your text to preserve it's format.
     
  8. Feb 28, 2012 #7
    thank you!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Hash Tables Linear Probing and Double Hashing
  1. Truth Table (Replies: 2)

  2. Steam Tables (Replies: 1)

  3. Set theory hash-tables (Replies: 0)

Loading...