Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Хэш-таблица - это структура данных, используемая для эффективного хранения и извлечения данных. Она обеспечивает быстрый поиск, вставку и удаление элементов, вычислительная сложность которых $O(1)$.

---

Где используется

1. Реализация множества
2. Реализация ассоциативного контейнера
3. В базах данных, в качестве индекса или системы хранения данных

---

Из чего состоит

Хэш-функция

Эта функция принимает входные данные и преобразует их в индекс в пределах заранее определённого диапазона. Цель хорошей хэш-функции - равномерно распределить входные данные по диапазону индексов, чтобы минимизировать коллизии. Это необходимо для поддержания вычислительной сложности операций $O(1)$.

Вычисление индексов

Если вам нужно сохранить или извлечь значение, ассоциированное с ключом, применяется хэш-функция к этому ключу для расчета индекса. Этот индекс определяет, где должно храниться значение или где его следует искать.

Массив корзин

Хэш-таблицы обычно используют массив «корзин» для хранения значений. Каждая корзина может содержать одно или несколько значений. Индекс, рассчитанный с помощью хэш-функции, указывает на конкретную корзину в массиве.

Разрешение коллизий

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

---

Механизмы обработки коллизий

Цепи (Chaining):

Каждая корзина представляет собой последовательный контейнер (в основном связный список), в котором хранятся элементы с одинаковым хэшем.

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

Все данные хранятся в массиве, каждая ячейка массива является корзиной. При возникновении коллизии в массиве ищется подходящая (свободная или хранящая совпадающий элемент) ячейка в предопределённой последовательности индексов, заданной линейным или квадратичным зондированием.

Линейное зондирование

При линейном зондировании, когда происходит коллизия, алгоритм ищет следующий доступный слот в линейной последовательности, увеличивая индекс на фиксированный шаг (обычно 1). Это продолжается до тех пор, пока не будет найден пустой слот или цикл не попадёт в ту же ячейку.

Например, при добавлении элемента $V$ для него был получен индекс $i$, по которому уже хранится значение. Тогда необходимо обратиться к ячейке с индексом $i + s$, если в ней находится элемент, то необходимо повторить операцию и обратиться к ячейке с индексом $i + 2s$, $i + 3s$ и т.д. Если подходящей позиции не будет найдено, то необходимо увеличить размер хэш-таблицы и повторить операцию.

Линейное зондирование может привести к кластеризации, когда последовательные элементы располагаются в непосредственной близости, что может привести к снижению производительности.

Квадратичное зондирование

При квадратичном зондировании последовательность зондирования определяется квадратичной функцией. При возникновении коллизии алгоритм увеличивает индекс на последовательно большие квадратичные шаги ($1^2, 2^2, 3^2, ...$), пока не будет найден пустой слот. Это помогает распределить элементы равномернее, чем линейное зондирование, но всё равно может привести к кластеризации.

Идеальное хэширование

В данном подходе коллизии разрешаются их отсутствием. Выбирается такая хэш-функция, которая будет возвращать для всех входных данных уникальный хэш. Данный способ стоит применять для известных входных данных, чтобы выбрать подходящую хэш-функцию и размер массива для хранения элементов.

---

Статическая и динамическая реализация

Статическая реализация хэш-таблицы предполагает, что размер массива индексов в ней не изменяется, поэтому при добавлении большого количества элементов, вычислительная сложность операций может повыситься до $O(n)$, где $n$ - количество элементов в структуре данных. Также, если весь массив корзин заполнится и в качестве алгоритма разрешения коллизий используется открытая адресация или идеальное хэширование, невозможно будет добавить новый элемент в структуру данных.

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

Также при увеличении размера структуры данных, необходимо создать новый массив корзин увеличенного размера и скопировать в него данные, хранящиеся в хэш-таблице данные, поэтому вычислительная сложность такой операции - $O(n)$.

Если увеличение размера таблицы возникает во время добавления элемента, то вычислительная сложность этой операции - $O(n)$. Но амортизированная вычислительная сложность операции добавления - $O(1)$ по аналогии с динамическим массивом.

---

Коэффициент загрузки

Коэффициент загрузки хэш-таблицы - это отношение количества хранимых элементов к количеству корзин. Высокий коэффициент загрузки может привести к увеличению числа коллизий, снижая производительность. Для поддержания эффективности размер хэш-таблиц можно изменить (увеличить количество корзин), когда коэффициент загрузки становится слишком высоким.

Идеальный коэффициент загрузки хэш-таблицы для увеличения её размера, независимо от алгоритма обработки коллизий, обычно составляет ~$0.7$. Это означает, что хэш-таблица заполнена примерно на $70\%$.

При таком коэффициенте загрузки хэш-таблица имеет оптимальный баланс между использованием оперативной памяти и сохранением производительности.

Данный коэффициент загрузки для увеличения размера структуры данных позволяет:

1. Минимизировать коллизии
2. Содержать достаточное количество пустых корзин во избежание чрезмерной кластеризации
3. Иметь оптимальную сложность по памяти

Важно отметить, что оптимальный коэффициент загрузки может изменяться в зависимости от таких факторов, как:

1. Выбранная хэш-функция
2. Способ распределения данных
3. Качество алгоритма разрешения коллизий
4. Множитель увеличения размера массива корзин

---

Выбор множителя увеличения размера массива корзин

При выборе множителя увеличения размера массива корзин следует руководствоваться требованиями к структуре данных: допустимой сложностью операций и максимальной пространственной сложностью.

Оптимальным коэффициентом расширения структуры данных является $2$ (аналогично динамическому массиву). Если необходимо минимизировать расход оперативной памяти, то следуем выбирать коэффициент $(1; 2]$. Если необходимо максимизировать производительность операций, то коэффициент следует сделать большим (оптимально $4$).

---

Псевдокод

добавить элемент(Элемент x):
    если необходимо расширить таблицу:
        расширить таблицу
    индекс = хэш_функция(x) - вычисление индекса корзины
    корзина = значение из таблице по индексу
    - проверка, что элемента в корзине не существует
    для элемента y в корзине:
        если x совпадает с y:
            завершить выполнение функции
    добавить элемент x в корзину
    увеличить size на 1

