Какую структуру данных следует использовать для хранения хеш-значений?

Question

У меня есть хеш-таблица, которую я хочу сохранить на диск. Список выглядит следующим образом:

<16-byte key     > <1-byte result> 
a7b4903def8764941bac7485d97e4f76 04 
b859de04f2f2ff76496879bda875aecf 03 
etc... 

Есть 1-5 миллионов записей. В настоящее время я просто храню их в одном файле, 17-байтов на каждую запись, количество записей. Этот файл имеет десятки мегабайт. Моя цель - сохранить их таким образом, чтобы сначала оптимизировать пространство на диске, а затем искать время поиска. Время вставки не имеет значения.

Каков наилучший способ для этого? Я хотел бы, чтобы файл был как можно меньше. Несколько файлов тоже будут в порядке. Патрисия три? Radix trie?

Какие бы хорошие предложения я не получил, я буду внедрять и тестировать. Я опубликую результаты здесь для всех, чтобы видеть.

Answer 1

Вы можете просто отсортировать записи по ключу и выполнить двоичный поиск.

Ключи фиксированного размера и ввода данных означают, что вы можете очень быстро переходить из строки в строку, а хранение только ключа и данных означает, что вы не теряете пространство на метаданных.

Я не думаю, что вы сделаете лучше на диске, а время поиска - O (log (n)). Время вставки очень сумасшедшее, но вы сказали, что это не имеет значения.

Если вы действительно готовы терпеть длительное время доступа, выполните сортировку таблицы, а затем поместите ее в блоки определенного размера и сжимайте их. Храните смещение * и клавиши запуска/завершения каждого блока в разделе файла в начале. Используя эту схему, вы можете найти блок, содержащий необходимый ключ в линейном времени, а затем выполнить двоичный поиск в распакованном блоке. Выберите размер блока в зависимости от того, какую часть файла вы хотите загрузить в память сразу.

Используя схему сжатия с полки (например, GZIP), вы можете настроить степень сжатия по мере необходимости; более крупные файлы, вероятно, будут иметь более быструю синхронизацию.

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

_{* Используйте заголовок для поиска смещения блока для распаковки и использования.}

Answer 2

Будет ли простой подход работать и хранить их в sqlite database? Я не думаю, что он будет меньше, но вы должны получить очень хорошую производительность поиска, и его очень легко реализовать.

Answer 3

Прежде всего - несколько файлов не в порядке, если вы хотите оптимизировать пространство на диске из-за размера кластера - при создании файла размером ~ 100 байт дисковое пространство уменьшается на размер кластера - например, на 2 КБ.

Во-вторых - в вашем случае я бы сохранил всю таблицу в одном двоичном файле, упорядоченную просто ASC по байтам в ключах. Это даст вам файл с длиной, которая точно равна entryNumber * 17, что минимально, если вы не хотите использовать архивирование, а во-вторых, вы можете использовать очень быстрый поиск с временем ~ log2 (entriesNumber), когда вы ищете файл деления ключа на две части и сравнивая ключ на своей границе с необходимым ключом. Если «пограничный ключ» больше, вы берете первую часть файла, если больше - затем вторую часть. И снова разделите часть на две части и т. Д. Так что вам потребуется прочесть операции log2 (entriesNumber) для поиска одного ключа.

Answer 4

5 миллионов записей - около 81 МБ - приемлемо для работы с массивом в памяти.

Как вы описали проблему - это более уникальные ключи, чем значения хэша. Попробуйте использовать таблицу хэша для доступа к значениям (см. this link).

Если есть мое недоразумение, и это реальный хеш - попробуйте построить второй уровень хэша выше этого.

Хэш-таблица также может быть успешно организована на диске (например, в виде отдельного файла).

Добавление

решение с хорошей производительностью поиска и минимальными накладными расходами является:

1. Определение хэш-функцию, которая производит целые значения от ключей.
2. Сортировка записей в файле в соответствии со значениями, полученной с помощью этих функции
3. смещений хранилища файлов, где каждое значение хэша начинается
4. Чтобы найти значение:
   4.1. вычислить его хэш с функцией
   4.2. поиск смещения в файле
   4.3. читать записи из файла, начиная с этой позиции, до тех пор, пока не будет найден или смещен ключ следующего ключа, не достигшего или конечного файла.

Есть некоторые дополнительные вещи, которые должны быть отметил:

• Функция хеширования должна быть быстрой, чтобы быть эффективным
• Функция хеширования должна производить линейные распределенные значения или около того
• Таблица хэша смещения значения могут быть помещены в отдельный файл
• Таблица смещений значения хэш-функции может быть произведена динамически с последовательным чтением всего отсортированного файла в начале приложения и сохранена в памяти
• на шаге 4.3. записи должны быть прочитаны блоками, а не один за другим, чтобы быть эффективными. Идеально считывает все значения с вычисленным хешем в память сразу.

Вы можете найти некоторые примеры хеш-функций here.

Answer 5

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

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

• Размер файла таков, что весь shebang можно хранить в памяти на любом современном ПК или сервере и много других устройств;

• ведущие 4 байта ваших ключей делят набор возможных ключей на подмножества 16^4 (= 65536); если ваши ключи распределены равномерно, и у вас есть 5x10^6 записей, это около 76 записей на подмножество; поэтому создайте файл с пространством для, скажем, 100 записей на подмножество; затем:

• при смещении 0 начните записывать все записи с ведущими 4 байтами 0x0000; pad в общей сложности 100 записей (1700 байт, я думаю) с 0s;

• со смещением 1700 начала писать все записи с ведущими 4 байта 0x0001, панель,

• повторить до тех пор, пока вы написали все данные.

Теперь ваш поиск становится вычислением, чтобы определить смещение в файле, за которым следует сканирование до 100 записей, чтобы найти тот, который вы хотите. Если это недостаточно быстро, используйте 16^5 подмножеств, допустив около 6 записей на подмножество (6x16^5 = 6291456). Я предполагаю, что это будет быстрее, чем бинарный поиск, но это всего лишь предположение.

Вставка - это немного проблема, вам нужно знать свои данные, чтобы решить, нужны ли новые записи (a) для повторной сортировки подмножества или (b), можно просто добавить в конце список записей в этом индексе (что означает сканирование всего подмножества при каждом поиске).

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

То, что я описываю, не очень хорошо, это таблица хеш-таблицы.

Answer 6

Ваш ключ - 128 бит, но если у вас есть макс 10^7 записей, для его индексации требуется всего 24 бита.

1. Вы могли бы сделать хэш-таблицу, или

2. Использование Bentley стиля раскатал бинарный поиск (не более 24 сравнений), как и в

Вот развернутый цикл (с 32 -бит ints).

int key[4]; 
int a[1<<24][4]; 

#define COMPARE(key, i) (key[0]>=a[i][0] && key[1]>=a[i][1] && key[2]>=a[i][2] && key[3]>=a[i][3]) 

i = 0; 
if (COMPARE(key, (i+(1<<23))) >= 0) i += (1<<23); 
if (COMPARE(key, (i+(1<<22))) >= 0) i += (1<<22); 
if (COMPARE(key, (i+(1<<21))) >= 0) i += (1<<21); 
... 
if (COMPARE(key, (i+(1<<3))) >= 0) i += (1<<3); 
if (COMPARE(key, (i+(1<<2))) >= 0) i += (1<<2); 
if (COMPARE(key, (i+(1<<1))) >= 0) i += (1<<3);