Принципи роботи хеш-таблиць

6.1 Визначення хеш-таблиці та її структура

Хеш-таблиця – це структура даних, яка надає можливість швидко знаходити, вставляти і видаляти елементи з використанням хеш-функції для обчислення індексів в масиві або списку. Хеш-таблиці зазвичай використовуються для реалізації асоціативних масивів, також відомих як словники.

Важливі аспекти хеш-таблиці

Масив – це основний компонент хеш-таблиці, він зберігає вказівники на елементи або списки елементів.

Хеш-функція: Функція, яка перетворює ключі словника в індекси масиву.

Колізії: Ситуація, коли два різних ключі мають однакове хеш-значення. Для вирішення колізій використовуються різні методи, такі як ланцюжки (chaining) або відкрита адресація (open addressing).

Приклад словника:

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

Приклад структури хеш-таблиці:

6.2 Основні операції в хеш-таблиці

Основні операції в хеш-таблиці: вставка, пошук, видалення

1. Вставка (Insertion): Процес додавання нового елемента (пари ключ-значення) в хеш-таблицю.

Кроки вставки:

1. Обчислити хеш-значення ключа за допомогою хеш-функції.
2. Знайти індекс в масиві на основі хеш-значення.
3. Якщо в масиві за цим індексом вже є елемент (колізія), додати елемент в список (у випадку ланцюжків) або знайти наступний доступний індекс (у випадку відкритої адресації).

Приклад вставки в хеш-таблицю з використанням ланцюжків:

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

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

# Приклад використання:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Пошук (Search): Процес знаходження значення за заданим ключем в хеш-таблиці.

Кроки пошуку:

1. Обчислити хеш-значення ключа за допомогою хеш-функції.
2. Знайти індекс в масиві на основі хеш-значення.
3. Перевірити наявність ключа в списку елементів (у випадку ланцюжків) або за індексом (у випадку відкритої адресації).

Приклад пошуку в хеш-таблиці з використанням ланцюжків:

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

    def hash_function(self, key):
        return hash(key) % self.size

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# Приклад використання:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Вивід: 2
print(hash_table.search("grape"))   # Вивід: None

3. Видалення (Deletion): Процес видалення елемента (пари ключ-значення) з хеш-таблиці.

Кроки видалення:

1. Обчислити хеш-значення ключа за допомогою хеш-функції.
2. Знайти індекс в масиві на основі хеш-значення.
3. Видалити елемент зі списку (у випадку ланцюжків) або встановити значення за індексом в None (у випадку відкритої адресації).

Приклад видалення з хеш-таблиці з використанням ланцюжків:

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

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# Приклад використання:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # Вивід: None

6.3 Часова складність хеш-таблиці

Часова складність операцій в хеш-таблиці

Вставка (Insertion):

• Середній випадок: O(1)
• Найгірший випадок: O(n) (у випадку великої кількості колізій або якщо всі елементи потрапляють в одне і те ж місце)

Пошук (Search):

• Середній випадок: O(1)
• Найгірший випадок: O(n) (у випадку великої кількості колізій або якщо всі елементи потрапляють в одне і те ж місце)

Видалення (Deletion):

• Середній випадок: O(1)
• Найгірший випадок: O(n) (у випадку великої кількості колізій або якщо всі елементи потрапляють в одне і те ж місце)

Пояснення:

Середній випадок: У середньому випадку хеш-функція рівномірно розподіляє елементи по таблиці, і кожен елемент знаходиться в своїй унікальній ячейці, що забезпечує постійний час доступу O(1).

Найгірший випадок: У найгіршому випадку всі елементи потрапляють в одну ячейку через погану хеш-функцію або велику кількість колізій. Тоді хеш-таблиця перетворюється в зв'язний список, і часова складність операцій стає O(n).

6.4 Приклади використання хеш-таблиць

1. Реалізація словника (асоціативного масиву)

Хеш-таблиці часто використовуються для реалізації словників, які дозволяють зберігати пари ключ-значення і забезпечують швидкий доступ по ключу.

Приклад:

# Створення словника
dictionary = {}

# Вставка елементів
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Пошук елемента
print(dictionary["banana"])  # Вивід: 2

# Видалення елемента
del dictionary["cherry"]

# Перевірка існування ключа
if "apple" in dictionary:
    print("Ключ 'apple' існує в словнику")  # Вивід: Ключ 'apple' існує в словнику

Тепер ти трохи більше знаєш про словник у Python і як він влаштований.

2. Кешування результатів обчислень

Хеш-таблиці використовуються для кешування результатів дорогих обчислень для прискорення наступних запитів.

Приклад:

# Кеш для зберігання результатів
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Приклад дорогого обчислення
    cache[x] = result
    return result

# Використання кеша
print(expensive_computation(10))  # Вивід: 100 (обчислення і кешування)
print(expensive_computation(10))  # Вивід: 100 (з кеша)

3. Підрахунок частоти слів у тексті

Хеш-таблиці використовуються для підрахунку кількості входжень кожного слова в тексті.

Приклад:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# Вивід результатів
for word, count in word_count.items():
    print(f"Слово '{word}' зустрічається {count} раз(ів)")

4. Пошук дублікатів у списку

Хеш-таблиці використовуються для ефективного пошуку дублікатів у списку.

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Приклад використання
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Вивід: [2, 4]