Хэш-таблицы в Python

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

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

Определение хеш-таблиц: структура данных пары ключ-значение

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

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

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

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

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

+-----------------------+
|   Key   |   Value     |
+-----------------------+
| Alice   | January     |
| Bob     | May         |
| Charlie | January     |
| David   | August      |
| Eve     | December    |
| Brian   | May         |
+-----------------------+

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

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

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

def simple_hash(key, array_size):
    return ord(key[0]) % array_size

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

Например, предположим, что наш массив имеет размер 10, запуск simple_hash(key, 10)для каждого из наших ключей даст нам:

В качестве альтернативы мы можем изменить эти данные более лаконично:

+---------------------+
|   Key   |   Index   |
+---------------------+
| Alice   |     5     |
| Bob     |     6     |
| Charlie |     7     |
| David   |     8     |
| Eve     |     9     |
| Brian   |     6     |
+---------------------+

Здесь Bob и Brian в результирующем массиве будут одинаковые индексы, что и приводит к коллизии . Мы поговорим о коллизиях подробнее в последних разделах — как с точки зрения создания хеш-функций, которые минимизируют вероятность коллизий, так и с точки зрения разрешения коллизий, когда они происходят.

Разработка надежных хеш-функций — один из наиболее важных аспектов эффективности хеш-таблицы!

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

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

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

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

Что такое хеш-функция?

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

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

Роль хэш-функций в хеш-таблицах

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

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

+-----------------------+
|   Key   |   Value     |
+-----------------------+
| Alice   | January     |
| Bob     | May         |
| Charlie | January     |
| David   | August      |
| Eve     | December    |
| Brian   | May         |
+-----------------------+

Как и раньше, предположим, что у нас есть хеш-функция simple_hash(key) и хеш-таблица размера 10.

Как мы видели ранее, выполнение, скажем, "Alice" функции simple_hash() возвращает индекс 5. Это означает, что мы можем найти элемент с ключом "Alice"и значением "January"в массиве, представляющем хеш-таблицу, по индексу 5(6-й элемент этого массива):

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

+---------------------+
|   Key   |   Index   |
+---------------------+
| Alice   |     5     |
| Bob     |     6     |
| Charlie |     7     |
| David   |     8     |
| Eve     |     9     |
| Brian   |     6     |
+---------------------+

Это можно легко преобразовать в массив, представляющий хеш-таблицу — элемент с ключом "Alice" будет храниться под индексом 5, "Bob" под индексом 6 и так далее:

Примечание. Под индексом 6 находятся два элемента — {"Bob", "February"}и {"Brian", "May"}. На иллюстрации выше эта коллизия была решена с помощью метода, называемого раздельной цепочкой , о котором мы поговорим подробнее позже в этой статье.

Когда мы хотим получить значение, связанное с ключом "Alice", мы снова передаем ключ хеш-функции, которая возвращает индекс 5. Затем мы немедленно получаем доступ к значению по индексу 3хеш-таблицы, то есть "January".

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

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

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

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

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

Анализ временной сложности хеш-таблиц: сравнение

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

При обсуждении временной сложности мы обычно имеем в виду три случая:

1. Лучший вариант: минимальное время, необходимое для выполнения операции.
2. Средний случай: среднее время, необходимое для выполнения операции.
3. Худший случай: максимальное время, необходимое для выполнения операции.

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

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

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

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

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

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

Сравнение с другими структурами данных

По сравнению с другими структурами данных хеш-таблицы выделяются своей эффективностью . Например, такие операции, как поиск, вставка и удаление в сбалансированном двоичном дереве поиска или сбалансированном дереве AVL, имеют временную сложность O(log n) , что, хотя и неплохо, но не так эффективно, как время O(1). сложность, которую предлагают хеш-таблицы в среднем случае.

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

Подход Python к хэш-таблицам: введение в словари

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

Что такое словари?

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

Пара ключ-значение в словаре также называется элементом. Каждый ключ в словаре связан (или сопоставлен) с одним значением, образуя пару ключ-значение:

my_dict = {"Alice": "January", "Bob": "May", "Charlie": "January"}

Как словари работают в Python?

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

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

my_dict = {}
my_dict["Alice"] = "January" # Hash function determines the location for "January"
print(my_dict["Alice"]) # "January"

Ключевые операции и временная сложность

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

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

Вставить пары ключ-значение в словарь Python очень просто. Вы просто присваиваете значение ключу с помощью оператора присваивания ( =). Если ключ еще не существует в словаре, он добавляется. Если он существует, его текущее значение заменяется новым значением:

my_dict = {}
my_dict["Alice"] = "January"
my_dict["Bob"] = "May"

print(my_dict)  # Outputs: {'Alice': 'January', 'Bob': 'May'}

Получить доступ к значению в словаре Python так же просто, как и вставить его. Вы можете получить доступ к значению, связанному с определенным ключом, указав ключ в квадратных скобках. Если вы попытаетесь получить доступ к ключу, которого нет в словаре, Python выдаст ошибку KeyError:

print(my_dict["Alice"])  # Outputs: Python

# Raises KeyError: 'Charlie'
print(my_dict["Charlie"])

