Хеш-таблиця
Щоб вставити в таблицю новий елемент, ми хешіруем ключ, щоб визначити список, в який його потрібно додати, потім вставляємо елемент в початок цього списку. Наприклад, щоб додати 11, ми ділимо 11 на 8 і отримуємо залишок 3. Таким чином, 11 слід розмістити в списку, на початок якого вказує hashTable [3]. Щоб знайти число, ми його хешіруем і проходимо за відповідним списком. Щоб видалити число, ми знаходимо його і видаляємо елемент списку, його містить.
При додаванні елементів в хеш-таблицю виділяються шматки динамічної пам'яті, які організовуються у вигляді пов'язаних списків, кожен з яких відповідає входу хеш-таблиці. Цей метод називається зв'язуванням .
Якщо хеш-функція розподіляє сукупність можливих ключів рівномірно по безлічі індексів, то хешування ефективно розбиває множину ключів. Найгірший випадок - коли всі ключі хешіруются в один індекс. При цьому ми працюємо з одним лінійним списком, який і змушені послідовно сканувати кожен раз, коли що-небудь робимо. Звідси видно, як важлива хороша хеш-функція. Тут ми розглянемо лише декілька з можливих підходів. При ілюстрації методів передбачається, що unsigned char розташовується в 8 бітах, unsigned short int - в 16, unsigned long int - в 32.
II. Розподіл ( розмір таблиці hashTableSize - просте число ). Цей метод використаний в останньому прикладі. Хешірующее значення hashValue , що змінюється від 0 до ( hashTableSize - 1 ), дорівнює залишку від ділення ключа на розмір хеш-таблиці. Ось як це може виглядати:
int HashIndexType; Hash (int Key) {Key% HashTableSize;
}
Для успіху цього методу дуже важливий вибір відповідного значення hashTableSize . Якщо, наприклад, hashTableSize дорівнює двом, то для парних ключів хеш-значення будуть парними, для непарних - непарними. Ясно, що це небажано - адже якщо всі ключі виявляться парними, вони потраплять в один елемент таблиці. Аналогічно, якщо всі ключі виявляться парними, то hashTableSize , рівне ступеню двох, попросту візьме частину бітів Key в якості індексу. Щоб отримати більш випадковий розподіл ключів, в якості hashTableSize потрібно брати просте число, не надто близьке до ступеня двох.
III. Мультиплікативний метод ( розмір таблиці hashTableSize є ступінь 2 n ). Значення key множиться на константу, потім від результату береться n біт. В якості такої константи Кнут рекомендує золотий перетин ( sqrt (5) - 1)/2=0.6180339887499. Нехай, наприклад, ми працюємо з таблицею з hashTableSize =32 (2 5) Декоративні елементи, хешування проводиться байтами (8 біт, unsigned char). Тоді необхідний множник: 2 8 * sqrt (5) - 1)/2=158.
IV. Далі, множачи 8-бітовий ключ на 158, будемо отримувати деякий 16-бітове число. Для таблиці довжиною 2 5 в якості хешірующего значення беремо 5 старших бітів молодшого слова, що містить такий твір. Ось як можна реалізувати цей метод:
/* 8-bit index */unsigned char HashIndexType; const HashIndexType K=158;
/* 16-bit index */
typedef unsigned short int HashIndexType; const HashIndexType K=40503;
/* 32-bit index */unsigned long int HashIndexType; const HashIndexType K=2654435769;
/* w=bitwidth (HashIndexType), size of table=2 ** m */const int S=w - m;
/* Перетворення типу прибирає старше слово, т. е
* зайві біти ліворуч, а зрушення прибирає зайве справа
*/HashValue=(HashIndexType) (K * Key) gt; gt; S;
Нехай, наприклад, розмір таблиці hashTableSize дорівнює 1024 (2 10). Тоді нам достатній 16-бітний індекс і величині зсуву S буде присвоєно значення 16 - 10=6. У результаті отримуємо:
typedef unsigned short int HashIndexType; Hash (int Key) {const HashIndexType K=40503; const int S=6; (HashIndexType) (K * Key) gt; gt; S;
}
V. Адитивний метод для рядків змінної довжини (розмір таблиці дорівнює 256). Для рядків змінної довжини цілком розумні результати дає додавання по модулю 256. У цьому випадку результат hashValue
