0

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.

4

2 回答 2

2

据我所知，您的函数有两个问题：

问题 1 是在你的while循环中，你hashkey用来更新它的值，new_hashkey这意味着如果你的函数在 while 循环的第一次迭代中未能找到给定值的适当索引，它永远不会找到它，因为值new_hashkey永远不会改变。同样，通过简单地添加steps，new_hashkey您会冒 anew_hashkey大于您的风险，hashtable_size最终会抛出IndexError. 您可以通过将该值取模来解决此问题hashtable_size。其次，您的函数返回得太早了。在您的示例中，它遇到后返回44（即第一次进入else块），这就是您不添加的原因51到您的输出列表。您的 return 语句实际上应该在 for 循环完成之后，以便您确保将keys列表中的所有值添加到输出列表中。

请参阅下面的更新代码（更改的行已注释）： 

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]
于 2017-02-16T06:03:21.027 回答
0

一般来说，我们使用双重哈希解决冲突的方法如下：如果有冲突，使用第二个哈希函数，在哈希表 T 中找到下一个位置，如下所示：

在此处输入图像描述

现在，让我们使用以下代码实现双重哈希：

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
于 2021-11-24T07:41:16.887 回答