Как я могу сохранить хеш-таблицу с отдельной цепочкой в файле на диске?
Генерация данных, хранящихся в хеш-таблице во время выполнения, обходится дорого, было бы быстрее просто загрузить HT с диска... если бы я только мог понять, как это сделать.
Изменить: поиск выполняется с загруженным в память HT. Мне нужно найти способ сохранить хеш-таблицу (в памяти) в файл в каком-то двоичном формате. Так что в следующий раз, когда программа запустится, она может просто загрузить HT с диска в оперативную память.
Я использую С++.
Будете ли вы выполнять поиск с диска или вам нужно только сохранить хэш-таблицу? Hank 07.02.2009
Хэнк, поиск выполняется с загруженным в память HT. Да, мне просто нужно сохранить хеш-таблицу. Girish 07.02.2009
пожалуйста, предоставьте более подробную информацию - язык, система и т. д. Eli Bendersky 07.02.2009
Какой язык вы используете? Обычный метод - выполнить какую-то двоичную сериализацию.
Хорошо, я вижу, вы отредактировали, чтобы добавить язык. Для С++ есть несколько вариантов. Я считаю, что механизм сериализации Boost довольно хорош. Кроме того, на странице библиотеки сериализации Boost также описаны альтернативы. Ссылка здесь:
Предполагая C/C++: используйте индексы массива и структуры фиксированного размера вместо указателей и распределения переменной длины. Вы должны иметь возможность напрямую писать() структуры данных в файл для последующего чтения().
Для чего-либо более высокого уровня: многие API-интерфейсы более высокого уровня имеют средства сериализации. И в Java, и в Qt/C++ есть методы, которые сразу приходят на ум, поэтому я знаю, что и у других они тоже есть.
Ответ 3 · рейтинг 5 · Zach Scrivena
Вы можете просто записать всю структуру данных непосредственно на диск, используя сериализацию (например, в Java). Однако вам может потребоваться прочитать весь объект обратно в память, чтобы получить доступ к его элементам. Если это нецелесообразно, вы можете рассмотреть возможность использования файла произвольного доступа для хранения элементов хэш-таблица. Вместо того, чтобы использовать указатель для представления следующего элемента в цепочке, вы просто использовали бы позицию байта в файле.
Ответ 4 · рейтинг 5 · Anders Eurenius
Откажитесь от указателей на индексы.
Это немного похоже на создание на диске DAWG, что я сделал некоторое время назад. Что сделало это таким приятным, так это то, что его можно было загрузить напрямую с помощью mmap вместо чтения файла. Если хеш-пространство управляемо, скажем, 216 или 224 записей, то я думаю, что сделал бы что-то вроде этого:
Держите список бесплатных индексов. (если таблица пуста, каждый индекс цепочки будет указывать на следующий индекс.)
Когда требуется цепочка, используйте свободное место в таблице.
Если вам нужно поместить что-то в индекс, который занят скваттером (переполнение из другого места):
запишите индекс (назовем его N)
поменять местами новый элемент и скваттер
поместите скваттер в новый свободный индекс (F).
следуйте по цепочке хэш-индекса скваттера, чтобы заменить N на F.
Если у вас полностью закончились свободные индексы, вам, вероятно, понадобится таблица большего размера, но вы можете справиться немного дольше, используя mremap для создания дополнительного места после таблицы.
Это должно позволить вам отображать и использовать таблицу напрямую, без изменений. (страшно быстро, если в кеше ОС!) но вам нужно работать с индексами вместо указателей. Довольно пугающе иметь мегабайты, доступные во время syscall-round-trip-time, и при этом занимать меньше, чем в физической памяти, из-за подкачки.
Если ваша реализация хэш-таблицы хороша, то просто сохраните хеш и данные каждого объекта - размещение объекта в таблице не должно быть дорогим, учитывая хэш, а отсутствие сериализации таблицы или цепочки напрямую позволяет вам варьировать точную реализацию между сохранением и загрузить.
