39. Алгоритмы вычисления хэш-функции.

Преобразование ключей в адреса в таблице или разбиение множества на подмножества.

Организация: прямая и открытая адресация

Если разным значениям ключей таблицы хеш-функция генерирует одинаковые адреса, то говорят, что возникает коллизия.

При прямой адресации строится для каждого адреса таблицы H связный список элементов, ключи которых отображаются на этот адрес. Коллизия разрешается с помощью цепочек. В строке таблицы Hс номером jхранится не сам элемент, а указатель на голову списка тех элементов, у которых хэш-значение ключа равно j, если нет то – NULL. Хэш-таблица может быть представлена массивом списков.

При открытой адресации все записи хранятся в самой хэш-таблице(хэш-списков нет), каждая ячейка содержит значение либо NULL.

Алгоритмы вычисления хэш-функции:

Модульноехэшированиеh(key)=key%hashTableSize

hashTableSize - простое число 0 до (hashTableSize-1)

Мультипликативныйметодh(key)=[hashTableSize(key×Amod1)]

1) hashTableSize =2^p

2) 0≤A≤1 A=(sqrt(5) - 1)/2 = 0.6180339887499

Аддитивныйметод

длястрокпеременнойдлиныypedef unsigned char HashIndexType;

 Недостатком является не различение схожих слов и анаграмм h(XY)= h(YX )

HashIndexTypeHash(char *str)

{

HashIndexType h = 0;

while (*str) h += *str++;

return h;

}

Универсальное хэширование

выбор хэш-функции во время исполнения программы случайным образом из некоторого множествавероятность конфликта = 1/hashTableSize

40. Хэш-таблицы. Прямая адресация в хэш-таблицах.

Сочетание массивов и списков с небольшой добавкой математики пример- записная книжка.

[_____]→[date|____]→[date|____]→[date|NULL]

[NULL]

[NULL]

[_____]→[date|NULL]

[NULL]

Понятие:

• хэш-таблица — это динамическое множество, поддерживающее словарные операции: добавление, поиск и удаление элемента, использующее специальные методы адресации. Основное отличие таблиц от других динамических множеств – вычисление адреса элемента по значению ключа.

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

Основное назначение хеш-функции поставить в соответствие различным ключам по возможности разные не отрицательные целые числа.

Если разным значениям ключей таблицы хеш-функция генерирует одинаковые адреса, то говорят, что возникает коллизия.

При прямой адресации строится для каждого адреса таблицы H связный список элементов, ключи которых отображаются на этот адрес. Коллизия разрешается с помощью цепочек. В строке таблицы Hс номером jхранится не сам элемент, а указатель на голову списка тех элементов, у которых хэш-значение ключа равно j, если нет то – NULL. Хэш-таблица может быть представлена массивом списков.

• В массиве H хранятся списки пар

• Среднее время выполнения операций = коэффициенту заполнения

• ключи

• числа из множества U={0,1,…,m-1} (m- не велико)

• для хранения множества - массив T[0..m-1]

• таблица прямой адресации (direct-adresstable)

Реализация операций

• поиск - return T[k];

• вставка T[key[x]]<-x;

• удаление T[key[x]]->x;

• каждая из операций требует времени О(1).

Недостатки:

• если множество ключей велико, то хранить а памяти массив T размером |U| непрактично и не возможно иногда.

• Если число реально присутствующих в таблице записей мало по сравнению с мощностью U , то много памяти тратиться зря

• требуются механизмы разрешения коллизий

41. Хеш-таблицы. Коллизии. Построение цепочек.

Хеш-таблица (перемешанные таблицы, таблицы с вычисляемыми адресами) динамическое множество, поддерживающее словарные операции: добавление поиск и удаление элемента и использующее специальные (ассоциативные) методы адресации.

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

42. Хеш-таблицы. Открытая адресация. Способы вычисления последовательности испробованных мест при открытой адресации (линейный, квадратичный).

Хеш-таблица (перемешанные таблицы, таблицы с вычисляемыми адресами) динамическое множество, поддерживающее словарные операции: добавление поиск и удаление элемента и использующее специальные (ассоциативные) методы адресации.

Существует еще один способ организации хеш-таблиц - открытая адресация. В этом случае для хранения элементов динамического множества используются не списки, а сама таблица. Каждый вход таблицы при открытой адресации содержит либо NIL (строка пуста), либо сам элемент .

Линейный алгоритм последовательности проб основан на формуле :

h(key)=(h’(key)+i) mod hashTableSize.

Квадратичый алгоритм последовательности проб основан на формуле :

h(key)=(h’(key)+ + ) mod hashTableSize.

43. Хеш-таблицы. Основные свойства и эффективность.

Хеш-таблица (перемешанные таблицы, таблицы с вычисляемыми адресами) динамическое множество, поддерживающее словарные операции: добавление, поиск и удаление элемента и использующее специальные (ассоциативные) методы адресации.

Коллизия – это когда разным значениям ключей таблицы хеш-функция генерирует одинаковые адреса.

При прямой адресации нужно построить для каждого адреса таблицы Н связный список элементов, ключи которых отображаются на этот адрес.

В открытой адресации хэш-списков нет, все записи хранятся в самой хэш-таблице, каждая ячейка содержит либо значение динамического множества, либо NULL.

Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время O(1).

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

Эффективность операций в хеш - таблице

Алгоритмы чтения или модификации, вставки и удаления элементов зависят от структуры хеш-таблицы. Если используется хеш-таблица с цепочками коллизий, то алгоритмы поиска, вставки и удаления элемента действуют по однотипной схеме:

·        хеширование ключа элемента и вычисление индекса заголовка списка в массиве цепочек коллизий,

·        поиск в списке элемента с заданным ключом,

·        выполнение операции над элементом.

Трудоёмкость операций зависит от средней длины списков, которую можно вычислить как α = n/m, где n – число занесенных в таблицу элементов, m – размер хеш-таблицы. С учётом первоначального хеширования ключа перед просмотром списка оценку трудоёмкости можно записать, как O(1+α/2). Величина α учитывает фактор заполнения таблицы и называется коэффициентом заполнения таблицы. Трудоёмкость операций в хеш-таблице зависит не от числа элементов n, содержащихся в ней, а от коэффициента заполнения α.

Для открытой адресации α ≤ 1. Анализ трудоёмкости операций для хеш-таблиц с открытой адресацией более сложен, чем для хеш-таблиц с цепочками коллизий. Помимо коэффициента α трудоёмкость операции зависит от её алгоритма, метода зондирования, вероятности промахов операций.