Hash + mapping или index + mapping для конденсирования использования строк

Question

У меня есть ~ 200K именованных свойств и ~ 25K файлов. Я извлекаю, сохраняются ли свойства или нет для каждого файла, используя Python, как набор свойств, которые хранятся, по одному для каждого файла.

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

Дополнительная обработка включает в себя чтение этих наборов 20K и работу с накопленными данными. для создания отчета об этом наборе файлов/свойств.

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

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

Альтернативой использованию индекса в отсортированном списке имен является использование str. hash() значение как индекс, который будет означать, вероятно, более быструю обработку, но меня беспокоит возможность двух неравных строк, заканчивающихся тем же hash() значение. Может ли это случиться?

Я бы использовал ту же исполняемую версию Python и версию ОС на всех машинах.

Answer 1

Знаете ли вы недвижимость заранее? Если вы это сделаете, вы можете рассмотреть Perfect hashing (то есть вы можете распространять настройки хэша вместо полного списка свойств/файлов).

Очень грубый (но возможно рабочий путь) имел бы несколько разных хеш-функций (h1, h2 ...); начало, например. с str.hash() и вычислить хеши. Если есть столкновения, попробуйте использовать кортеж (h1 (свойство), h2 (свойство)) как хэш. Если есть еще столкновения, используйте (h1 (свойство), h2 (свойство), h3 (свойство)) и т. Д., Пока не произойдет столкновений. Функции h_x могут быть фактически конфигурируемой функцией, и рекомендуется использовать некоторые случайные хеш-функции.

Однако мне кажется, что это может быть излишним, просто распределяя список файлов/свойства могут быть намного проще ...

Answer 2

Хеши могут сталкиваться. Вам придется это учитывать.