Автор: Xan Gregg
Статья впервые опубликована в журнале Forth Dimensions XVII/4
оригинальная статья взята отсюда
http://www.forth.org/fd/hash.html
Перевел
mOleg
Хеширование в форте.
"Компромисс между временем и пространством это хеширование"
Хеширование обеспечивает быстрый метод поиска больших несортированных объемов данных за счет использования дополнительной памяти. Роберт Седжевик в своей книге "Алгоритмы" кратко описывает хеширование как "прямо указывающие ссылки в таблице за счет арифметических преобразований ключей в адресном списке".
Формулировка станет понятна вам в конце статьи, но сначала давайте рассмотрим простой пример.
Допустим, вы должны написать код для управления базой данных с приблизительно 50000 записей, каждую из которых индексирует 16 битное число. Вставки и удаления записей часты, поэтому не могут быть медленными, и поиск записей
происходит часто, поэтому должен так же быть быстрым. При этом у вас 64кб ОЗУ в дополнение к дисковому пространству, где находятся данные, и вы знаете, что каждая запись имеет уникальный трехбуквенный код, подобно аэропортам в США.
Как форт-программист, вы понимаете, что трехбуквенная строка так же является числом, представляемым в 26ричной системе исчисления, и вы делаете таблицу 26x16x16=17,576 ячеек, где каждая ячейка содержит номер записи. Вставка и удаление просты -- вы только должны обновить таблицу вместе с каждой операцией. Поиск записи по ее ключу предполагает только упаковку трех
символов в 15-битное число, и использование этого числа как индекса в таблице. После чего вы получает номер записи.
Если вы можете так сделать, вы уже понимаете основную идею хеширования. Хеширование требует наличия хеш-функции и хеш-таблицы. Хеш-функция конвертирует ключевое значение, такое как текстовая строка или большое число, в индекс внутри хеш-таблицы. Каждая ячейка в хеш-таблице указывает на запись в базе.
В примере код для преобразования трех букв в 15 битное число является хеш-функцией, и таблица с номерами записей - это хеш таблица. Хеш-функция может выглядеть так:
Код:
: ID>INDEX ( addr -- n ) \ addr points to three uppercase letters
COUNT [CHAR] A - \ addr+1 n1
SWAP COUNT [CHAR] A - \ n1 addr+2 n2
SWAP C@ [CHAR] A - \ n1 n2 n3
26 * + 26 * + + ; \ n
Пока у вас 64кб памяти и скорость поиска столь важна, вы можете умножать на 32, вместо 26, так как вы можете использовать операцию сдвига, вместо умножения, то есть не 26 * , а 5 LSHIFT. Получение эффективной хеш-функции очень важно, поэтому она часто пишется на ассемблере.
Хеширование становится более интересным когда ключи очень велики, чтобы их можно было упаковать в уникальное число. Например, что, если ключем является фамилия персоны? Это более реалистично, чем уникальный трехсимовольный ключ
описываемый ранее. Не столь очевидно, как использовать хеширование в таком случае. Нам нужна хеш-функция для конвертирования строк переменной длины в табличный индекс, и нам необходима методика распределения множества записей
сведенных в один табличный индекс.
Хеш-функцией может быть почти все. Далее приводится несколько возможностей для преобразования фамилии в 15 битное число:
1) использовать первые три буквы, пять бит на цифру
2) использовать последние три буквы, пять бит на цифру
3) использовать первые пять букв, три бита на цифру (младшие)
4) перемножить все цифры и найти остаток от деления на 2^15
5) взять пять бит с первой буквы, и по два бита со следующих пяти букв
6) использовать три младших бита из байта длины, и по три бита со следующих четырех букв
7) исользовать сумму всех символов строки, взятую по модулю 2^15
8) складывать все символы строки как: буква(i)*2^i, потом 2^15 AND
Я уверен, вы можете придумать больше. Сложность следует за простотой. Вам нужна быстрая функция дающая качественно случайное распределение ключей. Первый приведенный вариант не очень удачен, потому что много имен, вероятно начинаются с одинаковых символов, в результате распределение получится плохим. Четвертый вариант плох по двум причинам: умножение медленная операция, и распределение не очень удачно, так как многократное умножение часто дает четные числа. Седьмой вариант плох, потому что сумма всех цифр не достигнет 2^15. Восьмой вариант пытается побороть маленький диапазон комбинируюя сдвиг и сложение, и может дать хороший результат при качественной настройке.
Любые другие хеш-функции так же могут быть хороши после подстройки. Например, когда вы берете три бита с символа, как решить какие биты стоит выбрать? Верхние три бита очевидно не подходят, потому что все заглавные буквы начинаются с одинаковой трехбитовой последовательности. Младшие три бита смотрятся подходящими, но тоже не достаточно. H, P, X всегда дают 0; B,J,R и Z дают 1 ; а G, O, W - 7; это не выглядит равнозначной группировкой. (Хотя кто знает? Возможно Greggs, Ouversons, и Wests так же часто встречаются, как Browns, Joneses, Rathers, и Zwickkers.) Единственная возможность быть
уверенным - собрать статистику на типичном наборе данных и посмотреть распределение хеш-значений. К сожалению, часто приходится разрабатывать код лишь с частью набора данных, что требует от вас более развитой интуиции.
Перед слишком глубоким погружением в выбор функций хеширования, мы должны рассмотреть еще одну проблему: что делать, если два или более ключей разделяют один и тот же индекс в хеш-списке, которая называется колизией. Существуют различные решения, но предпочитаемое мною заключается в добавлении поля к каждой записи хеш-списка, который может указывать на другую запись. Тогда каждая ссылка в таблице становится началом односвязанного списка, с другими ссылками, которые добавляются к каждой новой индексируемой записи.
Другое решение - использование вторичной хеш-функции для получения другого индекса, или добавление номера к полученному индексу для получения нового индекса. В любом случае существует возможность появления колизий, которые требуют нахождения другого хеш-индекса, и так далее. Это решение требует чтобы хеш-список имел как минимум одну ссылку на каждую запись.
Любые варианты требуют больше работы во время поиска. Вы можете сравнивать ключи повторно до тех пор, пока значения не станут равны, либо искать значение в другом хеш-списке. В результате простота удаления и добавления записей становится сложной.
Таким образом хеширование не так просто, как это показалось в первом примере, тем не менее остается очень удобным если время поиска критично. Классически хеширование используется в символьных списках компиляторов. Программа может иметь тысячи символов, которые компилятор должен просматривать очень часто в поисках имени, во время разбора исходных текстов. Я применял хеширование в MacForth словарях, и я знаю, что некоторые другие форты так же используют хешированные словари.
Первый в конце статьи содержит некий общий хеширующий код. FILL-TABLE неумело резервирует записи на лету в пространстве данных, но базовые слова (INSERT-RECORD DELETE-RECORD FIND-RECORD) дают хорошую начальную базу для любого, пытающегося разобраться с хешированием. Код использует односвязный список для разрешения колизий.
ANALYZE-HASH - полезное слово для получения информации о распределении хеш-ключей в хеш-списке. Оно отображает линии, пронумерованные от нуля до девяти, которые показывают как много используется односвязных списков и какой размер они имеют. В другой линии отображается средняя длина списков (без учета пустых). Это значение необходимо минимизировать. Другой полезный инструмент анализа используемый мной в прошлом - отображать хеш таблицу, показывая длину односвязных списков в хеш-таблице. Иногда это разоблачает неиспользуемые индексы, либо индексы, в которых слишком много записей.
Таблица 1 показывает средние длины списков для различных хеш-функций для 3448 форт слов, и размеры хеш-таблиц на 1024 и 4096 ссылок.
<pre>
Таблица 1.
Средняя длина цепочек для различных хеш-функций.
Hash Function W/1024 W/4096
Low bits of first three chars 5.23 3.44
Low bits of length and first two chars 4.36 2.30
Low bits of last three chars 6.31 4.41
Product of first three chars 6.64 3.91
Sum of char(i) * 2^i 3.56 1.57
</pre>
Все эти хеш функции имеют подходящие результаты. Бинарный поиск на этих же данных будет требовать от нас просматривания log2(3448)=11.8 записей. Последний вариант близок к оптимуму (3448.1024=3.37), и является моим любимым. Он похож на функцию, используемую в PowerMacForth, и имеет преимущество в том, что много символов включаются в результат.
В этой таблице впервые упоминает размер хеш-списка (с момента объявления 64К хеш-списка). Чем больше места используется под хеш-список, тем лучше работает поиск (потому что меньше колизий), но конечно же отнимает больше памяти. Компромисс между временем и пространством в хешировании обсужден.
Код:
anew --hash--
( Generic Hashing Code
Each record must start with one cell for use by the
hashing code. It must be followed by a counted string
which is the key. Variable-length data may optionally
follow. )
: ALLOTERASE ( n -- ) \ utility word
HERE SWAP DUP ALLOT ERASE ;
1024 CONSTANT /HASHTABLE
CREATE HASHTABLE
/HASHTABLE CELLS ALLOT
: INIT-HASHING ( -- )
HASHTABLE /HASHTABLE CELLS ERASE ;
: MY-HASH-FUNCTION ( key-addr -- table-index )
\ you should override this function
COUNT 0 SWAP 0 DO \ addr cur-index
SWAP COUNT I LSHIFT ROT +
LOOP NIP
/HASHTABLE 1- AND ; \ assumes power of 2
: KEY>INDEX ( key-addr -- table-index )
MY-HASH-FUNCTION
0 MAX /HASHTABLE 1- MIN ; \ for safety during development
: INSERT-LINK ( recAddr tableAddr -- )
\ insert at top of linked list for this index
DUP @ ROT DUP >R ! \ recAddr.link <= previous top
R> SWAP ! ; \ top <= recAddr
: INSERT-RECORD ( recAddr -- )
DUP CELL+ KEY>INDEX CELLS HASHTABLE + INSERT-LINK ;
: DELETE-LINK ( recAddr tableAddr -- )
\ remove link from list
SWAP >R
BEGIN
DUP @ R@ <> SWAP @ 0 <> AND
WHILE
@ \ no match, so go to next link
REPEAT
DUP @ 0 <> IF
R> @ SWAP ! \ prev.link <= rec.link
ELSE
R> DROP \ do nothing if not found
THEN ;
: DELETE-RECORD ( recAddr -- )
DUP CELL+ KEY>INDEX CELLS HASHTABLE + DELETE-LINK ;
: FIND-LINK ( addr tableAddr -- recAddr or 0 )
>R BEGIN
@ DUP
WHILE
DUP 1 CELLS + COUNT
R@ COUNT COMPARE 0= IF
R> EXIT \ found match, so exit
THEN
@ \ no match, so go to next link
REPEAT ;
: FIND-RECORD ( addr -- recAddr or 0 )
DUP KEY>INDEX CELLS HASHTABLE + FIND-LINK ;
\ ---- analysis words ----
: FILL-TABLE ( -- )
INIT-HASHING
S" FILEDATA1" R/O OPEN-FILE IF ABORT THEN
>R \ stash the file-id
BEGIN
HERE 32 CELL+ ALLOTERASE \ space for text and link
DUP CELL+ 1+ 31 R@ READ-LINE
0= OVER 0 <> AND
WHILE
DROP \ recAddr bytesRead
DUP IF
OVER CELL+ C!
INSERT-RECORD
ELSE
2DROP
THEN
REPEAT 2DROP DROP
R> CLOSE-FILE DROP ;
10 CONSTANT MAX-DEPTH
CREATE DEPTHS MAX-DEPTH CELLS ALLOT
VARIABLE TOTAL-ENTRIES
VARIABLE TOTAL-LISTS
: COUNT-LINKS ( tableAddr -- n )
0 SWAP BEGIN @ DUP WHILE SWAP 1+ SWAP REPEAT DROP ;
: ANALYZE-HASH ( -- )
MAX-DEPTH 0 DO I CELLS DEPTHS + OFF LOOP
TOTAL-ENTRIES OFF
TOTAL-LISTS OFF
/HASHTABLE 0 DO
I CELLS HASHTABLE + COUNT-LINKS
DUP TOTAL-ENTRIES +!
DUP 0> IF 1 TOTAL-LISTS +! THEN
MAX-DEPTH 1- MIN
1 SWAP CELLS DEPTHS + +!
LOOP
MAX-DEPTH 0 DO
CR I 3 .R 2 SPACES I CELLS DEPTHS + @ 5 .R
LOOP CR ." AVE = "
TOTAL-ENTRIES @ 100 TOTAL-LISTS @ */
S>D <# # # [CHAR] . HOLD #S #> TYPE ;