удалить элемент(Элемент x):
    индекс = хэш_функция(x)
    корзина = значение из таблице по индексу
    для элемента y в корзине:
        если x совпадает с y:
            удалить y из корзины
            уменьшить size на 1
            завершить выполнение функции

проверить содержание элемента(Элемент x) -> bool:
    индекс = хэш_функция(x)
    корзина = значение из таблицы по индексу
    для элемента y в корзине:
        если x совпадает с y:
            вернуть true
    вернуть false

---

Реализация на Python

Аннотация:
ChainingHashTable - хэш-таблица
__init__ - метод инициализации хэш-таблицы
default_capacity - емкость по умолчанию
max_load_factor - максимальный коэффициент загрузки
resize_factor - коэффициент изменения
_size - размер хэш-таблицы
_table - список, который хранит элементы хэш-таблицы
__len__ - метод возвращает число элементов в хэш-таблице
_hash - функция принимает элемент и возвращает его хэш-код
__contains__ - метод показывает находится ли указанное значение в хэш-таблице 
index - индекс элемента в таблице
__iter__ - метод возвращает итератор для хэш-таблице, который позволяет перебирать элементы в таблице
bucket - элемент из списка
item - элемент из bucket
__eq__ - метод показывает равна ли хэш-таблица указанному объекту или нет
load_factor - функция возвращает текущий коэффициент загрузки хэш-таблицы
add - функция добавляет указанное значение в хэш-таблицу
_resize - функция вызывается, когда коэффициент загрузки превышает максимальный коэффициент загрузки
remove - функция удаляет указанное значение из хэш-таблицы
new_size - новая емкость хэш-таблицы
new_table - новый список, который хранит элементы хэш-таблицы после изменений
---------------------------------------------------------------------------------
from collections import deque
from typing import Hashable

class ChainingHashTable:
    def __init__(self,
                 default_capacity=10,
                 max_load_factor=0.7,
                 resize_factor=2):
        self._size = 0
        self._table = [deque() for _ in range(default_capacity)]
        self._max_load_factor = max_load_factor
        self._resize_factor = resize_factor

    def __len__(self):
        return self._size

    def __contains__(self, value):
        index = self._hash(value)
        return value in self._table[index]

    def __iter__(self):
        for bucket in self._table:
            for item in bucket:
                yield item

    def __eq__(self, other):
        if len(self) != len(other):
            return False
        for item in self:
            if item not in other:
                return False
        return True

    def load_factor(self) -> float:
        return self._size / len(self._table)

    def add(self, value: Hashable):
        if self.load_factor() > self._max_load_factor:
            self._resize()
        index = self._hash(value)
        for i, item in enumerate(self._table[index]):
            if item == value:
                self._table[index][i] = value
                return
        self._table[index].append(value)
        self._size += 1

    def remove(self, value: Hashable) -> bool:
        index = self._hash(value)
        if value not in self._table[index]:
            return False
        self._table[index].remove(value)
        self._size -= 1
        return True

    def _hash(self, item) -> int:
        return hash(item) % len(self._table)

    def _resize(self):
        new_size = int(len(self._table) * self._resize_factor)
        new_table = [deque() for _ in range(new_size)]
        for bucket in self._table:
            for item in bucket:
                index = hash(item) % new_size
                new_table[index].append(item)
        self._table = new_table

---

Продуктовая реализация на C++

Реализация итератора по таблице:

Аннотация:
template - шаблон функции
ChainingHashTableIterator - класс реализующий итератор для хэш-таблицы
typename <ReferenceType> - шаблонный тип значений, хранящихся в хэш-таблице
typedef reference - переопределение ссылки на значения, хранящихся в хэш-таблице
typedef pointer - переопределение указателя на значения, хранящихся в хэш-таблице
typedef difference_type - переопределение типа, представляющегося разность между двумя итераторами
typedef iterator_category - переопределение типа, представляющегося категорию итератора
typedef TableIterator - переопределение типа итератора, использующегося для обхода корзин хэш-таблицы
typedef bucket - переопределение типа, представляющегося корзину хэш-таблицы
typedef bucket_iterator - переопределение типа итератора, использующегося для обхода элементов внутри корзины хэш-таблицы
table_iterator table_it - итератор на текущую корзину хэш-таблицы
table_iterator table_end - итератор на конец хэш-таблицы
bucket_iterator bucket_it - итератор на текущий элемент внутри текущей корзины хэш-таблицы
operator* - метод возвращает ссылку на текущий элемент хэш-таблицы
operator-> - метод возвращает указатель на текущий элемент хэш-таблицы
operator++ - метод увеличивает итератор на один, переходя к следующему элементу хэш-таблицы
operator++(int) - метод увеличивает итератор на один, возвращая копию исходного итератора
operator== - метод проверяет, равны ли два итератора
operator!= - метод проверяет, не равны ли два итератора
_is_end - метод проверяет, является ли текущий итератор итератором на конец хэш-таблицы
_table_it - функция принимает элемент и возвращает его хэш-код
---------------------------------------------------------------------------------

#include <functional>
#include <list>
#include <vector>

template <typename ReferenceType, typename TableIterator,
          typename BucketIterator>
class ChainingHashTableIterator {
 public:
  typedef std::remove_reference_t<ReferenceType> value_type;
  typedef ReferenceType reference;
  typedef value_type* pointer;
  typedef std::ptrdiff_t difference_type;
  typedef std::forward_iterator_tag iterator_category;

 private:
  typedef TableIterator table_iterator;
  typedef typename table_iterator::value_type bucket;
  typedef typename bucket::iterator bucket_iterator;

 public:
  ChainingHashTableIterator(table_iterator table_it, table_iterator table_end,
                            bucket_iterator bucket_it)
      : _table_it(table_it), _table_end(table_end), _bucket_it(bucket_it) {
    if (_table_it != _table_end and _bucket_it == _table_it->end()) ++(*this);
  }

  ChainingHashTableIterator(const ChainingHashTableIterator& other) = default;

  ChainingHashTableIterator(ChainingHashTableIterator&& other) = default;

  ~ChainingHashTableIterator() = default;

