Хеш-таблицы

Содержание

Слайд 2

АТД «Словарь» (dictionary)

Словарь (ассоциативный массив, associative array, map, dictionary) – структура данных

АТД «Словарь» (dictionary) Словарь (ассоциативный массив, associative array, map, dictionary) – структура
(контейнер) для хранения пар вида «ключ – значение» (key – value)
Реализации словарей отличаются вычислительной сложностью операций добавления (Add), поиска (Lookup) и удаления элементов (Delete)
Наибольшее распространение получили следующие реализации:
Деревья поиска (search trees)
Хэш-таблицы (hash tables)
Списки с пропусками
Связные списки
Массивы

Слайд 3

Хеш-таблицы (Hash tables)

Хеш-таблица (hash table) – структура данных для хранения пар «ключ

Хеш-таблицы (Hash tables) Хеш-таблица (hash table) – структура данных для хранения пар
– значение»
Доступ к элементам осуществляется по ключу (key)
Ключи могут быть строками, числами, указателями, …
Хеш-таблицы позволяют в среднем за время О(1) выполнять добавление, поиски и удаление элементов

Слайд 4

Основная идея

Чем хороши статические массивы int v[100]?
Быстрый доступ O(1) к элементу массива

Основная идея Чем хороши статические массивы int v[100]? Быстрый доступ O(1) к
по его ключу (индексу): v[17] = 45
Ограничение – ключи (индексы) это целые числа

Слайд 5

Основная идея

Чем хороши статические массивы int v[100]?
Быстрый доступ O(1) к элементу массива

Основная идея Чем хороши статические массивы int v[100]? Быстрый доступ O(1) к
по его ключу (индексу): v[17] = 45
Ограничение – ключи (индексы) это целые числа
Можно ли как-то использовать типы float, double, строки (char []) в качестве индексов в массиве?
Пример: массив анкет пользователей Twitter (словарь), ключ – login, значение – анкета (профиль с данными пользователя)
Массив структур: struct twitter_user users[MAX_USERS];

Слайд 6

Хеш-таблицы (Hash tables)

Ключ (Key)

“Антилопа Гну”

Хеш-таблица (Hash table)

Хеш-функция (Hash function)

hash(key) -> int

0

1

2


h – 1

Хеш-функция

Хеш-таблицы (Hash tables) Ключ (Key) “Антилопа Гну” Хеш-таблица (Hash table) Хеш-функция (Hash
– отображает (преобразует) ключ (key) в номер элемента (index) массива (в целое число от 0 до h – 1)
Время вычисления хеш-функции зависит от длины ключа и не зависит от количества элементов в массиве
Ячейки массива называются buckets, slots

index

Слайд 7

Хеш-таблицы (Hash tables)

Хеш-таблица (Hash table)

0

1

2


h – 1

 

Хеш-таблицы (Hash tables) Хеш-таблица (Hash table) 0 1 2 … h – 1

Слайд 8

Хеш-функции (Hash function)

Хеш-функция (Hash function) – это функция преобразующая значения ключа (например:

Хеш-функции (Hash function) Хеш-функция (Hash function) – это функция преобразующая значения ключа
строки, числа, файла) в целое число
Значение возвращаемое хеш-функцией называется хеш-кодом (hash code), контрольной суммой (hash sum) или хешем (hash)

#define HASH_MUL 31
#define HASH_SIZE 128
// Хеш-функция для строк [KP, “Practice of Programming”]
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;
}

Thash = O(|s|)

Слайд 9

Хеш-функции (Hash function)

Хеш-функция (Hash function) – это функция преобразующая значения ключа (например:

Хеш-функции (Hash function) Хеш-функция (Hash function) – это функция преобразующая значения ключа
строки, числа, файла) в целое число
Значение возвращаемое хеш-функцией называется хеш-кодом (hash code), контрольной суммой (hash sum) или хешем (hash)

#define HASH_MUL 31
#define HASH_SIZE 128
int main()
{
unsigned int h = hash(“ivanov”);
}

Слайд 10

Хеш-функции (Hash function)

