Представьте, что у вас есть две записи, одна с ключом «foo», а другая с ключом «bar». Скажем так, записи имеют фиксированную длину 64 байта, и что "foo" хеширует до 0x4000, а "bar" - до 0x0100.
В «организации хеш-файлов» у вас есть функция, которая принимает ключ поиска и напрямую вычисляет адрес. Таким образом, если вы добавите в файл «foo» и «bar», запись для «foo» начнется с адреса 0x4000 в файле, а запись «bar» начнется с адреса 0x0100 в файле.
Файл будет выглядеть примерно так:
Address Range Contents
------------- --------
0x0000 - 0x00FF empty space
0x0100 - 0x013F "bar" record
0x0140 - 0x3FFF empty space
0x0400 - 0x403F "foo" record
В «организации хеш-индекса» у вас есть вторичная структура данных - индекс, который сообщает вам, где начинается конкретная запись. Скажем, файл пуст и вы добавили «foo». Ваша хеш-функция вычисляет значение 0x4000. Вы добавляете это в индекс (хеш-карту или что-то подобное), и, поскольку файл пуст, присвоенное значение равно 0. Когда вы добавляете вторую запись, «bar», добавляется хеш-ключ 0x0100 и присваивается значение. это 0x0040. У вас есть индекс:
Key Value
-------------
0x0100 0x0040
0x4000 0x0000
И файл выглядит так:
Address Range Contents
-----------------------------
0x0000 - 0x003F "foo" record
0x0040 - 0x007F "bar" record
И, конечно, вы должны где-то хранить индекс. Это может быть в отдельном файле, или, возможно, в начале или в конце файла данных, или разбросано по всему файлу. Множество разных возможностей.
В первом случае в файле много потраченного впустую места, но вы можете напрямую посмотреть позицию записи: хешировать ключ, и результатом будет адрес записи.
Во втором случае вы хешируете ключ, а затем ищите результат в индексе, чтобы получить ключ записи. Основным преимуществом здесь является то, что он потенциально экономит много места в файле, но у вас возникают проблемы с тем, где сохранить индекс.
В любом случае у вас должен быть способ разрешать конфликты хешей.
person
Jim Mischel
schedule
18.06.2018
