Python Hash: функция определения самой длинной последовательности зондов

Question

Я пытаюсь написать функцию, которая возвращает список худших индексов/индексов хэш-таблицы определенного размера. Она должна выглядеть следующим образом:

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

Где list_of_keys список ключей, которые были введены в хэш-таблицу на основе хэш-функции: Н (ключ) = размер ключа%.

Моя функция, однако, не должна выводить хеш-таблицу, ей просто нужно вывести индексы, которые потребуют большинство сдвигов/зондов, если вы хотите ввести в них другой ключ.

Например, следующий код

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] 
>>> 

Надеюсь, это поможет.