Чтобы предотвратить эту ошибку, вы можете использовать метод словаря get(), который позволяет вернуть значение по умолчанию, если ключ не существует:

print(my_dict.get("Charlie", "Unknown"))  # Outputs: Unknown

Примечание. Аналогичным образом этот setdefault() метод можно использовать для безопасной вставки пары ключ-значение в словарь, если ключ еще не существует:

my_dict.setdefault("new_key", "default_value")

Вы можете удалить пару ключ-значение из словаря Python, используя delключевое слово. Если ключ существует в словаре, он удаляется вместе со своим значением. Если ключ не существует, Python также вызовет KeyError:

del my_dict["Bob"]
print(my_dict)  # Outputs: {'Alice': 'January'}

# Raises KeyError: 'Bob'
del my_dict["Bob"]

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

print(my_dict.pop("Bob", "Unknown"))  # Outputs: Unknown

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

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

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

Как создать свою первую хеш-таблицу в Python

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

Начнем с определения HashTable класса. Хэш-таблица будет представлена ​​списком ( ) table, и мы будем использовать очень простую хэш-функцию, которая вычисляет остаток от значения ASCII первого символа ключевой строки, деленный на размер таблицы:

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

    def _hash(self, key):
        return ord(key[0]) % self.size

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

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

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

    def _hash(self, key):
        return ord(key[0]) % self.size

    def set(self, key, value):
        hash_index = self._hash(key)
        self.table[hash_index] = (key, value)

    def get(self, key):
        hash_index = self._hash(key)
        if self.table[hash_index] is not None:
            return self.table[hash_index][1]

        raise KeyError(f'Key {key} not found')

    def remove(self, key):
        hash_index = self._hash(key)
        if self.table[hash_index] is not None:
            self.table[hash_index] = None
        else:
            raise KeyError(f'Key {key} not found')

Метод set() добавляет в таблицу пару ключ-значение, а get() метод извлекает значение по ее ключу. Метод remove() удаляет пару ключ-значение из хеш-таблицы.

Примечание. Если ключ не существует, методы get и remove создают объект KeyError.

Теперь мы можем создать хеш-таблицу и использовать ее для хранения и извлечения данных:

# Create a hash table of size 10
hash_table = HashTable(10)

# Add some key-value pairs
hash_table.set('Alice', 'January')
hash_table.set('Bob', 'May')

# Retrieve a value
print(hash_table.get('Alice'))  # Outputs: 'January'

# Remove a key-value pair
hash_table.remove('Bob')

# This will raise a KeyError, as 'Bob' was removed
print(hash_table.get('Bob'))

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

Разрешение коллизий в хэш-таблицах Python

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

Встроенная реализация хэш-таблицы Python использует метод, называемый «открытой адресацией», для обработки коллизий хэшей. Однако, чтобы лучше понять процесс разрешения коллизий, давайте обсудим более простой метод, называемый «раздельная цепочка» .

Отдельная цепочка

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

Помните, в нашем примере произошло столкновение, поскольку оба "Bob" и "Brian" имели одинаковый индекс — 6. Давайте используем этот пример, чтобы проиллюстрировать механизм разделения цепочек. Если бы мы предположили, что "Bob" элемент был сначала добавлен в хеш-таблицу, мы столкнулись бы с проблемой при попытке сохранить элемент, "Brian" поскольку индекс 6 уже был занят.

Решение этой ситуации с использованием отдельной цепочки включало бы добавление элемента "Brian" в качестве второго элемента связанного списка, назначенного индексу 6(этот "Bob" элемент является первым элементом этого списка). И это все, что нужно, как показано на следующей иллюстрации:

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

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        return ord(key[0]) % self.size

    def set(self, key, value):
        hash_index = self._hash(key)
        for kvp in self.table[hash_index]:
            if kvp[0] == key:
                kvp[1] = value
                return

        self.table[hash_index].append([key, value])

    def get(self, key):
        hash_index = self._hash(key)
        for kvp in self.table[hash_index]:
            if kvp[0] == key:
                return kvp[1]

        raise KeyError(f'Key {key} not found')

    def remove(self, key):
        hash_index = self._hash(key)
        for i, kvp in enumerate(self.table[hash_index]):
            if kvp[0] == key:
                self.table[hash_index].pop(i)
                return

        raise KeyError(f'Key {key} not found')

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

Методам get() and remove() также необходимо перебирать связанный список по хешированному индексу, чтобы найти искомый ключ.

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

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

Метод, используемый словарями Python для обработки коллизий, более сложен, чем раздельное связывание. Python использует форму открытой адресации, называемую «зондированием» .

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

• Линейное зондирование – проверка одного слота за раз по порядку
• Квадратичное зондирование - проверка слотов по возрастанию степени двойки

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

Давайте просто кратко рассмотрим пример коллизии из предыдущего раздела и покажем, как бы мы поступили с ним, используя метод открытой адресации. Допустим, у нас есть хэш-таблица всего с одним элементом — {"Bob", "May"} по номеру индекса 6. Теперь мы не сможем добавить "Brian" элемент в хеш-таблицу из-за коллизии. Но механизм линейного зондирования говорит нам хранить его в первом пустом индексе — 7. Вот и все, легко, правда?

Заключение

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

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

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

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