  ChainingHashTableIterator& operator=(const ChainingHashTableIterator& other) =
      default;

  ChainingHashTableIterator& operator=(ChainingHashTableIterator&& other) =
      default;

  reference operator*() const { return *_bucket_it; }

  pointer operator->() const { return &(*_bucket_it); }

  ChainingHashTableIterator& operator++() {
    ++_bucket_it;
    if (_bucket_it == _table_it->end()) {
      ++_table_it;
      while (_table_it != _table_end and _table_it->empty()) ++_table_it;
      if (_table_it != _table_end) _bucket_it = _table_it->begin();
    }
    return *this;
  }

  ChainingHashTableIterator operator++(int) {
    ChainingHashTableIterator tmp(*this);
    ++(*this);
    return tmp;
  }

  bool operator==(const ChainingHashTableIterator& other) const {
    return this->_is_end() and other._is_end() or
           _table_it == other._table_it and _bucket_it == other._bucket_it;
  }

  bool operator==(ChainingHashTableIterator&& other) const {
    return this->operator==(other);
  }

  bool operator!=(const ChainingHashTableIterator& other) const {
    return !(*this == other);
  }

  bool operator!=(ChainingHashTableIterator&& other) const {
    return this->operator!=(other);
  }

 private:
  bool _is_end() const { return _table_it == _table_end; }

 private:
  table_iterator _table_it, _table_end;
  bucket_iterator _bucket_it;
}

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

Аннотация:
template - шаблон функции
OpenAddressingHashTable - класс реализующий хэш-таблицу с открытой адресацией
typename ValueType - шаблонный тип значений, хранящихся в хэш-таблице
typename EqOperator - шаблонный тип оператора сравнения
typename Probing - шаблонный тип функции зондирования, используемой для разрешения коллизий
typename Hash - шаблонный тип функции хэширования
typedef - переопределение имени типа данных
typedef reference - переопределение ссылки на значения, хранящихся в хэш-таблице
typedef pointer - переопределение указателя на значения, хранящихся в хэш-таблице
typedef difference_type - переопределение типа, представляющегося разность между двумя итераторами
typedef bucket - переопределение типа, представляющегося корзину хэш-таблицы
typedef table - переопределение таблицы, используемой для хранения корзин
typedef iterator - переопределение типа итератора, использующегося для обхода значений в хэш-таблице
typedef const_iterator - переопределение типа константного итератора, использующегося для обхода значений в хэш-таблице
size_type - размер хэш-таблицы
default_capacity - размер таблицы по умолчанию
hash_type - функция хэширования
probing_type - функция пробирования
equal_type - функция сравнения
max_load_factor - максимальный коэффициент заполнения
rehash_multiplier - множитель для перехэширования
_size - текущее количество элементов в хэш-таблице
_table - вектор, используемый для хранения ячеек хэш-таблицы
_hash - функциональный объект, используемый для вычисления хэш-функции ключа
_probing - политика пробирования, используемая при разрешении коллизий
_eq - функциональный объект, используемый для сравнения ключей
_max_load_factor - максимальный коэффициент загрузки хэш-таблицы
_rehash_multiplier - коэффициент, используемый при перестроении таблицы для вычисления нового размера
size - метод, который возвращает текущий размер хэш-таблицы
empty - метод, который проверяет пуста ли хэш-таблица
load_factor - метод, который возвращает текущий коэффициент заполнения хэш-таблицы
insert - метод, который добавляет новое значение в хэш-таблицу
erase - метод, который удаляет элемент из хэш-таблицы по его значению
contains - метод, который проверяет содержит ли хэш-таблица указанное значение
clear - метод очистки хэш-таблицы
find - метод, который возвращает итератор на указанное значение в хэш-таблице
begin - метод, который возвращает итератор на начало хэш-таблицы
end - метод, который возвращает итератор на конец хэш-таблицы
cbegin - метод, который возвращает константный итератор на начало хэш-таблицы
cend - метод, который возвращает константный итератор на конец хэш-таблицы
_rehash - приватный метод, выполняющий перехэширование хэш-таблицы
_find_index - приватный метод, возвращающий индекс корзины, содержащей указанное значение, или индекс пустой корзины
---------------------------------------------------------------------------------
template <typename ValueType, typename EqOperator = std::equal_to<ValueType>,
          typename Probing = QuadraticProbing<std::size_t>,
          typename Hash = std::hash<ValueType>>
class OpenAddressingHashTable {
 public:
  typedef ValueType value_type;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef std::ptrdiff_t difference_type;
  typedef Hash hash_type;
  typedef Probing probing_type;
  typedef EqOperator equal_type;
  typedef std::size_t size_type;

 private:
  typedef OpenAddressingHashTableBucket<value_type> bucket;
  typedef std::vector<bucket> table;

 public:
  typedef OpenAddressingHashTableIterator<reference, typename table::iterator>
      iterator;
  typedef OpenAddressingHashTableIterator<const_reference,
                                          typename table::const_iterator>
      const_iterator;

 public:
  OpenAddressingHashTable(size_type default_capacity = 10,
                          const hash_type& hash = hash_type(),
                          const probing_type& probing = probing_type(),
                          const equal_type& eq = equal_type(),
                          double max_load_factor = 0.7,
                          double rehash_multiplier = 2.0)
      : _size(0),
        _table(default_capacity),
        _hash(hash),
        _probing(probing),
        _eq(eq),
        _max_load_factor(max_load_factor),
        _rehash_multiplier(rehash_multiplier) {}

  OpenAddressingHashTable(const OpenAddressingHashTable& other) = default;

  OpenAddressingHashTable(OpenAddressingHashTable&& other) = default;

  ~OpenAddressingHashTable() = default;

  OpenAddressingHashTable& operator=(const OpenAddressingHashTable& other) =
      default;

  OpenAddressingHashTable& operator=(OpenAddressingHashTable&& other) = default;

  size_type size() const { return this->_size; }

  bool empty() const { return this->_size == 0; }

  double load_factor() const {
    return static_cast<double>(this->_size) / this->_table.size();
  }

