Skip to content

Latest commit

 

History

History
232 lines (157 loc) · 10.2 KB

hash_tables.md

File metadata and controls

232 lines (157 loc) · 10.2 KB

Хеш-таблицы

Содержание

Хеш-функция

Если же все-таки БСТ нас не устроили, мы хотим чего-то быстрее, а ограничений по памяти нет, то мы можем воспользоваться хешом.

Что такое хеш? Давайте возьмем обычный массив/вектор размера m, в котором мы можем индексировать за O(1). Хорошо, но вдруг мы захотим хранить в нем строку или другой объект в нем.

Мы можем сделать такую функцию h(x), которая из любого объекта сделает нам соответствующее ему число, которое мы сможем использовать как индекс в нашем векторе.

Начнем с хеширования обычных чисел и возьмем хеш-функцию h(x) = x % m. Очевидно, что область значений функции должна быть в интервале [0; m).

Введем на нашей хеш-таблице 3 операции - удаление delete, добавление insert, поиск find

Приведем пример с m = 5:

insert 3
insert 0
insert 2
delete 0
Индекс Объект
0
1
2 2
3 3
4

Теперь хотим вставить 8 - но не можем! Клетка уже занята, и произошла т.н. коллизия хеш-функции - для двух объектов хеш-функция равна. Чтобы устранять коллизию, существует множество способов, описанные ниже.

Пока что зададимся другим вопросом - как хешировать строку? Вспомним, что строка a - это упорядоченный набор целых символов (a1, a2, ..., an). Можем сделать из нее полиномиальный хеш:

h(a) = (a1 + a2 * k + a3 * k^2 + ... + an * k^(n - 1)) % m, где k - какая-либо константа

Очевидно, что хеш строки можно вычислить за n - длину строки. Пример реализации:

fn hash1(a: &String, m: usize) -> i64 {
    let mut h = 0i64;
    for i in a.chars() {
        h = (h * 3543523 + (i as i64)) % (m as i64);
    }
    h
}

По такой аналогии мы можем вычислять хеш tuple и пары из чисел.

Помимо хеш-функции h(x) = x % m лучше использовать более рандомные и более распределенные хеш-функции, например, основанные на умножению: h(x) = m * (k * x / w), где k - какая-либо константа, а w - максимальное значение числа x (чаще всего 2^32)

В целом в выборе хеш-функции вы вольны делать, что хотите, но хорошая хеш-функция должна соблюдать 2 требования:

  • быть быстро вычисляемой
  • иметь минимум коллизий

Лично мой выбор - это такая хеш-функция:

fn hash_f(mut a: i64) -> i64 {
    a = a % (1 << 31);
    let m = 2654435769i64 * (a * a - a) ^ 314299671481i64 / 4294967296i64;
    if m > 0 { m } else { -m }
}

В конце концов для решения коллизии существуют различные методы решения коллизий, например:

Метод списков

Давайте хранить вместо числа вектор и складывать в него все объекты имеющий равный хеш.

Тогда наша нереализованная таблица выше будет выглядеть так:

Индекс Объект
0 []
1 []
2 [2]
3 [3, 8]
4 []

Поиск

Поиск происходит элементарно - вычисляем хеш и, используя линейный поиск, проходимся по вектору в поиске исходного элемента

Если наша хеш-функция хорошая, то мы можем говорить об амортизированной сложности O(1)

Добавление

Добавление происходит элементарно - вычисляем хеш, добавляем в вектор элемент, расположенный по индексу хеша

Все это можно делать за O(1) (допустим, что вектор расширяется за амортизированное O(1)). Если перед этим делать поиск, то O(1) превращается в амортизированное O(1)

Удаление

Удаление происходит элементарно - вычисляем хеш и удаляем элемент из вектора. Так как порядок в нашем векторе не важен, мы можем свапнуть этот элемент с последним за O(1) и уменьшить размер вектора на 1 за O(1)

Опять же этот элемент нужно найти за амортизированное O(1)

Реализация

Rust - list_method_hashing.rs

Операция Сложность в среднем Сложность в худшем
Поиск O(1) O(n)
Добавление O(1) O(n)
Удаление O(1) O(n)

Но! Следует помнить, что если хеш-функция плохая, то все эти O(1) превращаются в O(n)

Также, пишут, что метод списков работает за O(1 + α) - где α - коэффициент заполненности таблицы

У метода списков есть достоинство - мы не ограничены размером хеш-таблицы

Открытая адресация

Теперь давайте вместо списков будем смотреть в следующую ячейку и записывать туда, если она свободна

Наша таблица выше будет выглядеть так:

Индекс Объект
0
1
2 2
3 3
4 8

Но возникает проблема - удаляя 3 из нашей таблицы, мы впоследствии не сможем найти 8,

Индекс Объект
0
1
2 2
3
4 8

так как при переходе по хешу мы встретим пустую ячейку, а программа будет говорить, что 8 нет. Для решения этого мы можем реализовать метку deleted, означающую, что элемент в этой ячейке был удален.

Индекс Объект
0
1
2 2
3 deleted
4 8

Поиск

Поиск происходит так - вычисляем хеш, переходим в ячейку по этому индекс, сравниваем элементы - если они не равны, идем вниз, пока не найдем исходный или пока не найдем свободную ячейку

Если наша хеш-функция хорошая, то мы можем говорить об амортизированной сложности O(1)

Добавление

Добавление происходит аналогично поиску - вычисляем хеш, идем вниз до тех пор, пока не найдем пустую ячейку или deleted

Удаление

Удаление происходит так - ищем алгоритмом поиска элемент и в ячейке вместо него ставим deleted

Займет это все O(1) в зависимости от хеш-функции

Реализация

Rust - open_address_hashing.rs

Удобно делать хеш-таблицу с открытой адресацией в Rust; создадим enum, показывающий состояние ячейки:

enum MyOption<T> {
    Some(T),         // что-то лежит
    Deleted,         // удален
    None,            // ничего не лежит
}

и будем хранить его в векторе нашей хешмапы:

struct HashMap {
    table_size: usize,
    table: Vec<MyOption<(i64, i64)>>,
    size: usize
}
Операция Сложность в среднем Сложность в худшем
Поиск O(1) O(n)
Добавление O(1) O(n)
Удаление O(1) O(n)

Метод кукушки

TODO

Хеш множества

TODO