Метод хэширования
То есть, создается функция, которая хранит в себе непосредственно сравниваемые значения и их индексы. Функиця принимает значения для сравнения. Если найдено одинаковое значение, то она возвращает его адрес или позицию.
Или что то я не правильно понял? Если не сложно, напишите, пожалуйста пример на C. Буду очень благодарен :)
Ребят, расскажите, пожалуйста по-подробнее про поиск методом хэширования. Весь рунет облазил, много чего нашел. Но мне не понятен сам принцип.
То есть, создается функция, которая хранит в себе непосредственно сравниваемые значения и их индексы. Функиця принимает значения для сравнения. Если найдено одинаковое значение, то она возвращает его адрес или позицию.
Или что то я не правильно понял? Если не сложно, напишите, пожалуйста пример на C. Буду очень благодарен :)
Хэширование следующим образом используется в поиске:
Исходное множество S просто разбиванется на B сегментов(с номерами от 0 до B - 1). Эти сегменты обычно имеют одинаковую длину n. Затем строиться хэш-функция h(x), ставящая в соответствие каждому элементу x из множества S номер сегмента.
Например:
0 сегмент - 0,3,6,9
1 сегмент - 1,4,7,10
2 сегмент - 2,5,8,11
Это пример самой простой хэш функции mod.
В данном случае mod 3(Остаток от деления на 3).
Сегменты обычно представляют собой списки.
Так же строится таблица сегментов, которая для каждого номера сегмента ассоциирует указатель на начало списка элементов принадлежащих этому списку.
Теперь когда нам нужно найти элемент по ключу, мы с помощью хэш-функции на ходим сегмент, где он располагаеться, выбирая соответствующий список, бежим по этому списку и ищем совпадение с нашим ключем.
Когда нашли совпадение, то нашли затребованный элемент.
Таким образом поиск сегмента имеет сложность порядка O(1), а список мы пробегаем за время порядка O(N/B).Тоесть всего O(N/B), где N - кол-во элементов в списке, а B - кол-во сегментов.
Если не понятно давай e-mail пошлю это же но более подробно)
З.Ы. Это так называемое открытое хэширование.
Применяется когда мошность(aka кол-во элементов множества) ключей> реально используемых
Применяется когда мошность(aka кол-во элементов множества) ключей> реально используемых
Спасибо. Я, кстати, нашел немного другое понятие. В алгоритме они одинаковы. Но написано по-разному =). Спасибо.