#define HASH_MUL 31
#define HASH_SIZE 128
unsigned int hash(char *s) {
unsigned

Хеш-функции (Hash function) #define HASH_MUL 31 #define HASH_SIZE 128 unsigned int hash(char
int h = 0;
char *p;
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

Слайд 11

Понятие коллизии (Collision)

Коллизия (Collision) – это совпадение значений хеш-функции для двух разных

Понятие коллизии (Collision) Коллизия (Collision) – это совпадение значений хеш-функции для двух
ключей

Keys

Hashes

Hash function

Жираф

Слон

Муха Цеце

Волк

Collision!

hash(“Волк”) = 2 hash(“Жираф”) = 2

Существуют хеш-функции без коллизий – совершенные хеш-функции (perfect hash function)

Слайд 12

Разрешение коллизий (Collision resolution)

Метод цепочек (Chaining) – закрытая адресация
Элементы с одинаковым значением

Разрешение коллизий (Collision resolution) Метод цепочек (Chaining) – закрытая адресация Элементы с
хеш-функции объединяются в связный список. Указатель на список хранится в советующей ячейке хеш-таблицы.
При коллизии элемент добавляется в начало списка.
Поиск и удаление элемента требуют просмотра всего списка.

Keys

Hashes

Hash function

Жираф

Слон

Муха Цеце

Волк

Муха Цеце

NULL

Слон

NULL

Жираф

Волк

NULL

Слайд 13

Разрешение коллизий (Collision resolution)

Открытая адресация (Open addressing)
В каждой ячейке хеш-таблицы хранится

Разрешение коллизий (Collision resolution) Открытая адресация (Open addressing) В каждой ячейке хеш-таблицы
не указатель на связный список, а один элемент (ключ, значение)
Если ячейка с индексом hash(key) занята, то осуществляется поиск свободной ячейки в следующих позициях таблицы

Линейное хеширование (linear probing) – проверяются позиции:
hash(key) + 1, hash(key) + 2, …, (hash(key) + i) mod h, …
Если свободных ячеек нет, то таблица заполнена

Пример:
hash(D) = 3, но ячейка с индексом 3 занята
Присматриваем ячейки: 4 – занята, 5 – свободна

Слайд 14

Требования к хеш-функциям

Быстрое вычисление хэш-кода по значению ключа
Сложность вычисления хэш-кода не должна

Требования к хеш-функциям Быстрое вычисление хэш-кода по значению ключа Сложность вычисления хэш-кода
зависеть от количества 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;
}

Слайд 15

Требования к хеш-функциям

Равномерность (uniform distribution) – хеш-функция должна равномерно заполнять индексы массива

Требования к хеш-функциям Равномерность (uniform distribution) – хеш-функция должна равномерно заполнять индексы
возвращаемыми номерами
Желательно, чтобы все хэш-коды формировались с одинаковой равномерной распределенной вероятностью

A

B

C

D

E

F

G

H

Неравномерное распределение

Слайд 16

Требования к хеш-функциям

Равномерность (uniform distribution) – хеш-функция должна равномерно заполнять индексы массива

Требования к хеш-функциям Равномерность (uniform distribution) – хеш-функция должна равномерно заполнять индексы
возвращаемыми номерами
Желательно, чтобы все хэш-коды формировались с одинаковой равномерной распределенной вероятностью

A

B

C

D

E

F

G

H

Равномерное распределение

Слайд 17

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

Хеш-таблица требует предварительной инициализации ячеек значениями NULL – трудоемкость O(h)

Эффективность хеш-таблиц Хеш-таблица требует предварительной инициализации ячеек значениями NULL – трудоемкость O(h)

Слайд 18

Пример хэш-функции для строк

