Хэш-таблицы

Хэш-таблицы Лекция 8 АТД «Словарь» (dictionary) ▪ Словарь (ассоциативный массив, associative array, map, dictionary) – структура данных (контейнер) для хранения пар вида «ключ – значение» (key – value) ▪ Реализации словарей отличаются вычислительной сложностью операций добавления (Add), поиска (Lookup) и удаления элементов (Delete) ▪ Наибольшее распространение получили следующие реализации: 1. 2. 3. 4. 5. Деревья поиска (search trees) Хэш-таблицы (hash tables) Списки с пропусками Связные списки Массивы 2 Хэш-таблицы (Hash tables) ▪ Хэш-таблица (hash table) – структура данных для хранения пар «ключ – значение» ▪ Доступ к элементам осуществляется по ключу (key) ▪ Ключи могут быть строками, числами, указателями, … ▪ Хэш-таблицы позволяют в среднем за время О(1) выполнять добавление, поиск и удаление элементов 3 Основная идея ▪ Чем хороши статические массивы int v[100]? ▪ Быстрый доступ (𝑂(1)) к элементу массива по его ключу (индексу): v[17] = 45 ▪ Ограничение – целочисленные ключи (индексы) 4 Основная идея ▪ Чем хороши статические массивы int v[100]? ▪ Быстрый доступ (𝑂(1)) к элементу массива по его ключу (индексу): v[17] = 45 ▪ Ограничение – целочисленные ключи (индексы) ▪ Можно ли как-то использовать типы float,double, строки (char[]) в качестве индексов в массиве? ▪ Пример: массив анкет пользователей Twitter (словарь), ключ – login, значение – анкета (профиль с данными пользователя) ▪ Массив структур: struct twitter_user users[MAX_USERS]; 5 Хэш-таблицы (Hash tables) Ключ (Key) “Антилопа Гну” Хэш-функция (Hash function) Хэш-таблица (Hash table) hash(key) -> int h–1 … ▪ Хэш-ф ункция отображает (преобразует) ключ (key) в номер элемента (index) массива (в целое число от 0 до h – 1) ▪ Время вычисления хэш-функции зависит от длины ключа и не зависит от количества элементов в массиве index Value: 160 2 1 ▪ Ячейки массива называются buckets, slots 6 Хэш-таблицы (Hash tables) ▪ На практике, обычно известна информация о диапазоне значений ключей ▪ На основе этого выбирается размер h хэш-таблицы и выбирается хэш-функция ▪ Коэф ф ициент  заполнения хэш-таблицы (load factor, fill factor) отношение числа n хранимых элементов в хэш-таблице к размеру h массива (среднее число элементов на одну ячейку) 𝑛 α= ℎ h–1 Value: 160 2 1 ▪ Пример: h = 128, в хэш-таблицу добавили 50 элементов, тогда  = 50 / 128  0.39 ▪ От этого коэффициента зависит среднее время выполнения операций добавления, поиска и удаления элементов 7 Хэш-функции (Hash functions) ▪ Хэш-ф ункция (Hash function) – это функция, преобразующая значения ключа (например: строки, числа, файла) в целое число ▪ Значение, возвращаемое хэш-функцией, называется хэш-кодом (hash code), контрольной суммой (hash sum) или хэшем (hash) #define HASH_MUL 31 #define HASH_SIZE 128 Thash = O(|s|) // Хэш-функция для строк unsigned int hash(char *s) { unsigned int h = 0; char *p; } for (p = s; *p != '\0'; p++) h = h * HASH_MUL + (unsigned int)*p; return h % HASH_SIZE; 8 Хэш-функции (Hash functions) ▪ Хэш-ф ункция (Hash function) – это функция, преобразующая значения ключа (например: строки, числа, файла) в целое число ▪ Значение, возвращаемое хэш-функцией, называется хэш-кодом (hash code), контрольной суммой (hash sum) или хэшем (hash) #define HASH_MUL 31 #define HASH_SIZE 128 i v a n o v 105 118 97 110 111 118 int main() { unsigned int h = hash(“ivanov”); } 9 Хэш-функции (Hash functions) #define HASH_MUL 31 #define HASH_SIZE 128 unsigned int hash(char *s) { unsigned int h = 0; char *p; } i v a n o v 105 118 97 110 111 118 for (p = s; *p != '\0'; p++) h = h * HASH_MUL + (unsigned int)*p; return h % HASH_SIZE; h = 0 * HASH_MUL + 105 h = 105 * HASH_MUL + 118 h = 3373 * HASH_MUL + 97 h = 104660 * HASH_MUL + 110 h = 3244570 * HASH_MUL + 111 h = 100581781 * HASH_MUL + 118 return 3118035329 % HASH_SIZE // hash(“ivanov”) = 1 10 Понятие коллизии (Collision) ▪ Коллизия (Collision) – это совпадение значений хэш-функции для двух разных ключей hash(“Волк”) = 2 Keys Жираф Слон Муха Волк hash(“Жираф”) = 2 Hash function Hashes 127 ... 05 04 03 02 01 00 Collision! Существуют хэш-функции без коллизий – совершенные хэш-ф ункции (perfect hash function) 11 Разрешение коллизий (Collision resolution) Метод цепочек (Chaining) – закрытая адресация Элементы с одинаковым значением хэш-функции объединяются в связный список. Указатель на список хранится в соответствующей ячейке хэш-таблицы ▪ При коллизии элемент добавляется в начало списка ▪ Поиск и удаление элемента требуют просмотра всего списка Keys Жираф Слон Муха Волк Hash function Hashes 127 ... 05 04 03 02 01 00 Муха NULL Слон NULL Жираф Волк NULL 12 Разрешение коллизий (Collision resolution) Открытая адресация (Open addressing) В каждой ячейке хэш-таблицы хранится не указатель на связный список, а один элемент (ключ, значение) Если ячейка с индексом hash(key) занята, то осуществляется поиск свободной ячейки в следующих позициях таблицы Hash Элемент Линейное хэширование (linear probing) – проверяются позиции: 1 hash(key) + 1, hash(key) + 2, …, (hash(key) + i) mod h, … 2 3 4 5 Если свободных ячеек нет, то таблица заполнена Пример: ▪ hash(D) = 3, но ячейка с индексом 3 занята ▪ Просматриваем ячейки: 4 – занята, 5 – свободна B A C D 6 7 13 Требования к хэш-функциям ▪ Быстрое вычисление хэш-кода по значению ключа ▪ Сложность вычисления хэш-кода не должна зависеть от количества n элементов в хэш-таблице ▪ Детерминированность – для заданного значения ключа хэш-функция всегда должна возвращать одно и то же значение unsigned int hash(char *s) { unsigned int h = 0; char *p; } for (p = s; *p != '\0'; p++) h = h * HASH_MUL + (unsigned int)*p; return h % HASH_SIZE; 14 Требования к хэш-функциям ▪ Равномерность (uniform distribution) – хэш-функция должна равномерно заполнять индексы массива возвращаемыми номерами ▪ Желательно, чтобы все хэш-коды формировались с одинаковой равномерной распределенной вероятностью Hash Элемент Неравномерное C, F, G распределение A 1 D 2 C 3 G 4 B, E B 5 F E 6 A, D, H H 7 15 Требования к хэш-функциям ▪ Равномерность (uniform distribution) – хэш-функция должна равномерно заполнять индексы массива возвращаемыми номерами ▪ Желательно, чтобы все хэш-коды формировались с одинаковой равномерной распределенной вероятностью Равномерное Hash Элемент распределение C A D C G B F H E 1 A 2 3 4 5 D H B G 6 7 E F 16 Эффективность хэш-таблиц ▪ Хэш-таблица требует предварительной инициализации ячеек значениями NULL – трудоемкость 𝑂(ℎ) Операция Вычислительная сложность в среднем случае Вычислительная сложность в худшем случае Add(key, value) 𝑂(1) 𝑂(1) Lookup(key) 𝑂(1 + 𝑛/ℎ) 𝑂(𝑛) Delete(key) 𝑂(1 + 𝑛/ℎ) 𝑂(𝑛) Min() 𝑂(𝑛 + ℎ) 𝑂(𝑛 + ℎ) Max() 𝑂(𝑛 + ℎ) 𝑂(𝑛 + ℎ) 17 Пример хэш-функции для строк ▪ Используются только поразрядные операции (для эффективности) unsigned int ELFHash(char *key, unsigned int mod) { unsigned int h = 0, g; while (*key) { h = (h << 4) + *key++; g = h & 0xf0000000L; if (g) h ^= g >> 24; h &= ~g; } return h % mod; } 18 Jenkins hash functions uint32_t jenkins_hash(char *key, size_t len) { uint32_t hash, i; for (hash = i = 0; i < len; ++i) { hash += key[i]; hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return hash; } 19 Пример хэш-функции для чисел ▪ Ключи – размер файла (int) ▪ Значение, хранимое в словаре – название файла ▪ Требуется разработать хэш-функцию hash(filesize)  [0..1023] function hash(int filesize) return filesize % 1024 end function 20 Пример хэш-функции для строк 𝐿−1 hash 𝑠 = ෍ ℎ𝐿−(𝑖+1) ∙ 𝑠 𝑖 = = 𝑠[0]ℎ𝐿−1 + 𝑠[1]ℎ 𝑖=0 𝐿−2 + ⋯+ 𝑠 𝐿 − 2 ℎ + 𝑠 𝐿 − 1 , где s – ключ (строка), L – длина строки, s[i] – код символа i 21 Хэш-таблицы (Hash table) ▪ Длину ℎ хэш-таблицы выбирают как простое число ▪ Для такой таблицы модульная хэш-функция дает равномерное распределение значений ключей 𝒉𝒂𝒔𝒉(𝑘𝑒𝑦) = 𝑘𝑒𝑦 % ℎ 22 Хэш-таблицы vs. Бинарное дерево поиска ▪ Эффективность реализации словаря хэш-таблицей (метод цепочек) и бинарным деревом поиска ▪ Ключ – это строка из m символов ▪ Оценка сложности для худшего случая (worst case) Операция Hash table (unordered map) Binary search tree (ordered map) Add(key, value) 𝑂(𝑚) 𝑂(𝑛𝑚) Lookup(key) 𝑂(𝑚 + 𝑛𝑚) 𝑂(𝑛𝑚) Delete(key) 𝑂(𝑚 + 𝑛𝑚) 𝑂(𝑛𝑚) Min() 𝑂(𝑚(𝑛 + ℎ)) 𝑂(𝑛) Max() 𝑂(𝑚(𝑛 + ℎ)) 𝑂(𝑛) 23 Хэш-таблицы vs. Бинарное дерево поиска ▪ Эффективность реализации словаря хэш-таблицей (метод цепочек) и бинарным деревом поиска ▪ Ключ – это строка из m символов ▪ Оценка сложности для среднего случая (average case) Операция Hash table (unordered map) Binary search tree (ordered map) Add(key, value) 𝑂(𝑚) 𝑂(𝑚𝑙𝑜𝑔𝑛) Lookup(key) 𝑂(𝑚 + 𝑚𝑛/ℎ) 𝑂(𝑚𝑙𝑜𝑔𝑛) Delete(key) 𝑂(𝑚 + 𝑚𝑛/ℎ) 𝑂(𝑚𝑙𝑜𝑔𝑛) Min() 𝑂(𝑚(𝑛 + ℎ)) 𝑂(𝑙𝑜𝑔𝑛) Max() 𝑂(𝑚(𝑛 + ℎ)) 𝑂(𝑙𝑜𝑔𝑛) 24 Реализация хэш-таблицы #include #include #include #define HASHTAB_SIZE 71 #define HASHTAB_MUL 31 struct listnode { char *key; int value; }; struct listnode *next; struct listnode *hashtab[HASHTAB_SIZE]; 25 Хэш-функция unsigned int hashtab_hash(char *key) { unsigned int h = 0; char *p; } for (p = key; *p != '\0'; p++) { h = h * HASHTAB_MUL + (unsigned int)*p; } return h % HASHTAB_SIZE; THash = O(|key|) 26 Инициализация хэш-таблицы void hashtab_init(struct listnode **hashtab) { int i; } for (i = 0; i < HASHTAB_SIZE; i++) { hashtab[i] = NULL; } TInit = O(h) 27 Добавление элемента в хэш-таблицу void hashtab_add(struct listnode **hashtab, char *key, int value) { struct listnode *node; } int index = hashtab_hash(key); // Вставка в начало списка node = malloc(sizeof(*node)); if (node != NULL) { node->key = strdup(key); node->value = value; node->next = NULL; hashtab[index] = node; } TAdd = THash + O(1) = O(1) 28 Поиск элемента struct listnode *hashtab_lookup(struct listnode **hashtab, char *key) { int index; struct listnode *node; } index = hashtab_hash(key); for (node = hashtab[index]; node != NULL; node = node->next) { if (strcmp(node->key, key) == 0) return node; } return NULL; TLookup = THash + O(n) = O(n) 29 Поиск элемента int main() { struct listnode *node; hashtab_init(hashtab); hashtab_add(hashtab, “Tiger”, 190); hashtab_add(hashtab, “Elefant”, 2300); hashtab_add(hashtab, “Wolf”, 60); node = hashtab_lookup(hashtab, “Elefant”); printf("Node: %s, %d\n", node->key, node->value); } return 0; 30 Удаление элемента void hashtab_delete(struct listnode **hashtab, char *key) { int index; struct listnode *p, *prev = NULL; } index = hashtab_hash(key); for (p = hashtab[index]; p != NULL; p = p->next) { if (strcmp(p->key, key) == 0) { if (prev == NULL hashtab[index] = p->next; else prev->next = p->next; free(p); return; } prev = p; TDelete = THash + O(n) = O(n) } 31 Удаление элемента int main(){ struct listnode *node; /* ... */ } hashtab_delete(hashtab, “Elefant”); node = hashtab_lookup(hashtab, “Elefant”); if (node != NULL) { printf("Node: %s, %d\n", node->key, node->value); } else { printf("Key ‘Elefant’ not found\n"); } return 0; 32 Литература ▪ [DSABook, Глава 11] ▪ Седжвик Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. – К.: ДиаСофт, 2001. – 688 с. [С. 575] о хэш-функциях для вещественных чисел ▪ Керниган Б.У., Пайк Р. Практика программирования. – М.: Вильямс, 2004. ▪ “Глава 11. Хеш-таблицы” [CLRS, С. 282] 33