  void insert(const value_type& value) {
    auto iter = this->find(value);
    if (iter != this->end()) {
      *iter = value;
      return;
    }
    if (this->load_factor() > this->_max_load_factor) this->_rehash();
    auto index = this->_find_index(value, true);
    if (index >= this->_table.size()) {
      this->_rehash();
      this->insert(value);
      return;
    }
    auto& bucket = this->_table[index];
    bucket.set_value(value);
    ++this->_size;
  }

  void insert(value_type&& value) {
    auto iter = this->find(value);
    if (iter != this->end()) {
      *iter = std::move(value);
      return;
    }
    if (this->load_factor() > this->_max_load_factor) this->_rehash();
    auto index = this->_find_index(value, true);
    if (index >= this->_table.size()) {
      this->_rehash();
      this->insert(value);
      return;
    }
    auto& bucket = this->_table[index];
    bucket.set_value(std::move(value));
    ++this->_size;
  }

  bool erase(const value_type& value) {
    auto index = this->_find_index(value);
    if (index >= this->_table.size()) return false;
    auto& bucket = this->_table[index];
    if (not bucket) return false;
    bucket.erase();
    --this->_size;
    return true;
  }

  bool erase(value_type&& value) { return this->erase(value); }

  bool contains(const value_type& value) const {
    auto index = this->_find_index(value);
    if (index >= this->_table.size()) return false;
    auto& bucket = this->_table[index];
    return bool(bucket);
  }

  bool contains(value_type&& value) const { return this->contains(value); }

  void clear() {
    for (auto& bucket : this->_table) bucket.erase();
    this->_size = 0;
  }

  iterator find(const value_type& value) {
    auto index = this->_find_index(value);
    if (index >= this->_table.size() or not this->_table[index])
      return this->end();
    return {this->_table.begin() + index, this->_table.end()};
  }

  iterator find(value_type&& value) { return this->find(value); }

  const_iterator find(const value_type& value) const {
    auto index = this->_find_index(value);
    if (index >= this->_table.size() or not this->_table[index])
      return this->cend();
    return {this->_table.cbegin() + index, this->_table.cend()};
  }

  const_iterator find(value_type&& value) const { return this->find(value); }

  iterator begin() { return {this->_table.begin(), this->_table.end()}; }

  iterator end() { return {this->_table.end(), this->_table.end()}; }

  const_iterator cbegin() const {
    return {this->_table.begin(), this->_table.end()};
  }

  const_iterator cend() const {
    return {this->_table.end(), this->_table.end()};
  }

 private:
  void _rehash() {
    size_type new_size = _table.size() * _rehash_multiplier;
    table new_table(new_size);
    for (auto& bucket : _table) {
      if (bucket) {
        auto index = _hash(*bucket) % new_size;
        size_type iteration = 0;
        while (new_table[index]) {
          index = _probing(index, iteration);
          ++iteration;
        }
        new_table[index] = std::move(bucket);
      }
    }
    _table = std::move(new_table);
  }

  size_type _find_index(const value_type& value, bool for_add = false) const {
    size_type index = _hash(value) % _table.size();
    size_type iteration = 1;
    while (index < this->_table.size()) {
      auto& bucket = _table[index];
      if (for_add and bucket.can_set())
        return index;
      else if (bucket.state() == bucket::state_type::EMPTY or
               bucket.state() == bucket::state_type::OCCUPIED and
                   _eq(*bucket, value))
        return index;
      index = _probing(index, iteration);
      ++iteration;
    }
    return index;
  }

 private:
  size_type _size;
  table _table;
  hash_type _hash;
  probing_type _probing;
  equal_type _eq;
  double _max_load_factor;
  double _rehash_multiplier;
}

---

Реализация метода разрешения коллизий на основе открытой адресации

Псевдокод

найти позицию(Элемент x) -> индекс:
    базовый_индекс = хэш-функция(x)
    если в таблице по базовому_индексу существует элемент,
                                        совпадающий с x:
        вернуть базовый_индекс
    шаг = 1
    позиция = генерация_последовательности_открытой_адресации(индекс, шаг) 
    пока позиция не совпадает с базовым_индексам:
        если в таблице по индексу позиции существует элемент, 
                совпадающий с x ИЛИ в таблице по индексу позиции
                не существует элемента:
            вернуть позицию
    вернуть несуществующий индекс

добавить элемент(Элемент x):
    индекс = найти позицию(x)
    если индекс - несуществующий индекс:
        расширить таблицу
        добавить элемент(x)
        завершить выполнение функции
    установить в таблице на позицию индекса элемент x
    увеличить размер на 1

удалить элемент(Элемент x):
    индекс = найти позицию(x)
    если индекс - несуществующий индекс ИЛИ элемент на 
            позиции индекс в таблице не совпадает с x:
        завершить выполнение функции
    удалить элемент в таблице на позиции индекса

проверить содержание элемента(Элемент x) -> true/false:
    индекс = найти позицию(x)
    если индекс - несуществующий индекс ИЛИ элемент на
            позиции индекс в таблице не совпадает с x:
        вернуть false
    вернуть true

---

Реализация на Python

Аннотация:
linear_probing - функция, реализующая линейное зондирование
iteration - номер итерации
quadratic_probing - функция, реализующая квадратичное зондирования
OpenAddressingHashTableBucket - класс, реализующий ячейку хеш-таблицы
State - перечисления, определяющее состояние ячейки
Hashable - значение ячейки
__bool__ - метод, проверяющий, занята ли ячейка
set - метод, устанавливающий значение ячейки
clear - метод, удаляющий значение ячейки
can_set - метод, проверяющий, может ли быть установлено значение ячейки
OpenAddressingHashTable - класс, реализующий хэш-таблицу
Bucket - алиас для хэш-таблицы
__init__ - метод инициализации хэш-таблицы
default_capacity - емкость по умолчанию
max_load_factor - максимальный коэффициент загрузки
resize_factor - коэффициент изменения
probing_function - функция зондирования
_size - размер хэш-таблицы
_table - список, который хранит элементы хэш-таблицы
__len__ - метод, который возвращает число элементов в хэш-таблице
_hash - функция принимает элемент и возвращает его хэш-код
__contains__ - метод, который показывает находится ли указанное значение в хэш-таблице 
index - индекс элемента в таблице
__iter__ - метод, который возвращает итератор для хэш-таблице, который позволяет перебирать элементы в таблице
bucket - элемент из списка
item - элемент из bucket
__eq__ - метод, который показывает равна ли хэш-таблица указанному объекту или нет
load_factor - функция, которая возвращает текущий коэффициент загрузки хэш-таблицы
add - функция, которая добавляет указанное значение в хэш-таблицу
_add_existing - приватная функция, которая проверяет, существует ли уже значения в хэш-таблице
_find_index_for_addition - приватная функция, которая используется для поиска индекса в массиве для добавления нового значения
_resize - функция, которая вызывается, когда коэффициент загрузки превышает максимальный коэффициент загрузки
remove - функция, которая удаляет указанное значение из хэш-таблицы
new_size - новый размер хэш-таблицы
new_table - новый список, который хранит элементы хэш-таблицы после изменений
get - функция, которая возвращает значение из таблицы по узазанному ключу
find_index - функция, которая находит индекс ячейки для указанного значения
---------------------------------------------------------------------------------
from enum import Enum
from typing import Hashable, Any
from dataclasses import dataclass

