Double Hashing with python

Question

I'm currently doing hashing in my class. I need to create a double hashing function which takes a list and uses double hashing and returns a new list.

I understand how a list uses double hashing but I have trouble writing down the code for it.

hashkey = key % len(list)
steps = q - (key % q)
new_hashkey = steps + hashkey
#q = double_hash_value

This is the double hashing function that I have learned in class. I just have trouble implementing it in the code.

This is my attempt so far:

def double_hashing(keys, hashtable_size, double_hash_value):
    hashtable_list = [None] * hashtable_size
    for i in range(len(keys)):
        hashkey = keys[i] % hashtable_size
        if hashtable_list[hashkey] is None:
            hashtable_list[hashkey] = keys[i]
        else:
            new_hashkey = hashkey
            while hashtable_list[new_hashkey] is not None:
                steps = double_hash_value - (keys[i] % double_hash_value)
                new_hashkey = hashkey + steps
            hashtable_list[new_hashkey] = keys[i]
            return hashtable_list

values = [26, 54, 94, 17, 31, 77, 44, 51]
double = double_hashing(values, 13, 5)
print('Double =', double)

I'm fairly sure this is close to being right but I'm just making a stupid mistake or something. I understand how double hashing works but this code above does not work.

The output for this should be:

[26, None, 54, 94, 17, 31, 44, 51, None, None, None, None, 77]

but my output is:

[26, None, 54, 94, 17, 31, 44, None, None, None, None, None, 77]

The value 51 in index position is not being added.

Any help is appreciated. Thank you.

Answer 1

Your function has two problems as far as I can tell:

Problem 1 is that in your while loop, you were using hashkey to update the value of new_hashkey which meant that if your function failed to find an appropriate index for a given value in the first iteration of the while loop, it would never find it since the value of new_hashkey would never change. Also by simply adding the steps to new_hashkey you run the risk of having a new_hashkey that is greater than your hashtable_size which will eventually throw an IndexError. You can fix that by taking that value modulo the hashtable_size. Secondly, your function was returning too early. In your example, it was returning after it encountered 44 (i.e. the first time it entered the else block), which was why you weren't adding 51 to your output list. Your return statement should really be after the for loop is finished so that you are sure to add all the values in the keys list to your output list.

See the updated code below (changed lines are commented):

def double_hashing(keys, hashtable_size, double_hash_value):
    hashtable_list = [None] * hashtable_size
    for i in range(len(keys)):
        hashkey = keys[i] % hashtable_size
        if hashtable_list[hashkey] is None:
            hashtable_list[hashkey] = keys[i]
        else:
            new_hashkey = hashkey
            while hashtable_list[new_hashkey] is not None:
                steps = double_hash_value - (keys[i] % double_hash_value)
                new_hashkey = (new_hashkey + steps) % hashtable_size  ## problem 1 is here
            hashtable_list[new_hashkey] = keys[i]
    return hashtable_list  ## problem 2 is here


values = [26, 54, 94, 17, 31, 77, 44, 51]
print( double_hashing(values, 13, 5) )

[26, None, 54, 94, 17, 31, 44, 51, None, None, None, None, 77]

Answer 2

In general, here is how we resolve collision with double-hashing: use the second hash function if there is a collision as follows, to find the next location in hash table T, as shown below:

Now, let's implement double hashing with the following code:

def h1(k, m):
    return (2*k+3)%m

def h2(k, m):
    return (3*k+1)%m

def resolve_collision_with_double_hashing(hastable, keys, m, h1, h2):
    for k in keys:
        index = h1(k, m)
        if not hastable[index]: # no collision
            hastable[index] = k
        else:         # use double-hashing
            v = h2(k, m)
            inserted = False
            i = 1 # no need to check for i = 0, since collision already occurred
            while i < m: 
                index1 =  (index +  v * i) % m
                i += 1
                print('inserting {}, number of probings: {}'.format(k, i))
                if not hastable[index1]:
                    hastable[index1], inserted = k, True
                    break
            if not inserted:
                print('could not insert {}'.format(k))

print('hash table: ' + ' '.join(map(lambda x: str(x) if x else '', hastable)))

m = 11
hashtable = [None]*m
keys = [3,2,9,6,11,13,7,1,12,22]
resolve_collision_with_double_hashing(hashtable, keys, m, h1, h2)

# trying to insert 13, number of probings: 2
# trying to insert 13, number of probings: 3
# trying to insert 13, number of probings: 4
# inserted 13
# trying to insert 7, number of probings: 2
# trying to insert 7, number of probings: 3
# trying to insert 7, number of probings: 4
# trying to insert 7, number of probings: 5
# trying to insert 7, number of probings: 6
# trying to insert 7, number of probings: 7
# trying to insert 7, number of probings: 8
# trying to insert 7, number of probings: 9
# trying to insert 7, number of probings: 10
# trying to insert 7, number of probings: 11
# could not insert 7
# trying to insert 12, number of probings: 2
# trying to insert 12, number of probings: 3
# inserted 12
# trying to insert 22, number of probings: 2
# trying to insert 22, number of probings: 3
# trying to insert 22, number of probings: 4
# trying to insert 22, number of probings: 5
# trying to insert 22, number of probings: 6
# inserted 22
# hash table: _ _ 12 11 6 1 13 2 22 3 9