Как сохранить хеш-таблицу в файле?

Question

Как я могу сохранить хеш-таблицу с отдельной цепочкой в ​​файле на диске?

Генерация данных, хранящихся в хеш-таблице во время выполнения, обходится дорого, было бы быстрее просто загрузить HT с диска ... если бы я только мог понять, как это сделать.

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

Я использую C ++.

Answer 1

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

Хорошо, я вижу, вы отредактировали, чтобы добавить язык. Для C ++ есть несколько вариантов. Я считаю, что механизм сериализации Boost довольно хорош. Кроме того, страница библиотеки сериализации Boost также описывает альтернативы. Вот ссылка:

http://www.boost.org/doc/libs/1_37_0/libs/serialization/doc/index.html

Answer 2

Откажитесь от указателей на индексы.

Это немного похоже на создание на диске DAWG , которое я сделал некоторое время назад. То, что сделало это настолько приятным, было то, что он мог быть загружен непосредственно с mmap вместо чтения файла. Если хеш-пространство является управляемым, скажем, 2 ¹⁶ или 2 ²⁴ записей, то я думаю, что я бы сделал что-то вроде этого:

• Вести список свободных индексов. (если таблица пуста, каждый цепной индекс будет указывать на следующий индекс.)
• Когда необходимо связывание, используйте свободное место в таблице.
• Если вам нужно поместить что-то в индекс, который занят скваттером (переполнение откуда-либо):
  • записать индекс (назовем его N)
  • поменяйте местами новый элемент и скваттер
  • поместите скваттер в новый свободный индекс (F).
  • следуйте по цепочке в хэш-индексе скваттера, чтобы заменить N на F.
• Если у вас закончились свободные индексы, вам, вероятно, понадобится таблица большего размера, но вы можете справиться немного дольше, используя mremap, чтобы создать дополнительное пространство после таблицы.

Это должно позволить вам отображать и использовать таблицу напрямую, без изменений. (Страшно быстро, если в кеше ОС!) но вы должны работать с индексами, а не с указателями. Довольно пугающе иметь мегабайты, доступные в режиме syscall-round-trip-time, и все равно иметь их меньше, чем в физической памяти, из-за подкачки.

Answer 3

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

Answer 4

Предполагается, что C / C ++: использовать индексы массива и структуры фиксированного размера вместо указателей и распределения переменной длины. Вы должны иметь возможность напрямую записывать () структуры данных в файл для последующего чтения () ing.

Для чего-либо более высокого уровня: многие API более высокого языка имеют средства сериализации. В Java и Qt / C ++ есть методы, которые сразу приходят на ум, поэтому я знаю, что и другие тоже.

Answer 5

Возможно, DBM может быть вам полезно.

Answer 6

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