Реализация хеш-таблицы в 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).

Заключение

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

Читайте также:  Удалить элементы, превышающие определенное значение, из списка в Python
Оцените статью
bestprogrammer.ru
Добавить комментарий