Предупреждение: этот ответ может быть немного запутанным, потому что нужно учитывать две разные вещи:
Python имеет встроенный тип хеш-таблицы, dict. Его внутренняя реализация написана на C (по крайней мере, для CPython) и использует трюки, которые вы не можете написать непосредственно на Python. Подробнее о (нескольких) реализациях, использовавшихся за эти годы, см. Как реализованы встроенные словари Python .
Python как язык в основном не имеет массивов. 1 Некоторые ответы на связанный вопрос выражены в виде массивов, а встроенный в Python список type может быть , используемый как массив, так что он будет служить моделью. Вот что я буду здесь делать.
Итак, начнем с создания пустого псевдомассива: []. Мы свяжем это с каким-нибудь «похожим на массив» именем:
a = []
, а затем приступайте к своим вопросам.
1 Модуль array предоставляет массивы в стиле C. Подробности смотрите в документации по массиву .
Мой вывод заключается в том, что если у меня есть пара ключ-значение, то хеш по существу преобразует индекс в ключ, а затем этот ключ сохраняется в массиве.
И наоборот: хеш-код преобразует ключ, который является «слишком большим», в меньший , т. Е. Хэш-значение, которое компьютер может обрабатывать более легко и напрямую. Это преобразует ключ в индекс. Вы правильно поняли это в следующей части вопроса:
Таким образом, если индекс для 'key1' равен 0, тогда a[0] содержит фактическое значение 'value1'.
Обычно да. Однако, если хеш-таблица предназначена для обоих попаданий и пропусков, и какой-то другой ключ (скажем, '1frotz') может также преобразовать в индекс 0, мы должны хранить два элемента в a[0], или сохраняйте параллельный массив фактических ключей или что-то в этом духе, чтобы убедиться, что a[0] содержит 'key1', а не какую-либо другую пару ключ-значение. То есть в Python мы могли бы сделать это:
i = hash(key) % tablesize # assuming a fixed table size
assert i < len(a) # this is going to fail since len(a) == 0!
kv_pair = a[i]
assert kv_pair[0] == key
... use kv_pair[1], which holds the value ...
Конечно, нам также нужно иметь возможность поместить элементы в хэш-таблицу. Как правило, когда мы делаем это, мы расширяем таблицу, если пара ключ-значение не подходит, поэтому вместо вышеуказанных assert s мы делаем:
def find_value(key):
if len(a) > 0:
i = hash(key) % len(a)
kv_pair = a[i]
if kv_pair is not None and kv_pair[0] == key:
return kv_pair[1]
return None
def insert_kv_pair(key, value):
if len(a) > 0:
i = hash(key) % len(a)
kv_pair = a[i]
if kv_pair is None: # not in the table yet
a[i] = [key, value] # so put it in
return
if kv_pair[0] == key: # already in the table
kv_pair[1] = value # so replace the value
return
... the complicated parts go here ...
Когда мы нажимаем на «сложные части», либо сам массив слишком мал, либо слот, который мы хотим использовать, уже используется для некоторого другого ключа.
Вот где хеш-таблицы становятся модными. Некоторые используют вторичную хеш-функцию, делая что-то под названием повторное хеширование и проверяя другие слоты таблицы (в этом случае мы хотим начать с ненулевого размера таблицы). Некоторые расширяют стол на месте. Опять же, чтобы увидеть, что на самом деле делает Python, посмотрите этот другой вопрос и ответы на него.
Тем не менее, я не уверен, так ли это на самом деле, или, как и переменные в python, значение в массиве на самом деле не представляет 'value1', а вместо этого некоторый указатель, который указывает на место в памяти, где 'value1 ' хранится. ...
Поскольку Python допускает динамические типы в словарях, слот значения для любого хешированного ключа определенно хранит указатель на фактическое значение, а не его копию. Значения разных типов имеют разные базовые размеры. Вы можете просмотреть размер типа, используя sys.getsizeof (но см. Как мне определить размер объекта в Python? также):
>>> import sys
>>> sys.getsizeof(int)
400
>>> sys.getsizeof(1)
28
>>> sys.getsizeof('str')
52
>>> sys.getsizeof('string')
55
Поскольку размеры меняются по всей карте, Python просто сохраняет указатель в слоте «значения» словаря для данного ключа.
... означает ли это, что значения, хранящиеся в хэш-таблице, на самом деле разбросаны по всей памяти, а не хранятся последовательно?
Да. Во внутренней реализации Python последовательно хранятся только хэш-значение и пара указателей ключ / значение.