unsigned int ELFHash(char *key, unsigned int mod)
{
unsigned

Пример хэш-функции для строк unsigned int ELFHash(char *key, unsigned int mod) {
int h = 0, g;
while (*key) {
h = (h << 4) + *key++;
g = h & 0xf0000000L;
if (g)
h ^= g >> 24;
h &= ~g;
}
return h % mod;
}

Используются только поразрядные операции (для эффективности)

Слайд 19

Jenkins hash functions

uint32_t jenkins_hash(char *key, size_t len)
{
uint32_t hash, i;

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;
}

Слайд 20

Пример хэш-функции для чисел

Ключи – размер файла (int)
Значение, хранимое в словаре –

Пример хэш-функции для чисел Ключи – размер файла (int) Значение, хранимое в
название файла
Требуется разработать хеш-функцию
hash(filesize) → [0..1023]

function hash(int filesize)
return filesize % 1024
end function

Слайд 21

Пример хэш-функции для строк

 

Пример хэш-функции для строк

Слайд 22

Хеш-таблицы (Hash table)

Длину h хеш-таблицы выбирают как простое число
Для такой таблицы модульная

Хеш-таблицы (Hash table) Длину h хеш-таблицы выбирают как простое число Для такой
хеш-функция дает равномерное распределение значений ключей
hash(key) = key % h

Слайд 23

Хеш-таблицы vs. Бинарное дерево поиска

Эффективность реализации словаря хеш-таблицей (метод цепочек) и бинарным

Хеш-таблицы vs. Бинарное дерево поиска Эффективность реализации словаря хеш-таблицей (метод цепочек) и
деревом поиска
Ключ – это строка из m символов
Оценка сложности для худшего случая (worst case)

Слайд 24

Хеш-таблицы vs. Бинарное дерево поиска

Эффективность реализации словаря хеш-таблицей (метод цепочек) и бинарным

Хеш-таблицы vs. Бинарное дерево поиска Эффективность реализации словаря хеш-таблицей (метод цепочек) и
деревом поиска
Ключ – это строка из m символов
Оценка сложности для среднего случая (average case)

Слайд 25

Реализация хеш-таблицы

#include
#include
#include
#define HASHTAB_SIZE 71
#define HASHTAB_MUL 31
struct listnode {
char

Реализация хеш-таблицы #include #include #include #define HASHTAB_SIZE 71 #define HASHTAB_MUL 31 struct
*key;
int value;
struct listnode *next;
};
struct listnode *hashtab[HASHTAB_SIZE];

Слайд 26

Хеш-функция

unsigned int hashtab_hash(char *key)
{
unsigned int h = 0;
char *p;
for (p

Хеш-функция unsigned int hashtab_hash(char *key) { unsigned int h = 0; char
= key; *p != '\0'; p++) {
h = h * HASHTAB_MUL + (unsigned int)*p;
}
return h % HASHTAB_SIZE;
}

THash = O(|key|)

Слайд 27

Инициализация хеш-таблицы

void hashtab_init(struct listnode **hashtab)
{
int i;
for (i = 0; i <

Инициализация хеш-таблицы void hashtab_init(struct listnode **hashtab) { int i; for (i =
HASHTAB_SIZE; i++) {
hashtab[i] = NULL;
}
}

TInit = O(h)

Слайд 28

Добавление элемента в хеш-таблицу

void hashtab_add(struct listnode **hashtab,
char *key, int value)
{
struct

Добавление элемента в хеш-таблицу void hashtab_add(struct listnode **hashtab, char *key, int value)
listnode *node;
int index = hashtab_hash(key);
// Вставка в начало списка
node = malloc(sizeof(*node));
if (node != NULL) {
node->key = key;
node->value = value;
node->next = hashtab[index];
hashtab[index] = node;
}
}

TAdd = THash + O(1) = O(1)

Слайд 29

Поиск элемента

struct listnode *hashtab_lookup(
struct listnode **hashtab,
char *key)
{
int index;

Поиск элемента struct listnode *hashtab_lookup( struct listnode **hashtab, char *key) { int
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)

Слайд 30

Поиск элемента

int main()
{
struct listnode *node;
hashtab_init(hashtab);
hashtab_add(hashtab, "Tigr", 190);
hashtab_add(hashtab, "Slon", 2300);

Поиск элемента int main() { struct listnode *node; hashtab_init(hashtab); hashtab_add(hashtab, "Tigr", 190);
hashtab_add(hashtab, "Volk", 60);
node = hashtab_lookup(hashtab, "Slon");
printf("Node: %s, %d\n",
node->key, node->value);
return 0;
}

Слайд 31

Удаление элемента

void hashtab_delete(struct listnode **hashtab, char *key)
{
int index;
struct listnode *p,

Удаление элемента void hashtab_delete(struct listnode **hashtab, char *key) { int index; struct
*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)

Слайд 32

Удаление элемента

int main()
{
struct listnode *node;
/* ... */
hashtab_delete(hashtab, "Slon");
node = hashtab_lookup(hashtab,

Удаление элемента int main() { struct listnode *node; /* ... */ hashtab_delete(hashtab,
"Slon");
if (node != NULL) {
printf("Node: %s, %d\n",
node->key, node->value);
} else {
printf("Key 'Slon' not found\n");
}
return 0;
}