Сортування й пошук: Рецептурний довідник, страница 7

Для успіху цього методу дуже важливий вибір підходящого значення hashTableSize. Якщо, наприклад, hashTableSize рівняється двом, то для парних ключів хеш-значения будуть парними, для непарних – непарними. Ясно, що це небажано – адже якщо всі ключі виявляться парними, вони потраплять в один елемент таблиці. Аналогічно, якщо всі ключі виявляться парними, то hashTableSize, рівне ступеня двох, попросту візьме частина битов Key як індекс. Щоб одержати більше випадковий розподіл ключів, у якості hashTableSize потрібно брати просте число, не занадто близьке до ступеня двох.

• Мультиплікативний метод (розмір таблиці hashTableSize є ступінь 2ⁿ). Значення Key множиться на константу, потім від результату береться необхідне число битов. Як така константа Батіг^[1] рекомендує золотий перетин = 0.6180339887499. Нехай, наприклад, ми працюємо з байтами. Помноживши золотий перетин на 2⁸, одержуємо 158. Перемножимо 8-бітовий ключ і 158, одержуємо 16-бітове ціле. Для таблиці довжиною 2⁵ у якості хеширующего значення беремо 5 молодших битов молодшого слова, що містить такий добуток. От як можна реалізувати цей метод:

/* 8-bit index */

typedef unsigned char hashIndexType;

static const hashIndexType K = 158;

/* 16-bit index */

typedef unsigned short int hashIndexType;

static const hashIndexType K = 40503;

/* 32-bit index */

typedef unsigned long int hashIndexType;

static const hashIndexType K = 2654435769;

/* w=bitwidth(hashIndexType), size of table=2**m */

static const int S = w - m;

hashIndexType hashValue = (hashIndexType)(K * Key) >> S;

Нехай, наприклад, розмір таблиці hashTableSize дорівнює 1024 (2¹⁰). Тоді нам достатній 16-бітний індекс і S буде привласнене значення 16 – 10 = 6. У підсумку одержуємо:

typedef unsigned short int hashIndexType;

hashIndexType hash(int Key) {

    static const hashIndexType K = 40503;

    static const int S = 6;

    return (hashIndexType)(K * Key) >> S;

}

• Аддитивный метод для рядків змінної довжини (розмір таблиці дорівнює 256). Для рядків змінної довжини цілком розумні результати дає додавання по модулі 256. У цьому випадку результат hashValue укладений між 0 і 244.

typedef unsigned char hashIndexType;

hashIndexType hash(char *str) {

    hashIndexType h = 0;

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

    return h;

}

• Що виключає АБО для рядків змінної довжини (розмір таблиці дорівнює 256). Цей метод аналогічний аддитивному, але успішно розрізняє схожі слова й анаграми (аддитивный метод дасть одне значення для XY і YX). Метод, як легко догадатися, полягає в тім, що до елементів рядка послідовно застосовується операція “ щовиключає або”. У нижченаведеному алгоритмі додається випадковий компонент, щоб ще поліпшити результат.

typedef unsigned char hashIndexType;

unsigned char Rand8[256];

hashIndexType hash(char *str) {

    unsigned char h = 0;

    while (*str) h = Rand8[h ^ *str++];

    return h;

}

Тут Rand8 – таблиця з 256 восьмибитовых випадкових чисел. Їхній точний порядок не критичний. Коріння цього методу лежать у криптографії; він виявився цілком ефективним ^[4].

• Що виключає АБО для рядків змінної довжини (розмір таблиці £ 65536). Якщо ми хешируем рядок двічі, ми одержимо хеш-значение для таблиці будь-якої довжини до 65536. Коли рядок хешируется в другий раз, до першого символу додається 1. Одержувані два 8-бітових числа поєднуються в одне 16-бітове.

typedef unsigned short int hashIndexType;

unsigned char Rand8[256];

hashIndexType hash(char *str) {

    hashIndexType h;

    unsigned char h1, h2;

    if (*str == 0) return 0;

    h1 = *str; h2 = *str + 1;

    str++;

    while (*str) {

        h1 = Rand8[h1 ^ *str];

        h2 = Rand8[h2 ^ *str];

        str++;

    }

    /* h is in range 0..65535 */

    h = ((hashIndexType)h1 << 8)|(hashIndexType)h2;

    /* use division method to scale */

    return h % hashTableSize

}