def linear_probing(index, iteration, step=1):
    return index + step * iteration

def quadratic_probing(index, iteration, step=1):
    return index + ((step * iteration) ** 2)

@dataclass
class OpenAddressingHashTableBucket:
    class State(Enum):
        EMPTY = 0
        DELETED = 1
        OCCUPIED = 2

    value: Hashable = None
    state: State = State.EMPTY

    def __bool__(self):
        return self.state == self.State.OCCUPIED

    def set(self, value):
        self.value = value
        self.state = self.State.OCCUPIED

    def clear(self):
        self.value = None
        self.state = self.State.DELETED

    def can_set(self) -> bool:
        return self.state in (self.State.DELETED, self.State.EMPTY)

class OpenAddressingHashTable:
    Bucket = OpenAddressingHashTableBucket

    def __init__(self,
                 default_capacity=10,
                 max_load_factor=0.7,
                 resize_factor=2,
                 probing_function=quadratic_probing):
        self._size = 0
        self._table = [self.Bucket() for _ in range(default_capacity)]
        self._max_load_factor = max_load_factor
        self._resize_factor = resize_factor
        self._probing_function = probing_function

    def __len__(self):
        return self._size

    def __contains__(self, value):
        index = self._find_index(value)
        if index >= len(self._table):
            return False
        bucket = self._table[index]
        return bool(bucket)

    def __iter__(self):
        for bucket in self._table:
            if bucket:
                yield bucket.value

    def __eq__(self, other):
        if len(self) != len(other):
            return False
        for item in self:
            if item not in other:
                return False
        return True

    def load_factor(self) -> float:
        return self._size / len(self._table)

    def add(self, value: Hashable):
        if self._add_existing(value):
            return
        if self.load_factor() > self._max_load_factor:
            self._resize()
        index = self._find_index(value, for_add=True)
        if index >= len(self._table):
            self._resize()
            return self.add(value)
        bucket = self._table[index]
        bucket.set(value)
        self._size += 1

    def remove(self, value: Hashable) -> bool:
        index = self._find_index(value)
        if index >= len(self._table):
            return False
        bucket = self._table[index]
        if not bucket:
            return False
        bucket.clear()
        self._size -= 1
        return True

    def get(self, value: Hashable) -> Any:
        index = self._find_index(value)
        if index >= len(self._table) or not self._table[index]:
            raise KeyError(f"{value} not found")
        return self._table[index].value

    def _add_existing(self, value: Hashable) -> bool:
        index = self._find_index(value)
        if index >= len(self._table):
            return False
        bucket = self._table[index]
        if bucket:
            bucket.set(value)
            return True
        return False

    def _find_index_for_addition(self, value: Hashable) -> int:
        index = self._hash(value)
        step = 1
        result_index = len(self._table)
        while index < len(self._table):
            bucket = self._table[index]
            if bucket.state == self.Bucket.State.OCCUPIED and bucket.value == value:
                return index
            elif bucket.can_set() and result_index == len(self._table):
                result_index = index
            index = self._probing_function(index, step)
            step += 1
        return result_index

    def _find_index(self, value: Hashable, for_add=False) -> int:
        index = self._hash(value)
        step = 1
        while index < len(self._table):
            bucket = self._table[index]
            if for_add and bucket.can_set():
                return index
            elif (bucket.state == self.Bucket.State.EMPTY or
                  bucket.state == self.Bucket.State.OCCUPIED and
                  bucket.value == value
                  ):
                return index
            index = self._probing_function(index, step)
            step += 1
        return index

    def _hash(self, item) -> int:
        return hash(item) % len(self._table)

    def _resize(self):
        new_size = int(len(self._table) * self._resize_factor)
        new_table = [self.Bucket() for _ in range(new_size)]
        for bucket in self._table:
            if bucket:
                index = hash(bucket.value) % new_size
                iteration = 0
                while new_table[index]:
                    index = self._probing_function(index, iteration)
                    iteration += 1
                new_table[index] = bucket
        self._table = new_table

---

Продуктовая реализация на C++

Реализация функторов зондирования:

Реализация интерфейса зондирования:

Аннотация:
template - шаблон функции
Probing - алгоритм зондирования для хэш-таблицы
typedef - переопределение имени типа данных
IndexType - параметр, который определяет тип индексов, используемых в хеш-таблице
~Probing - виртуальный деструктор по умолчанию
operator - виртуальная функция, которая вычисляет следующий индекс в последовательности пробирования
start - начало, откуда начнет считать operator
iteration - счетчик попыток поиска свободного места в хэш-таблице при разрешении коллизий
---------------------------------------------------------------------------------
#include <functional>
#include <vector>

template <typename IndexType>
struct Probing {
  typedef IndexType index_type;

  virtual ~Probing() = default;

  virtual index_type operator()(index_type start,
                                index_type iteration) const = 0;
}

Реализация линейного зондирования:

