Понять реализацию таблицы ha sh

Question

Я изучаю ха sh таблицы, и меня немного смущает эта реализация таблицы ха sh, написанная на Python из учебника. Я понимаю все это, кроме одной точки, где внутри метода addEntry () есть для l oop, который делает hashBucket[i] = (dictKey, dictVal), если hashBucket[i][0] == dictKey Я немного запутался в том, что он делает.

class intDict(object):
    def __init__(self, numBuckets):
        self.buckets = []
        self.numBuckets = numBuckets
        for i in range(numBuckets):
            self.buckets.append([])

    def addEntry(self, dictKey, dictVal):
        hashBucket = self.buckets[dictKey%self.numBuckets]
        for i in range(len(hashBucket)):
            if hashBucket[i][0] == dictKey:
                hashBucket[i] = (dictKey, dictVal)
                return
        hashBucket.append((dictKey, dictVal))

    def getValue(self, dictKey):
        hashBucket = self.buckets[dictKey%self.numBuckets]
        for e in hashBucket:
            if e[0] == dictKey:
                return e[1]
        return None

    def __str__(self):
        result = '{'
        for b in self.buckets:
            for e in b:
                result = result + str(e[0]) + ':' + str(e[1]) + ','
        return result[:-1] + '}' 

Answer 1

Сделайте шаг назад и подумайте о столе ha sh. У вас просто есть массив блоков, и способ, которым вы можете получить индекс для определения того, на какой блок вы будете смотреть по заданному ключу, основан на некоторой функции ha sh, f(). Представьте, что у вас бесконечное количество ключей, но f() может производить только, скажем, ~ 2 миллиарда уникальных хэшей. Принцип «Голубиная дыра» гласит, что если у вас есть n корзин и n + 1 объектов для размещения в корзинах, то как минимум в одном из корзин будет больше один объект. Вы можете представить себе наихудший сценарий, когда f() - плохая функция ha sh, и мы помещаем все в одно ведро.

Действительно, нет никакого способа гарантировать, что таблица ha sh выиграла не допускается столкновение ключей для бесконечно большого набора ключей и ограниченного набора хэшей. Итак, почему это?

for i in range(len(hashBucket)):
    if hashBucket[i][0] == dictKey:
        hashBucket[i] = (dictKey, dictVal)
            return

Это объясняет возможность того, что два или более ключей могут существовать в одном сегменте. Мы не только go получаем индекс хэшированного значения, но и go должны пройти через все значения в этом сегменте, чтобы определить, является ли это значение, которое мы ищем. Если это так, нам нужно также сохранить это новое значение с ключом, в некотором роде. Просто так получилось, что ваш ключ и значение dict в этом случае сохраняются в виде (key, value) кортежа.