Как реализовать хэш-таблицу в Python?

[

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

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

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

Знакомство с хэш-таблицей

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

Хэш-таблица против словаря

Хотя в Python словарь (dict) и реализован с использованием хэш-таблицы, существуют некоторые различия между этими двумя структурами данных.

Хэш-таблица	Словарь
Элементы неупорядочены	Элементы неупорядочены
Индексация по хэш-ключу	Индексация по ключу
Решение коллизий на уровне обработки	Решение коллизий на уровне языка Python

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

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

Хэш-таблица: массив с хэш-функцией

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

Понимание хэш-функции

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

В следующих подразделах мы рассмотрим как работает встроенная функция hash() в Python, а также напишем свою собственную хэш-функцию.

Исследование встроенной функции hash() Python

В Python уже есть встроенная функция hash(), которая возвращает хэш-код для переданного значения. Однако это не обязательно значит, что hash() всегда возвращает уникальный хэш-код для каждого уникального значения. Возможно, что два разных значения могут иметь одинаковый хэш-код, что называется “коллизией хэш-кода”.

Вот примеры использования встроенной функции hash() в Python:

>>> hash("hello")
5527622724386862202
>>> hash(42)
42
>>> hash(3.14)
1418983462493309918

hash("hello") возвращает уникальный хэш-код для строки “hello”. Однако hash(42) возвращает само число 42, так как числовые значения хэшируются в соответствии с их собственным значением. Аналогично, hash(3.14) возвращает уникальный хэш-код для числа 3.14.

Глубокое изучение hash() в Python

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

Встроенный тип str в Python имеет свою собственную хэш-функцию. Например, hash("hello") возвращает уникальный хэш-код для строки “hello”. Другие типы данных, такие как int и float, также имеют свои собственные хэш-функции. Они преобразуют числовое значение в хэш-код, который также является числом.

Определение свойств хэш-функции

Хэш-функция должна удовлетворять нескольким свойствам, чтобы быть эффективной:

1. Уникальность: Хэш-функция должна возвращать уникальный хэш-код для каждого уникального значения. Если два разных значения имеют один и тот же хэш-код, это называется “коллизией хэш-кода”. Чтобы уменьшить вероятность коллизий, хорошая хэш-функция должна равномерно распределять значения по всему диапазону возможных хэш-кодов.

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

3. Вычислительная эффективность: Хорошая хэш-функция должна быть быстрой и эффективной в вычислении. Вычисление хэш-кода должно занимать как можно меньше времени.

4. Изоляция: Хэш-функция должна быть независимой от внутреннего состояния объекта. Два объекта, считающихся “равными” на основе метода __eq__(), должны иметь одинаковый хэш-код.

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

Сравнение идентичности объекта с его хэш-кодом

В Python каждый объект имеет свой уникальный хэш-код, который можно получить с помощью функции hash(). Хэш-код представляет собой целое число, которое определяется на основе внутреннего состояния объекта. Однако важно понимать, что хэш-код не является уникальным идентификатором объекта.

Два разных объекта могут иметь одинаковый хэш-код. Это называется “коллизией хэш-кода”. В Python коллизии получаются благодаря ограниченному диапазону возможных хэш-кодов и сложности создания идеальной хэш-функции.

Однако, если два объекта равны между собой на основе метода __eq__(), они должны иметь одинаковый хэш-код. Например:

>>> a = "hello"
>>> b = "hello"
>>> a == b
True
>>> hash(a) == hash(b)
True

>>> x = 42
>>> y = 42
>>> x == y
True
>>> hash(x) == hash(y)
True

В приведенных примерах объекты a и b равны между собой на основе метода __eq__(), поэтому они имеют одинаковый хэш-код. Аналогично, объекты x и y тоже равны между собой и имеют одинаковый хэш-код.

Создание собственной хэш-функции

Python предоставляет возможность создания собственной хэш-функции путем определения метода __hash__() для пользовательских классов. Метод __hash__() должен вернуть хэш-код объекта.

Вот пример создания собственной хэш-функции для пользовательского класса Person:

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __hash__(self):
        return hash(self.name) + hash(self.age)

Мы определили метод __hash__() для класса Person, который возвращает сумму хэш-кодов имени и возраста объекта. Теперь объекты класса Person можно использовать в хэш-таблицах и сравнивать их на основе их хэш-кода.

Прототип хэш-таблицы в Python с использованием TDD

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

Мы начнем с создания базового класса HashTable и напишем первый тест для проверки его функциональности.

Возьмите экспресс-курс по разработке, основанной на TDD

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

При использовании TDD мы проходим следующие шаги:

1. Создаем тесты для требований
2. Запускаем тесты и убеждаемся, что они проваливаются
3. Реализуем минимальное количество кода, чтобы тесты проходили
4. Улучшаем код и перезапускаем тесты
5. Повторяем шаги 3 и 4, чтобы добиться полного покрытия тестами

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

Определите класс CustomHashTable

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

class HashTable:
    def __init__(self):
        self.capacity = 10
        self.size = 0
        self.buckets = [[] for _ in range(self.capacity)]

Мы определили метод __init__() для класса HashTable, который инициализирует начальные значения атрибутов capacity, size и buckets. Атрибут capacity определяет начальный размер хэш-таблицы, а атрибут buckets представляет собой список пустых списков, где будут храниться элементы хэш-таблицы.

Вставка ключ-значение пары

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

class HashTable:
    ...

    def insert(self, key, value):
        index = self.hash_function(key)
        bucket = self.buckets[index]

        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        else:
            bucket.append((key, value))
            self.size += 1

Мы определили метод insert(), который принимает ключ (key) и значение (value), и добавляет их в хэш-таблицу. Сначала мы вычисляем индекс ячейки массива (index), используя хэш-функцию. Затем мы проходим по списку элементов данной ячейки, чтобы проверить, есть ли уже элемент с таким же ключом. Если да, мы обновляем значение элемента. Если нет, мы добавляем новый элемент в конец списка.

Поиск значения по ключу

Добавим функциональность поиска значения в хэш-таблице по ключу.

class HashTable:
    ...

    def get(self, key):
        index = self.hash_function(key)
        bucket = self.buckets[index]

        for pair in bucket:
            if pair[0] == key:
                return pair[1]

        raise KeyError(f"Key not found: {key}")

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

Если элемент с заданным ключом не найден, мы выбрасываем исключение KeyError.

Удаление ключ-значение пары

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

class HashTable:
    ...

    def remove(self, key):
        index = self.hash_function(key)
        bucket = self.buckets[index]

        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket.pop(i)
                self.size -= 1
                return

        raise KeyError(f"Key not found: {key}")

Мы определили метод remove(), который принимает ключ (key) и удаляет ключ-значение пару с указанным ключом из хэш-таблицы. Мы вычисляем индекс ячейки (index) с помощью хэш-функции и проходим по элементам этой ячейки с помощью цикла. Если находим элемент с указанным ключом, мы используем метод pop() для удаления элемента из списка и уменьшаем размер хэш-таблицы на 1.

Если элемент с заданным ключом не найден, мы выбрасываем исключение KeyError.

Обновление значения существующей пары

Добавим функциональность обновления значения существующей пары по ключу.

class HashTable:
    ...

    def update(self, key, value):
        index = self.hash_function(key)
        bucket = self.buckets[index]

        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return

        raise KeyError(f"Key not found: {key}")

Мы определили метод update(), который принимает ключ (key) и новое значение (value) и обновляет значение существующей пары с указанным ключом. Мы вычисляем индекс ячейки (index) с помощью хэш-функции и проходим по элементам этой ячейки с помощью цикла. Если находим элемент с указанным ключом, мы обновляем его значение на новое.

Если элемент с заданным ключом не найден, мы выбрасываем исключение KeyError.

Получение ключей и значений

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

class HashTable:
    ...

    def keys(self):
        keys = []

        for bucket in self.buckets:
            for pair in bucket:
                keys.append(pair[0])

        return keys

    def values(self):
        values = []

        for bucket in self.buckets:
            for pair in bucket:
                values.append(pair[1])

        return values

Мы определили метод keys(), который возвращает список всех ключей из хэш-таблицы, и метод values(), который возвращает список всех значений из хэш-таблицы. Мы просто проходим по всем элементам хэш-таблицы и добавляем соответствующие ключи и значения в список.

Получение количества элементов в хэш-таблице

Добавим функциональность получения количества элементов в хэш-таблице.

class HashTable:
    ...

    def length(self):
        return self.size

Мы определили метод length(), который возвращает текущее количество элементов в хэш-таблице. Мы просто возвращаем значение атрибута size, который увеличивается при каждой успешной операции добавления элемента.

Сделайте хэш-таблицу “итерируемой”

Давайте сделаем нашу хэш-таблицу “итерируемой”, чтобы мы могли проходить по элементам с помощью цикла for.

class HashTable:
    ...

    def __iter__(self):
        for bucket in self.buckets:
            for pair in bucket:
                yield pair

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

Представление хэш-таблицы в виде текста

Добавим функциональность представления хэш-таблицы в виде текста с помощью метода __str__().

class HashTable:
    ...

    def __str__(self):
        output = ""

        for index, bucket in enumerate(self.buckets):
            bucket_output = ", ".join([f"{pair[0]}={pair[1]}" for pair in bucket])
            output += f"[{index}]: {bucket_output}\n"

        return output

Мы переопределили метод __str__() для класса HashTable, чтобы он возвращал строку, представляющую нашу хэш-таблицу. Мы проходим по всем элементам хэш-таблицы и формируем строку, содержащую индекс ячейки и элементы каждой ячейки.

Разрешение коллизий хэш-кода

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

Нахождение столкнувшихся ключей через линейное зондирование

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

Давайте реализуем линейное зондирование в нашей хэш-таблице.

class HashTable:
    ...

    def insert(self, key, value):
        index = self.hash_function(key)
        bucket = self.buckets[index]

        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))
        self.size += 1

        if self.load_factor() > 0.7:
            self.resize()

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

