Довольно часто встречаются ситуации, когда обработке подлежат много маленьких строк — слов, которые надо сохранять в некоторой единой структуре — словаре. Сами слова не требуют для своего представления сложной структуры: для их представления вполне достаточно стандартных способов описания строк. Однако для словаря необходимо выбрать такое представление, которое бы обеспечило максимальную эффективность выполнения основной операции над словарем — поиска слова в словаре.
Самым простым представлением для словаря будет, конечно, массив слов. Для обеспечения эффективности поиска можно обеспечить упорядоченность элементов этого массива, тогда поиск слов можно производить с помощью алгоритма двоичного поиска, изученного ранее, который обеспечивает нахождение нужного слова среди множества из п слов за количество операций, пропорциональное log2 п. К сожалению, эффективность работы со словарем, организованным таким образом, резко снижается, когда требуется добавлять в него новые слова или удалять имеющиеся. Каждая вставка или удаление слова требуют сдвига в среднем около половины всех имеющихся в массиве слов. Кроме того, при вставке слов возникает проблема отведения новой памяти, если первоначально отведенной под словарь памяти не хватает для размещения новых элементов.
Одним из способов решения этой проблемы является использование так называемой функции расстановки или хеширования. Слово хеширование происходит от английского hash, означающего "крошить", "резать на кусочки", и отражает характер работы этой функции.
Основная идея применения функции расстановки состоит в следующем. Словарь будем представлять в виде массива слов, но помещать слова в него будем не в соответствии с алфавитным порядком, а в соответствии со значениями некоторой простой функции, вычисленной над словом. Такая функция — функция расстановки, — получая в качестве аргумента некоторое слово, выдает в качестве результата некоторое целое число — индекс в словаре, под которым следует хранить это слово. Если каждому слову будет соответствовать свое значение функции расстановки, то поиск в словаре становится ненужным. Вместо поиска осуществляется вычисление значения функции расстановки, после чего слово находится сразу же по вычисленному индексу.
К сожалению, на практике оказывается невозможным определить функцию расстановки так, чтобы каждому слову соответствовало свое уникальное значение индекса. Это приводит к тому, что два или более слов получают одно и то же значение функции расстановки. Говорят, что в этом случае происходит конфликт хеш-индексов (коллизия). Один из самых простых способов разрешения коллизий состоит в том, чтобы помещать слово, вызвавшее конфликт в один из соседних элементов массива. Тогда поиск и вставка новых слов будет производиться хотя и не за один шаг, но все же достаточно быстро.
Естественным требованием для функции расстановки будет требование простоты ее вычисления. Но это далеко не единственное, что требуется от хорошей функции расстановки. Прежде всего, надо обеспечить равномерное распределение вычисленных индексов слов в словаре.
Пусть функция code (с) по заданной букве выдает ее номер в латинском алфавите (если символ не является буквой латинского алфавита, то будем считать, что функция code возвращает значение 0). Вот как, например, может выглядеть эта функция:
intcode(char c)
{
returnstrchr("abcdefghijklmnopqrstuvwxyz", c) + 1;
}
На самом деле, на практике обычно просто используют внутренний код каждого символа, так что фактически в использовании функции code нет необходимости.
Далее эту функцию можно использовать как базовую для определения функции расстановки. Прежде всего, обеспечим зависимость значения функции расстановки от всех символов слова. Для этого сложим коды всех букв. Дополнительно, для того чтобы позиция буквы в слове также играла некоторую роль, будем добавлять к коду каждой буквы номер ее позиции. Далее решим, словарь какого размера нам потребуется. В конечном итоге значение функции хеширования должно получиться достаточно равномерно распределенным на множестве всех обрабатываемых слов, и попадать в диапазон [0, n-1], где п — размер словаря. Достаточно равномерное распределение получается, если вычислять индекс по формуле (Р * Х+ Q) % n, где числа Р и Q — это некоторые простые числа, по порядку близкие к п, X— вычисленная сумма кодов букв слова, а символ % задает операцию вычисления остатка от целочисленного деления. Если, например, считать, что словаря в 1000 слов будет достаточно для наших целей, то можно выбрать для Р и Q значения 557 и 811, и тогда функция расстановки примет следующий вид:
inthash(conststring & str) {
intsum = 0;
for (int i = 0; i < str.length(); i++) {
sum += code(str[i]) + i;
}
return(557 * sum + 811)% 1000;
}
Теперь можно задать словарь, в котором будет храниться некоторое множество слов. Мы определим функцию добавления слова в словарь и функцию, выясняющую, содержит ли словарь заданное слово. В обеих функциях слово (или место для этого слова) ищется схожим образом: по слову вычисляется значение функции расстановки, затем происходит перебор позиций слов в массиве, предназначенном для их хранения, до тех пор, пока либо искомое слово не будет найдено, либо не встретится пустое значение.
Если слова не удаляются из словаря, а только добавляются в него, то такой алгоритм поиска будет корректным, хотя при большой загруженности словаря поиск может осуществляться достаточно долго. В предельном случае, когда все позиции в словаре заняты, при поиске слова может оказаться необходимым перебрать все слова.
Листинг : Определение простого словаря