Как использовать хэш-таблицы в Python?

[

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

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

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

В этом руководстве вы узнаете:

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

Знакомство с структурой данных “хэш-таблица”

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

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

Хэш-таблица и словарь в Python имеют много общих черт, но есть и некоторые отличия:

Хэш-таблица	Словарь
Изначально пуст	Изначально пуст
Может содержать несколько элементов с одним и тем же ключом	Ключи должны быть уникальными
Быстрое время доступа к элементам	Быстрое время доступа к элементам
Неупорядоченный набор итерируемых элементов	Неупорядоченный набор итерируемых элементов
Более легкая и практически неограниченная вместимость	Легкое изменение размера и ограниченная емкость

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

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

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

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

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

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

Изучение встроенной функции hash() в Python

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

hashable = hash("Python")
print(hashable)  # Вывод: 139542455672688

Глубокий анализ функции hash() в Python

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

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

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

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

Хэш-код объекта - это целое число, которое идентифицирует объект внутри хэш-таблицы. За тем, как генерируется хэш-код, отвечает хэш-функция. Однако, не следует считать, что два объекта равны только потому, что их хэш-коды совпадают. Совпадение хэш-кодов не гарантирует идентичность объектов.

a = 12345
b = 12345
print(a == b)  # Вывод: True
print(hash(a) == hash(b))  # Вывод: True

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

def custom_hash(s):
    """
    Функция принимает строку и возвращает сумму кодов всех символов
    """
    return sum(ord(c) for c in s)

print(custom_hash("Python"))  # Вывод: 628

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

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

Краткий курс по разработке через тестирование (TDD)

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

Определение собственного класса HashTable

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def _hash_function(self, key):
        """Хэш-функция"""
        return len(key) % self.size

    def insert(self, key, value):
        """Вставка пары 'ключ-значение'"""
        index = self._hash_function(key)
        self.table[index] = value

    def get(self, key):
        """Получение значения по ключу"""
        index = self._hash_function(key)
        return self.table[index]

hashtable = HashTable(10)
hashtable.insert("name", "John")
print(hashtable.get("name"))  # Вывод: John

Добавление функциональности хэш-таблицы

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def _hash_function(self, key):
        """Хэш-функция"""
        return len(key) % self.size

    def insert(self, key, value):
        """Вставка пары 'ключ-значение'"""
        index = self._hash_function(key)
        self.table[index] = value

    def get(self, key):
        """Получение значения по ключу"""
        index = self._hash_function(key)
        return self.table[index]

    def delete(self, key):
        """Удаление пары 'ключ-значение'"""
        index = self._hash_function(key)
        self.table[index] = None

    def update(self, key, value):
        """Обновление значения по ключу"""
        index = self._hash_function(key)
        if self.table[index] is not None:
            self.table[index] = value

    def get_keys(self):
        """Получение всех ключей"""
        keys = []
        for item in self.table:
            if item is not None:
                keys.append(item)
        return keys

    def get_values(self):
        """Получение всех значений"""
        values = []
        for item in self.table:
            if item is not None:
                values.append(item)
        return values

    def report_length(self):
        """Получение длины хэш-таблицы"""
        count = 0
        for item in self.table:
            if item is not None:
                count += 1
        return count

    def make_iterable(self):
        """Сделать хэш-таблицу итерируемой"""
        return iter(self.table)

    def represent_text(self):
        """Вывод текстового представления хэш-таблицы"""
        text = ""
        for item in self.table:
            if item is not None:
                text += str(item) + "\n"
        return text

hashtable = HashTable(10)
hashtable.insert("name", "John")
hashtable.insert("age", 25)
hashtable.update("age", 30)
hashtable.delete("name")
print(hashtable.get("age"))  # Вывод: 30
print(hashtable.get_keys())  # Вывод: ['age']
print(hashtable.get_values()) # Вывод: [30]
print(hashtable.report_length)  # Вывод: 1
print(list(hashtable.make_iterable()))  # Вывод: [30]
print(hashtable.represent_text())  # Вывод: 30

Тестирование эквивалентности хэш-таблиц

class HashTable:
    # ...

    def __eq__(self, other):
        """Тестирование эквивалентности хэш-таблиц"""
        if isinstance(other, HashTable):
            return self.table == other.table
        return False

hashtable1 = HashTable(10)
hashtable2 = HashTable(10)
hashtable1.insert("name", "John")
hashtable2.insert("name", "John")
print(hashtable1 == hashtable2)  # Вывод: True

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

class HashTable:
    # ...

    def _linear_probing(self, index):
        """Нахождение свободной ячейки с использованием линейного пробирования"""
        while self.table[index] is not None:
            index = (index + 1) % self.size
        return index

    def _separate_chaining(self, index):
        """Изолирование коллизий через метод цепочек"""
        if self.table[index] is None:
            self.table[index] = []
        return index

    def resize(self):
        """Автоматическое изменение размера хэш-таблицы"""
        pass

hashtable = HashTable(10)
print(hashtable._linear_probing(0))  # Вывод: 0
print(hashtable._separate_chaining(0))  # Вывод: 0

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

from collections import OrderedDict

class HashTable:
    # ...

    def __init__(self, size):
        self.size = size
        self.table = OrderedDict([(i, None) for i in range(size)])

    # ...

hashtable = HashTable(10)
hashtable.insert("name", "John")
hashtable.insert("age", 25)
print(hashtable.get_keys())  # Вывод: ['name', 'age']

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

class HashTable:
    # ...

    def insert(self, key, value):
        """Вставка пары 'ключ-значение'"""
        if isinstance(key, Hashable):
            index = self._hash_function(key)
            self.table[index] = value
        else:
            raise TypeError("Key must be hashable.")

    # ...

hashtable = HashTable(10)
hashtable.insert("name", "John")
hashtable.insert(123, "number")  # Raises TypeError

Заключение

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