Что такое реализация хеш-таблицы / словаря для Python, которая не хранит ключи?

Question

Я храню миллионы, возможно, миллиарды 4-байтовых значений в хеш-таблице, и я не хочу хранить ни один из ключей. Я ожидаю, что будут храниться только хэши ключей и значений. Это должно быть быстро и все хранится в оперативной памяти. Записи будут по-прежнему просматриваться с ключом, в отличие от set ().

Что такое реализация для Python? Есть имя для этого?

Да, столкновения разрешены и могут быть проигнорированы.

(Я могу сделать исключение для коллизий, для них можно сохранить ключ. В качестве альтернативы коллизии могут просто перезаписать ранее сохраненное значение.)

Answer 1

Фильтры Блумье - ассоциативный массив с эффективным использованием пространства

Из Википедии:

Chazelle et al. (2004) разработал обобщение фильтров Блума, которые может связать значение с каждым элемент, который был вставлен, реализация ассоциативного массива. Как и фильтры Блума, эти структуры достичь небольшого пространства над головой принимая небольшую вероятность ложного позитивы. В случае с "Блумье" фильтры ", определяется ложное срабатывание возвращая результат, когда ключ не на карте. Карта никогда не будет вернуть неправильное значение для ключа, который находится на карте.

Answer 2

Как насчет использования обычного словаря и вместо того, чтобы делать:

d[x]=y

использование:

d[hash(x)]=y

Чтобы посмотреть вверх:

d[hash(foo)]

Конечно, если есть коллизия хэшей, вы можете получить неверное значение.

Answer 3

Это старый добрый пробел против компромисса времени выполнения: вы можете иметь постоянное время с линейным использованием пространства для ключей в таблице hastable. Или вы можете неявно хранить ключ и использовать log n time, используя двоичное дерево. (Бинарный) хеш значения дает вам путь в дереве, где он будет храниться.

Answer 4

Хотя словари python очень эффективны, я думаю, что если вы собираетесь хранить миллиарды элементов, вы можете создать свое собственное расширение C с оптимизированными структурами данных за то, как вы на самом деле используете его (последовательный доступ «совершенно случайно» и т. д.).

Чтобы создать расширение C, вы можете использовать SWIG или что-то вроде Pyrex (который я никогда не использовал).

Answer 5

Создайте свое собственное b-дерево в оперативной памяти.

Использование памяти:

(4 байта) сравнительного хеш-значения

(4 байта) индекс следующего листа, если хеш <= сравнение ИЛИ, если отрицательный индекс значения </p>

(4 байта) индекс следующего листа, если хэш> сравнение ИЛИ, если отрицательный индекс значения

12 байт на узел b-дерева для b-дерева. Дополнительные издержки для значений (см. Ниже).

Как вы структурируете это в Python - не существует ли «нативных массивов» 32-битных целых чисел, практически без дополнительных затрат памяти…? как они называются ... в любом случае те.

Отдельный упорядоченный массив подмассивов, каждый из которых содержит одно или несколько значений. Приведенные выше «индексы значений» являются индексами в этом большом массиве, что позволяет извлекать все значения, соответствующие хешу.

Это предполагает 32-битный хэш. Вам понадобится больше байтов на узел b-дерева, если у вас есть больше 2 ^ 31-1 записей или больший хэш.

НО Спаннер в работах возможно: Обратите внимание, что вы не сможете, если вы не сохраняете значения ключей, проверить, что искомое значение хеша соответствует только вашему ключу, если только через какой-то алгоритмический или организационный механизм вы гарантировали что никакие два ключа не будут иметь одинаковый хеш. Довольно серьезная проблема здесь. Вы рассматривали это? :)

Answer 6

Не могли бы вы рассказать нам больше о ключах? Мне интересно, есть ли какая-то закономерность в ключах, которые мы могли бы использовать.

Если ключи представляют собой строки в небольшом алфавите (например, строки из цифр, например номера телефонов), вы можете использовать структуру данных Trie:

http://en.wikipedia.org/wiki/Trie

Answer 7

Если вы на самом деле храните миллионы уникальных значений, почему бы не использовать словарь?
Магазин: d[hash(key)/32] |= 2**(hash(key)%32)
Проверить: (d[hash(key)/32] | 2**(hash(key)%32))

Если у вас есть миллиарды записей, используйте вместо этого пустой массив размером (2 ** 32) / 32. (Потому что, в конце концов, у вас есть только 4 миллиарда возможных значений для хранения в любом случае).

Answer 8

Это не то, что вы просили купить, почему бы не рассмотреть Токийский кабинет или BerkleyDB для этой работы? Это не будет в памяти, но вы торгуете производительностью для большей емкости хранения. Вы все еще можете хранить свой список в памяти и использовать базу данных только для проверки существования.

Answer 9

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

Однако, если ваши ключи похожи на строки, существует очень экономичная структура данных - ориентированный ациклический граф слов (DAWG). Я не знаю ни одной реализации Python.

Answer 10

Почему не словарь + hashlib?

>>> import hashlib
>>> hashtable = {}
>>> def myHash(obj):
    return hashlib.sha224(obj).hexdigest()

>>> hashtable[myHash("foo")] = 'bar'
>>> hashtable
{'0808f64e60d58979fcb676c96ec938270dea42445aeefcd3a4e6f8db': 'bar'}