Понятие хеширования
Для решения задачи поиска необходимого элемента среди данных большого объема был предложен алгоритм хеширования (hashing – перемешивание), при котором создаются ключи, определяющие данные массива и на их основании данные записываются в таблицу, названную хеш-таблицей. Ключи для записи определяются при помощи функции i = h(key), называемой хеш-функцией. Алгоритм хеширования определяет положение искомого элемента в хеш-таблице по значению его ключа, полученного хеш-функцией.
Понятие хеширования– это разбиение общего (базового) набора уникальных ключей элементов данных на непересекающиеся наборы с определенным свойством.
Возьмем, например, словарь или энциклопедию. В этом случае буквы алфавита могут быть приняты за ключи поиска, т.е. основным элементом алгоритма хеширования является ключ (key). В большинстве приложений ключ обеспечивает косвенную ссылку на данные.
Фактически хеширование – это специальный метод адресации данных для быстрого поиска нужной информации по ключам.
Если базовый набор содержит N элементов, то его можно разбить на 2N различных подмножеств.
Хеш-таблица и хеш-функции
Функция, отображающая ключи элементов данных во множество целых чисел (индексы в таблице – хеш-таблица), называется функцией хеширования, или хеш-функцией:
i = h(key);
где key – преобразуемый ключ, i – получаемый индекс таблицы, т.е. ключ отображается во множество целых чисел (хеш-адреса), которые впоследствии используются для доступа к данным.
Однако хеш-функция для нескольких значений ключа может давать одинаковое значение позиции i в таблице. Ситуация, при которой два или более ключа получают один и тот же индекс (хеш-адрес), называется коллизией при хешировании.
Хорошей хеш-функцией считается такая функция, которая минимизирует коллизии и распределяет данные равномерно по всей таблице, а совершенной хеш-функцией – функция, которая не порождает коллизий:
Разрешить коллизии при хешировании можно двумя методами:
– методом открытой адресации с линейным опробыванием;
– методом цепочек.
Хеш-таблица
Хеш-таблица представляет собой обычный массив с необычной адресацией, задаваемой хеш-функцией.
Хеш-структуру считают обобщением массива, который обеспечивает быстрый прямой доступ к данным по индексу.
Имеется множество схем хеширования, различающихся как выбором удачной функции h(key), так и алгоритма разрешения конфликтов. Эффективность решения реальной практической задачи будет существенно зависеть от выбираемой стратегии.
Дата добавления: 2014-12-30; просмотров: 939;