Python哈希：函數來確定最長的探測序列

Question

我想寫一個函數，返回一個特定大小的哈希表最差的索引/索引列表。它應該像：

def worst_indices(size_of_hashtable, list_of_keys): 
    .... 

哪裏list_of_keys是訂立基於哈希函數的哈希表鍵列表：H（鍵）=鍵％大小。

但是我的函數並不需要輸出哈希表，只需要輸出需要最多移位/探針的索引，如果你想輸入另一個關鍵字。

例如，下面的代碼

values = [25, 32, 88, 10, 35, 11] 
worst = worst_indices(11, values) 
print(worst)   

應該產生輸出：

[10]   

作爲另一個示例，代碼：

values = [4, 9, 12, 3, 7, 26, 16, 20, 11] 
worst = worst_indices(13, values) 
print(worst)   

應該產生輸出：

[3, 7, 11] 

因此，如果您要在哈希表中添加另一個值，那麼在這些「最差索引」中添加一個值會導致最右移，因爲它會探測下一個未知的點。 任何幫助或提示如何做到這一點將是非常棒的。 謝謝。

Answer 1

假設我明白你的意圖，這應該可以解決你的問題。需要注意的是在其中加入KEY_LIST值的順序應該不會影響結果（儘管這當然會影響實際的哈希表中的桶分配）：

def worst_indices(hash_size, key_list): 
    # require at least one empty hash bucket 
    assert(len(key_list) < hash_size) 

    buckets = [False] * hash_size 
    for key in key_list: 
     index = key % hash_size 
     index2 = index 
     while buckets[index2]: 
      index2 += 1 
      if index2 == hash_size: 
       index2 = 0 
     buckets[index2] = True 

    # find some empty bucket 
    ix0 = buckets.index(False) 

    # count the chain lengths 
    lengths = [None] * hash_size 
    ix = ix0 
    length = 0 
    while True: 
     length = length + 1 if buckets[ix] else 0 
     lengths[ix] = length 
     ix = hash_size - 1 if ix == 0 else ix - 1 
     if ix == ix0: 
      break 

    max_length = max(lengths) 

    return [ix for ix in xrange(hash_size) 
       if lengths[ix] == max_length] 

下面是輸出：

>>> worst_indices(11, [25, 32, 88, 10, 35, 11]) 
[10] 
>>> worst_indices(13, [4, 9, 12, 3, 7, 26, 16, 20, 11]) 
[3, 7, 11] 
>>> 

希望這會有所幫助。