пример

key = {1,3,56,4,32,40,23,7,41,13,6,7}

hashTableSize = 5.

h(key)={1,3,1,4, 2, 0, 3, 2, 1, 3, 1, 2}

ограничения

►hashTableSize ≠2^p и далеко от него ►hashTableSize - простое

Мультипликативный метод

1)hashTableSize =2p

2)0≤A≤1

золотое сечение

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

h(key) hashTableS ize(key A mod1)

пример

key = 123456; hashTableSize =10000; A =0.618,

h(key)=[10000*(123456*0,61803…mod1)]= =[10000*(76500,0041151..mod1)]= =[10000*0,0041151…]=[41,151…]= =41.

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

//для строк переменной длины

typedef unsigned char HashIndexType;

HashIndexType Hash(char *str) {

HashIndexType h = 0; while (*str) h += *str++; return h;

}

Универсальное

хэширование

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

вероятность конфликта = 1/hashTableSize

мультипликативное

хэширование

A – послед случ. чисел

h(key) hashTableS ize(key A mod1)

►в универсальную хэш-функцию.

// грубый генератор

typedef int HashIndexType;

HashIndexType Hash (char *v, int HashTableSize)

{

int h, a = 31415, b = 27183;

for(h = 0; *v != 0; v++, a = a*b %

(HashTableSize -l))

h= (a*h + *v) % HashTableSize;

return (h < 0) ? (h + HashTableSize) : h;

}

Адресация

►прямая ►открытая

Прямая адресация

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

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

►ключи

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

► для хранения множества - массив T[0..m-1] таблица прямой адресации (direct-adress table)

Реализация операций ►поиск - return T[k];

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

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

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