Реализация хеш-таблицы в Python с использованием отдельной цепочки

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

Компоненты хеширования

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

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

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

Создайте два класса: » Node » и » HashTable «.

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

Python3

class Node:

    def __init__(self, key, value):

        self.key = key

        self.value = value

        self.next = None

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

Python3

class HashTable:

    def __init__(self, capacity):

        self.capacity = capacity

        self.size = 0

        self.table = [None] * capacity

Метод __init__ инициализирует хеш-таблицу с заданной емкостью. Он устанавливает переменные » capacity » и » size » и инициализирует массив значением «None».

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

Python3

def _hash(self, key):

return hash(key) % self.capacity

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

Python3

def insert(self, key, value):

    index = self._hash(key)

    if self.table[index] is None:

        self.table[index] = Node(key, value)

        self.size += 1

    else:

        current = self.table[index]

        while current:

            if current.key == key:

                current.value = value

                return

            current = current.next

        new_node = Node(key, value)

        new_node.next = self.table[index]

        self.table[index] = new_node

        self.size += 1

Метод поиска извлекает значение, связанное с данным ключом. Сначала он получает индекс, в котором должна храниться пара ключ-значение, используя метод _hash. Затем он ищет ключ в связанном списке по этому индексу. Если он находит ключ, он возвращает связанное значение. Если он не находит ключ, он вызывает KeyError.

Python3

def search(self, key):

       index = self._hash(key)

       current = self.table[index]

       while current:

           if current.key == key:

               return current.value

           current = current.next

        raise KeyError(key)

Метод remove удаляет пару ключ-значение из хеш-таблицы. Сначала он получает индекс, где должна храниться пара, используя метод ` _hash`. Затем он ищет ключ в связанном списке по этому индексу. Если он находит ключ, он удаляет узел из списка. Если он не находит ключ, он вызывает ` KeyError`.

Python3

def remove(self, key):

        index = self._hash(key)

        previous = None

        current = self.table[index]

        while current:

            if current.key == key:

                if previous:

                    previous.next = current.next

                else:

                    self.table[index] = current.next

                self.size -= 1

                return

            previous = current

            current = current.next

        raise KeyError(key)

’__str__’, который возвращает строковое представление хеш-таблицы.

Python3

def __str__(self):

    elements = []

    for i in range(self.capacity):

        current = self.table[i]

        while current:

            elements.append((current.key, current.value))

            current = current.next

    return str(elements)

Вот полная реализация класса HashTable:

Python3

class Node:

    def __init__(self, key, value):

        self.key = key

        self.value = value

        self.next = None

class HashTable:

    def __init__(self, capacity):

        self.capacity = capacity

        self.size = 0

        self.table = [None] * capacity

    def _hash(self, key):

        return hash(key) % self.capacity

    def insert(self, key, value):

        index = self._hash(key)

        if self.table[index] is None:

            self.table[index] = Node(key, value)

            self.size += 1

        else:

            current = self.table[index]

            while current:

                if current.key == key:

                    current.value = value

                    return

                current = current.next

            new_node = Node(key, value)

            new_node.next = self.table[index]

            self.table[index] = new_node

            self.size += 1

    def search(self, key):

        index = self._hash(key)

        current = self.table[index]

        while current:

            if current.key == key:

                return current.value

            current = current.next

        raise KeyError(key)

    def remove(self, key):

        index = self._hash(key)

        previous = None

        current = self.table[index]

        while current:

            if current.key == key:

                if previous:

                    previous.next = current.next

                else:

                    self.table[index] = current.next

                self.size -= 1

                return

            previous = current

            current = current.next

        raise KeyError(key)

    def __len__(self):

        return self.size

    def __contains__(self, key):

        try:

            self.search(key)

            return True

        except KeyError:

            return False

# Driver code

if __name__ == '__main__':

    # Create a hash table with

    # a capacity of 5

    ht = HashTable(5)

    # Add some key-value pairs

    # to the hash table

    ht.insert("apple", 3)

    ht.insert("banana", 2)

    ht.insert("cherry", 5)

    # Check if the hash table

    # contains a key

    print("apple" in ht) # True

    print("durian" in ht) # False

    # Get the value for a key

    print(ht.search("banana")) # 2

    # Update the value for a key

    ht.insert("banana", 4)

    print(ht.search("banana")) # 4

    ht.remove("apple")

    # Check the size of the hash table

    print(len(ht)) # 3

Выход

True
False
2
4
3

Сложность времени и сложность пространства:

Временная сложность методов вставки, поиска и удаления в хэш-таблице с использованием отдельной цепочки зависит от размера хэш-таблицы, количества пар ключ-значение в хэш-таблице и длины связанного списка по каждому индексу.
Предполагая хорошую хеш-функцию и равномерное распределение ключей, ожидаемая временная сложность этих методов составляет O (1)для каждой операции. Однако в худшем случае временная сложность может быть O(n), где n — количество пар ключ-значение в хеш-таблице.
Однако важно выбрать хорошую хеш-функцию и подходящий размер хеш-таблицы, чтобы свести к минимуму вероятность коллизий и обеспечить хорошую производительность.
Сложность пространствахэш -таблицы с использованием отдельной цепочки зависит от размера хэш-таблицы и количества пар ключ-значение, хранящихся в хэш-таблице.
Сама хеш-таблица занимает O(m)пространства, где m — емкость хэш-таблицы. Каждый узел связанного списка занимает O(1) пространства, и в связанных списках может быть не более n узлов, где n — количество пар ключ-значение, хранящихся в хэш-таблице.
Следовательно, общая сложность пространства равна O(m + n).

Заключение

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