Хеш-функции

Операции использующие хэш-таблицы эффективны, потому что позиция хранимой суммы может быть вычислена, используя ключ. Хэш-таблицы обычно реализуются как массив значений, а хеш-функция используется, чтобы отобразить ключ как индекс в пределах этого массива. Индекс это то, где сохранено соответствующее значение ключа. Другие алгоритмы поиска, такие как линейный или двоичный поиск, не могут отобразить ключ на позицию его значения так быстро как хэш-таблицы. Эти алгоритмы должны выполнить больше сравнений, чтобы найти индекс хранимой суммы. Время это поиск и увеличения числа сохраненных элементов.

Рисунок 1 Демонстрационная хеш-функция

Отображение ключей к индексам демонстрируется в рисунке 1. Здесь хеш-функция генерирует индекс, основанный на самой правой цифре значения ASCII второй буквы фамилии человека. Например, на имя "Hanson, Bob", вторая буква является "a". Значение ASCII "a" 97. Самая правая цифра 97 7. Поэтому, запись для "Hanson, Bob" сохранен в хэш-таблице по индексу 7.

Рисунок 3 Демонстрационная хэш-таблица

Хэш-таблица на рисунке 2 показывает каждое имя в своей отображенной позиции. Преимущество хэш-таблицы состоит в том, что, чтобы найти запись, одно должна иметь единственную хеш-функцию к ключу.

Популярный метод, используемый в реализации хеш-функции, division method. Как все хеш-функции, метод подразделения отображает ключ на индекс в пределах хэш-таблицы. Реализация метода подразделения включает преобразование ключа к переменной типа unsigned int. Затем, это значение делится на размер хэш-таблицы. Остаток от этого подразделения используется в качестве индекса.

Проблема возникает, когда мы полагаем, что обычно есть еще много ключей чем расположения в пределах хэш-таблицы. Это означает, что хеш-функция может потенциально отобразить два или больше отличных ключа на один и тот же индекс. Рассмотрим попытку добавить имя "Anderson, Jeff" в хэш-таблицу на рисунке 2. Применение хеш-функции дает индекс 0. Но однако, уже существует по индексу 0 имя "Adderly, Maria". Когда хеш-функция отображает больше чем один ключ на тот же самый индекс происходит коллизия.

Реализации хэш-таблицы усложняются фактом, что они должны обработать потенциальные коллизии. Эти механизмы, чтобы обработать коллизии обсуждаются подробно в главе 20 в учебнике Вайс. В основном, коллизии уменьшают производительность операций хэш-таблицы. Лучший способ сократить количество коллизий, и таким образом увеличить эффективность хэш-таблицы, состоит в том, чтобы использовать хорошую хеш-функцию. Хорошая хеш-функция равномерно распределяет отображение ключей всюду по позициям в хэш-таблице.

Это - хорошая практика разработки программного обеспечения, чтобы разделить хеш-функцию от реализации хэш-таблицы. Это позволяет программисту настраивать хеш-функцию к данным, хранившим определенным экземпляром хэш-таблицы. Перечисление 1 определяет хэш-таблицу как класс тот оператор перегрузок ().