Мы также добавили проверку на load_factor() в методе insert(). load_factor() вычисляет отношение размера хэш-таблицы к ее вместимости. Если это отношение превышает 0.7, мы вызываем метод resize(), который увеличивает размер хэш-таблицы для уменьшения коллизий.

Автоматическое изменение размера хэш-таблицы

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

class HashTable:
    ...

    def resize(self):
        self.capacity *= 2
        self.size = 0
        new_buckets = [[] for _ in range(self.capacity)]

        for bucket in self.buckets:
            for pair in bucket:
                index = self.hash_function(pair[0])
                new_buckets[index].append(pair)
                self.size += 1

        self.buckets = new_buckets

Мы определили метод resize(), который удваивает вместимость нашей хэш-таблицы (атрибут capacity) и перехеширует все пары ключ-значение в новое множество ячеек массива. Мы также обновляем значение атрибута size и перезаписываем атрибут buckets для соответствия новому размеру.

Вычисление коэффициента заполнения

Добавим функциональность вычисления коэффициента заполнения хэш-таблицы.

class HashTable:
    ...

    def load_factor(self):
        return self.size / self.capacity

Мы определили метод load_factor(), который вычисляет отношение размера хэш-таблицы (атрибут size) к ее вместимости (атрибут capacity). Это позволяет нам определить, насколько “заполнена” хэш-таблица. Значение коэффициента заполнения превышает 0.7, мы вызываем метод resize() для уменьшения коллизий.