Аннотация:
template - шаблон функции
IndexType - индексы, используемые в хэш-таблице
AddFunction - функция-обёртка для операции сложения, используемая при вычислении нового индекса
MultiplyFunction - функция-обёртка для операции умножения, используемая при вычислении нового индекса
typedef - переопределение имени типа данных
LinearProbing - алгоритм линейного зондирования
start - начальный индекс для поиска свободного места в хэш-таблице
iteration - текущее количество попыток для поиска свободного места в хэш-таблице
---------------------------------------------------------------------------------
template <typename IndexType = std::size_t,
          typename AddFunction = std::plus<IndexType>,
          typename MultiplyFunction = std::multiplies<IndexType>>
struct LinearProbing : Probing<IndexType> {
  using index_type = typename Probing<IndexType>::index_type;
  typedef AddFunction add_type;
  typedef MultiplyFunction multiply_type;

  LinearProbing(index_type step = 1, add_type add_func = add_type(),
                multiply_type multiply_func = multiply_type())
      : step(step), add_func(add_func), multiply_func(multiply_func) {}

  index_type operator()(index_type start, index_type iteration) const override {
    return add_func(start, multiply_func(step, iteration));
  }

 private:
  index_type step;
  add_type add_func;
  multiply_type multiply_func;
}

Реализация квадратичного зондирования:

Аннотация:
template - шаблон функции
IndexType - индексы, используемые в хэш-таблице
AddFunction - функция-обёртка для операции сложения, используемая при вычислении нового индекса
MultiplyFunction - функция-обёртка для операции умножения, используемая при вычислении нового индекса
typedef - переопределение имени типа данных
QuadraticProbing - алгоритм квадратичного зондирования
start - начальный индекс для поиска свободного места в хэш-таблице
iteration - текущее количество попыток для поиска свободного места в хэш-таблице
---------------------------------------------------------------------------------
template <typename IndexType = std::size_t,
          typename AddFunction = std::plus<IndexType>,
          typename MultiplyFunction = std::multiplies<IndexType>>
struct QuadraticProbing : Probing<IndexType> {
  using index_type = typename Probing<IndexType>::index_type;
  typedef AddFunction add_type;
  typedef MultiplyFunction multiply_type;

  QuadraticProbing(index_type step = 1, add_type add_func = add_type(),
                   multiply_type multiply_func = multiply_type())
      : step(step), add_func(add_func), multiply_func(multiply_func) {}

  index_type operator()(index_type start, index_type iteration) const override {
    auto value = multiply_func(step, iteration);
    return add_func(start, multiply_func(value, value));
  }

 private:
  index_type step;
  add_type add_func;
  multiply_type multiply_func;
}

Реализация корзины:

Аннотация:
template - шаблон функции
OpenAddressingHashTableBucket - структура данных, использующая для хранения значений в хэш-таблице
OpenAddressingHashTableBucketState - перечисление, представляющее собой состояние ячейки хэш-таблицы
typedef - переопределение имени типа данных
value_type - значение, хранящиеся в ячейки
reference - ссылка на значение, хранящиеся в ячейки
const_reference - константная ссылка на значение, хранящиеся в ячейки
pointer - указатель на значение в ячейки
const_pointer - константный указатель на значение в ячейки
state_type - состояние ячейки
OpenAddressingHashTableBucket() - конструктор, который создает ячейку
_ptr - указатель на значение, хранящееся в ячейке
_state - текущее состояние ячейки
~OpenAddressingHashTableBucket() - деструктор, освобождает память, выделенную под значение
state - метод, возвращающий текущее состояние ячейки 
operator* - метод, возвращающий ссылку на значение, хранящееся в ячейке
set_value - метод, устанавливающий новое значение в ячейку
erase - метод, удаляющий значение из ячейки
bool - метод, показывающий занята ли ячейка
can_set - метод, показывающий пуста или удалена ли ячейка
---------------------------------------------------------------------------------
template <typename ValueType>
struct OpenAddressingHashTableBucket {
  enum OpenAddressingHashTableBucketState {
    EMPTY,
    DELETED,
    OCCUPIED,
  };

  typedef ValueType value_type;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef OpenAddressingHashTableBucketState state_type;

  OpenAddressingHashTableBucket() : _ptr(nullptr), _state(state_type::EMPTY) {}

  OpenAddressingHashTableBucket(const value_type& value)
      : _ptr(new value_type(value)), _state(state_type::OCCUPIED) {}

  OpenAddressingHashTableBucket(value_type&& value)
      : _ptr(new value_type(std::move(value))), _state(state_type::OCCUPIED) {}

  OpenAddressingHashTableBucket(const OpenAddressingHashTableBucket& other)
      : _ptr(new value_type(*other._ptr)), _state(other._state) {}

  OpenAddressingHashTableBucket(OpenAddressingHashTableBucket&& other)
      : _ptr(other._ptr), _state(other._state) {
    other._ptr = nullptr;
  }

  ~OpenAddressingHashTableBucket() { delete _ptr; }

  OpenAddressingHashTableBucket& operator=(
      const OpenAddressingHashTableBucket& other) {
    if (this != &other) {
      delete _ptr;
      _ptr = new value_type(*other._ptr);
      _state = other._state;
    }
    return *this;
  }

  OpenAddressingHashTableBucket& operator=(
      OpenAddressingHashTableBucket&& other) {
    if (this != &other) {
      delete _ptr;
      _ptr = other._ptr;
      other._ptr = nullptr;
      _state = other._state;
    }
    return *this;
  }

  state_type state() const { return this->_state; }

  reference operator*() { return *_ptr; }

  const_reference operator*() const { return *_ptr; }

  void set_value(const value_type& value) {
    if (_ptr == nullptr)
      _ptr = new value_type(value);
    else
      *_ptr = value;
    _state = state_type::OCCUPIED;
  }

  void set_value(value_type&& value) {
    if (_ptr == nullptr)
      _ptr = new value_type(std::move(value));
    else
      *_ptr = std::move(value);
    _state = state_type::OCCUPIED;
  }

  void erase() {
    delete _ptr;
    _ptr = nullptr;
    _state = state_type::DELETED;
  }

  operator bool() const { return _state == state_type::OCCUPIED; }

  bool can_set() const {
    return _state == state_type::EMPTY or _state == state_type::DELETED;
  }

