Зачем использовать пустышки?

Question

В реализации Cpython, когда мы удаляем ключ в dict, Cpython устанавливает соответствующую запись для фиктивной записи, почему фиктивная запись?Могу ли я просто позволить значению ertry быть нулевым?

Я не очень хорошо разбираюсь в C, поэтому я издеваюсь над ним на python, ниже приведен код реализации моего python:

class DictEntry:
def __init__(self):
    self.key = None
    self.value = None
    self.hash = None
def __repr__(self):
    return ' %s %s %s' % (self.key, self.hash, self.value)


class Hashtable:
def __init__(self):
    self.size = 8
    self.used = 0
    self.mask = self.size - 1
    self.pow2 = 3
    self.entyies = [DictEntry() for _ in range(self.size)]

def insert(self, key, item):
    hash_value = _hash(key)
    _key = hash_value & (self.size - 1)
    if not self.is_slot_empty(_key):
        _key = self.next_slot(_key, hash_value)
    entry = self.entyies[_key]
    entry.key = _key
    entry.hash = hash_value
    entry.value = item
    self.used += 1
    # if need resize
    if self.size * 2 / 3 < self.used:
        old_entyies = self.entyies
        self.entyies = [DictEntry() for _ in range(self.size * 2)]
        self.size = 2 * self.size
        self.mask = self.size - 1
        self.pow2 += 1
        for entry in old_entyies:
            if entry.value:
                self.insert(entry.key, entry.value)

def delete(self, obj):
    # delete won't resize
    # find the slot
    hash_value = _hash(obj)
    key = hash_value & (self.size - 1)
    perturb = hash_value
    PERTURB_SHIFT = 5
    while self.entyies[key].hash != hash_value:
        print(self.entyies[key].value, obj)
        key = key * 5 + 1 + perturb
        perturb <<= PERTURB_SHIFT
        key = key % 2 ** self.pow2

    # set to empty
    entry = self.entyies[key]
    entry.key = None
    entry.hash = None
    entry.value = None
    self.used -= 1

def getitem(self, obj):
    hash_value = _hash(obj)
    key = hash_value & (self.size - 1)
    perturb = hash_value
    PERTURB_SHIFT = 5
    while self.entyies[key].hash != hash_value:
        key = key * 5 + 1 + perturb
        perturb <<= PERTURB_SHIFT
        key = key % 2 ** self.pow2
    return self.entyies[key].value

def next_slot(self, key, hash_value):
    # open_address
    perturb = hash_value
    PERTURB_SHIFT = 5
    while not self.is_slot_empty(key):
        key = key * 5 + 1 + perturb
        perturb <<= PERTURB_SHIFT
        key = key % 2 ** self.pow2
    return key

def is_slot_empty(self, key):
    if self.entyies[key].value:
        return False
    return True

def __repr__(self):
    return '%s' % [(entry.hash, entry.value) for entry in self.entyies]enter code here

И я могу вставлять, удалять значения по своему желанию.когда я хочу пустую запись, я проверю, является ли значение записи None. Так что я не очищаю дизайн «фиктивной записи» для?

Может кто-нибудь показать мне функцию «фиктивной» и указать наошибка в моем коде?

Answer 1

(Примечание: я не очень хорошо знаком с внутренними компонентами реализации dict Python, я говорю здесь о хеш-таблицах в целом.)

Основная идея хеш-таблицы заключается в том, что вы можете получитьхеш-значение из ключа, и используйте его, чтобы перейти непосредственно к записи таблицы, которая содержит соответствующее значение.Однако любая реализация должна иметь дело с возможностью того, что два разных ключа имеют одинаковое хеш-значение (или иным образом отображаются на один и тот же индекс записи с помощью операции по модулю, выполняемой с хеш-значением).Python обрабатывает это с помощью стратегии, называемой «закрытое хеширование»: если соответствующая запись уже взята другим ключом, вычисленная последовательность других возможных записей проверяется, пока не будет найдена пустая.(Таблице не разрешается заполняться почти на 100%, так что эта проверка никогда не занимает необоснованно много времени и гарантированно находит пустую запись.) Реализация get() следует той же последовательности, пока либонайден правый ключ или найдена пустая запись.

Теперь представьте, что два ключа A и B, имеющие коллизию хешей, вставляются в dict в указанном порядке, а затем A удалено.Если вы реализовали это, установив пустую запись A, подумайте о том, что произойдет при последующем вызове get(B): он сразу найдет эту пустую запись и сообщит, что B вообще отсутствует!Эта проблема может быть исправлена ​​с помощью специального значения флага, отличного от фактического ключа или пустой записи, которое используется для указания удаленной записи.Когда get() видит один из них, он знает, что ему нужно продолжать поиск в других возможных местах входа.Когда set() видит его, он может перезаписать его вставленным ключом (хотя он все равно должен будет сканировать, пока не найдет фактическую пустую запись, чтобы убедиться, что ключ еще не присутствует).