Выделение коллизирующих ключей с использованием раздельной цепочки

Другой способ разрешить коллизии хэш-кода является использование метода под названием “раздельная цепочка”. При использовании раздельной цепочки, вместо того, чтобы помещать несколько значений с одинаковым хэш-кодом в одну ячейку массива, мы создаем список, который хранит все эти значения. Таким образом, каждая ячейка массива является списком значений.

Давайте реализуем раздельную цепочку в нашей хэш-таблице.

class HashTable:
    ...

    def insert(self, key, value):
        index = self.hash_function(key)
        bucket = self.buckets[index]

        for i, pair in enumerate(bucket):
            if pair[0] == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))
        self.size += 1

        if self.load_factor() > 0.7:
            self.resize()

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

Сохранение порядка вставки в хэш-таблице

Добавим функциональность сохранения порядка вставки элементов в хэш-таблице.

class HashTable:
    ...

    def __iter__(self):
        pairs = [pair for bucket in self.buckets for pair in bucket]
        pairs.sort(key=lambda pair: pair[0])

        for pair in pairs:
            yield pair

Мы переопределили метод __iter__() для класса HashTable, чтобы мы могли проходить по элементам в порядке их вставки. Мы сначала объединяем все пары ключ-значение в один список pairs, а затем сортируем этот список по ключам. Наконец, мы проходим по отсортированному списку и возвращаем каждую пару.

Использование хэшируемых ключей

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

class HashTable:
    ...

    def hash_function(self, key):
        if not isinstance(key, str):
            raise TypeError("Key must be a string")

        return hash(key) % self.capacity

Мы уточнили метод hash_function(), чтобы он принимал только строковые значения ключей и выбрасывал исключение, если ключ не является строкой. Мы всегда хэшируем ключ с помощью встроенной функции hash(), но обрезаем хэш-код по размеру вместимости (атрибут capacity).

Заключение

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

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

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

---

api best-practices career community databases data-science data-structures [data-viz](/tutorials/data- viz/) devops django docker editors flask front-end gamedev gui machine- learning numpy projects python testing tools web- dev web-scraping

---