 private:
  pointer _ptr;
  state_type _state;
}

Реализация итератора:

Аннотация:
template - шаблон функции
typename - шаблонный тип данных параметра
ReferenceType - тип ссылки на элемент в хэш-таблице
TableIterator - тип итератора, используемого для перебора корзин в хэш-таблице
OpenAddressingHashTableIterator - итератор хэш-таблицы с открытой адресацией
typedef - переопределение имени типа данных
value_type - элементы, хранящиеся в хэш-таблице
reference - ссылка на элементы, хранящиеся в хэш-таблице
pointer - указатель на элементы в хэш-таблице
difference_type - тип, представляющий разность между двумя итераторами
iterator_category - тип, представляющий категорию итератора
bucket - корзина хэш-таблицы
OpenAddressingHashTableIterator() - конструктор итератора
_it - итератор на текущую корзину
it - текущая корзина
_end - итератор на конечную корзину
end - конец хэш-таблицы
operator= - оператор присваивания 
operator* -  оператор разыменования
operator-> - оператор стрелки, возвращающий указатель на элемент в текущей корзине
operator++ - оператор инкремента, переходящий к следующей непустой корзине
operator== - оператор сравнения на равенство
operator!= - оператор сравнения на неравенство
---------------------------------------------------------------------------------
template <typename ReferenceType, typename TableIterator>
class OpenAddressingHashTableIterator {
 public:
  typedef std::remove_reference_t<ReferenceType> value_type;
  typedef ReferenceType reference;
  typedef value_type* pointer;
  typedef std::ptrdiff_t difference_type;
  typedef std::forward_iterator_tag iterator_category;

 private:
  typedef TableIterator table_iterator;
  typedef typename table_iterator::value_type bucket;

 public:
  OpenAddressingHashTableIterator(table_iterator it, table_iterator end)
      : _it(it), _end(end) {
    while (_it != _end and not *_it) ++_it;
  }

  OpenAddressingHashTableIterator(
      const OpenAddressingHashTableIterator& other) = default;

  OpenAddressingHashTableIterator(OpenAddressingHashTableIterator&& other) =
      default;

  ~OpenAddressingHashTableIterator() = default;

  OpenAddressingHashTableIterator& operator=(
      const OpenAddressingHashTableIterator& other) = default;

  OpenAddressingHashTableIterator& operator=(
      OpenAddressingHashTableIterator&& other) = default;

  reference operator*() { return **_it; }

  pointer operator->() { return &**_it; }

  OpenAddressingHashTableIterator& operator++() {
    ++_it;
    while (_it != _end and not *_it) ++_it;
    return *this;
  }

  OpenAddressingHashTableIterator operator++(int) {
    auto tmp = *this;
    ++*this;
    return tmp;
  }

  bool operator==(const OpenAddressingHashTableIterator& other) const {
    return _it == other._it;
  }

  bool operator==(OpenAddressingHashTableIterator&& other) const {
    return _it == other._it;
  }

  bool operator!=(const OpenAddressingHashTableIterator& other) const {
    return !(*this == other);
  }

  bool operator!=(const OpenAddressingHashTableIterator&& other) const {
    return !(*this == other);
  }

 private:
  table_iterator _it, _end;
}

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

Аннотация:
template - шаблон функции
typename - шаблонный тип данных параметра
ValueType - шаблонный параметр, определяющий тип значений, хранящихся в хэш-таблице
EqOperator - шаблонный параметр, определяющий тип функционального объекта, используемого для сравнения значений в хэш-таблице
Probing - шаблонный параметр, определяющий тип функционального объекта, используемого для зондирования в хэш-таблице
Hash - шаблонный параметр, определяющий тип функционального объекта, используемого для вычисления хэш-функции в хэш-таблице
OpenAddressingHashTableBucket - класс, представляющий собой ячейку хэш-таблицы
typedef - переопределение имени типа данных
value_type - значение, хранящиеся в ячейки
reference - ссылка на значение, хранящиеся в ячейки
const_reference - константная ссылка на значение, хранящиеся в ячейки
pointer - указатель на значение в ячейки
const_pointer - константный указатель на значение в ячейки
difference_type - тип, представляющий разность между двумя итераторами
hash_type - тип, представляющий категорию итератора
probing_type - шаблонный параметр, определяющий тип функции зондирования, которая используется для разрешения коллизий в хэш-таблице
equal_type - шаблонный параметр, определяющий тип функции сравнения, которая используется для сравнения ключей в хэш-таблице
size_type - тип, использующийся для представления размера хэш-таблицы
bucket - корзина хэш-таблицы
table - вектор из ячеек хэш-таблицы
OpenAddressingHashTable - конструктор, принимающий параметры для инициализации хэш-таблицы
default_capacity - емкость по умолчанию
max_load_factor - максимальный коэффициент загрузки
rehash_multiplier - коэффициент, используемый при перехэшировании хэш-таблицы
_size - приватное поле, представляющее собой текущее количество элементов в хэш-таблице 
_table - приватное поле, представляющее собой вектор из ячеек хеш-таблицы
_hash - приватное поле, представляющее собой функциональный объект, используемый для вычисления хэш-функции в хэш-таблице
_probing - приватное поле, представляющее собой функциональный объект, используемый для зондирования в хэш-таблице
_eq - приватное поле, представляющее собой функциональный объект, используемый для сравнения значений в хэш-таблице
_max_load_factor - приватное поле, представляющее собой максимальный коэффициент заполнения хэш-таблицы
_rehash_multiplier - приватное поле, представляющее собой множитель, используемый при перехэшировании хэш-таблицы 
~OpenAddressingHashTable - деструктор хэш-таблицы
size - метод, возвращающий текущее количество элементов в хэш-таблице
empty - метод, проверяющий, пуста ли хэш-таблица
load_factor - метод, возвращающий текущий коэффициент заполнения хэш-таблицы
insert - метод, добавляющий элемент в хэш-таблицу
_rehash - приватный метод, выполняющий перехеширование хэш-таблицы
_find_index - приватный метод, возвращающий индекс ячейки в хэш-таблице, соответствующий указанному значению или пустой ячейки для добавления нового элемента
erase - метод, удаляющий элемент из хэш-таблицы
contains - метод, проверяющий, содержит ли хэш-таблица указанное значение
clear - метод, очищающий хэш-таблицу
find - метод, возвращающий итератор на элемент в хэш-таблице, соответствующий указанному значению
begin - метод, возвращающий итератор на начало хэш-таблицы
end - метод, возвращающий итератор на конец хэш-таблицы
cbegin - :метод, возвращающий константный итератор на начало хэш-таблицы
cend - метод, возвращающий константный итератор на конец хэш-таблицы
iteration - текущее количество попыток для поиска свободного места в хэш-таблице
---------------------------------------------------------------------------------
template <typename ValueType, typename EqOperator = std::equal_to<ValueType>,
          typename Probing = QuadraticProbing<std::size_t>,
          typename Hash = std::hash<ValueType>>
