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

Question

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Добавление

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

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

Есть несколько дополнительных вещей, на которые следует указать:

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

Вы можете найти несколько примеров хеш-функций здесь .

Answer 3

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

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

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

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

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);

Answer 4

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

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

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

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

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

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

• повторяйте, пока не напишите все данные.

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

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

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

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

Answer 5

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

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

Answer 6

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