class OpenAddressingHashTable {
 public:
  typedef ValueType value_type;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef std::ptrdiff_t difference_type;
  typedef Hash hash_type;
  typedef Probing probing_type;
  typedef EqOperator equal_type;
  typedef std::size_t size_type;

 private:
  typedef OpenAddressingHashTableBucket<value_type> bucket;
  typedef std::vector<bucket> table;

 public:
  typedef OpenAddressingHashTableIterator<reference, typename table::iterator>
      iterator;
  typedef OpenAddressingHashTableIterator<const_reference,
                                          typename table::const_iterator>
      const_iterator;

 public:
  OpenAddressingHashTable(size_type default_capacity = 10,
                          const hash_type& hash = hash_type(),
                          const probing_type& probing = probing_type(),
                          const equal_type& eq = equal_type(),
                          double max_load_factor = 0.7,
                          double rehash_multiplier = 2.0)
      : _size(0),
        _table(default_capacity),
        _hash(hash),
        _probing(probing),
        _eq(eq),
        _max_load_factor(max_load_factor),
        _rehash_multiplier(rehash_multiplier) {}

  OpenAddressingHashTable(const OpenAddressingHashTable& other) = default;

  OpenAddressingHashTable(OpenAddressingHashTable&& other) = default;

  ~OpenAddressingHashTable() = default;

  OpenAddressingHashTable& operator=(const OpenAddressingHashTable& other) =
      default;

  OpenAddressingHashTable& operator=(OpenAddressingHashTable&& other) = default;

  size_type size() const { return this->_size; }

  bool empty() const { return this->_size == 0; }

  double load_factor() const {
    return static_cast<double>(this->_size) / this->_table.size();
  }

  void insert(const value_type& value) {
    auto iter = this->find(value);
    if (iter != this->end()) {
      *iter = value;
      return;
    }
    if (this->load_factor() > this->_max_load_factor) this->_rehash();
    auto index = this->_find_index(value, true);
    if (index >= this->_table.size()) {
      this->_rehash();
      this->insert(value);
      return;
    }
    auto& bucket = this->_table[index];
    bucket.set_value(value);
    ++this->_size;
  }

  void insert(value_type&& value) {
    auto iter = this->find(value);
    if (iter != this->end()) {
      *iter = std::move(value);
      return;
    }
    if (this->load_factor() > this->_max_load_factor) this->_rehash();
    auto index = this->_find_index(value, true);
    if (index >= this->_table.size()) {
      this->_rehash();
      this->insert(value);
      return;
    }
    auto& bucket = this->_table[index];
    bucket.set_value(std::move(value));
    ++this->_size;
  }

  bool erase(const value_type& value) {
    auto index = this->_find_index(value);
    if (index >= this->_table.size()) return false;
    auto& bucket = this->_table[index];
    if (not bucket) return false;
    bucket.erase();
    --this->_size;
    return true;
  }

  bool erase(value_type&& value) { return this->erase(value); }

  bool contains(const value_type& value) const {
    auto index = this->_find_index(value);
    if (index >= this->_table.size()) return false;
    auto& bucket = this->_table[index];
    return bool(bucket);
  }

  bool contains(value_type&& value) const { return this->contains(value); }

  void clear() {
    for (auto& bucket : this->_table) bucket.erase();
    this->_size = 0;
  }

  iterator find(const value_type& value) {
    auto index = this->_find_index(value);
    if (index >= this->_table.size() or not this->_table[index])
      return this->end();
    return {this->_table.begin() + index, this->_table.end()};
  }

  iterator find(value_type&& value) { return this->find(value); }

  const_iterator find(const value_type& value) const {
    auto index = this->_find_index(value);
    if (index >= this->_table.size() or not this->_table[index])
      return this->cend();
    return {this->_table.cbegin() + index, this->_table.cend()};
  }

  const_iterator find(value_type&& value) const { return this->find(value); }

  iterator begin() { return {this->_table.begin(), this->_table.end()}; }

  iterator end() { return {this->_table.end(), this->_table.end()}; }

  const_iterator cbegin() const {
    return {this->_table.begin(), this->_table.end()};
  }

  const_iterator cend() const {
    return {this->_table.end(), this->_table.end()};
  }

 private:
  void _rehash() {
    size_type new_size = _table.size() * _rehash_multiplier;
    table new_table(new_size);
    for (auto& bucket : _table) {
      if (bucket) {
        auto index = _hash(*bucket) % new_size;
        size_type iteration = 0;
        while (new_table[index]) {
          index = _probing(index, iteration);
          ++iteration;
        }
        new_table[index] = std::move(bucket);
      }
    }
    _table = std::move(new_table);
  }

  size_type _find_index(const value_type& value, bool for_add = false) const {
    size_type index = _hash(value) % _table.size();
    size_type iteration = 1;
    while (index < this->_table.size()) {
      auto& bucket = _table[index];
      if (for_add and bucket.can_set())
        return index;
      else if (bucket.state() == bucket::state_type::EMPTY or
               bucket.state() == bucket::state_type::OCCUPIED and
                   _eq(*bucket, value))
        return index;
      index = _probing(index, iteration);
      ++iteration;
    }
    return index;
  }

 private:
  size_type _size;
  table _table;
  hash_type _hash;
  probing_type _probing;
  equal_type _eq;
  double _max_load_factor;
  double _rehash_multiplier;
}