Problemy kolizji i metody ich rozwiązywania

7.1 Definicja kolizji w tabeli haszującej

Kolizja w tabeli haszującej występuje, gdy dwa różne klucze są haszowane do tego samego indeksu tablicy. To oznacza, że więcej niż jeden element próbuje zająć tę samą komórkę w tabeli haszującej.

Przykład kolizji:

Załóżmy, że mamy prostą funkcję haszującą, która zwraca resztę z dzielenia klucza przez rozmiar tabeli. Dla kluczy 5 i 15 przy rozmiarze tabeli 10 oba klucze dadzą ten sam indeks: 5 % 10 = 5 i 15 % 10 = 5. To jest kolizja.

Kolejny przykład:

Załóżmy, że tworzysz słownik imion i masz prostą funkcję haszującą, która zwraca pierwszą literę imienia. Ale okazuje się, że 80% imion zaczyna się na literę „A”. To nie tylko kolizja, to problem.

7.2 Metody rozwiązywania kolizji – łańcuchy

Istnieje kilka metod rozwiązywania kolizji w tabelach haszujących. Dwa najbardziej powszechne to łańcuchy (chaining) i otwarte adresowanie (open addressing).

Łańcuchy (Chaining)

Zalety:

• Prostota implementacji.
• Efektywność przy niewielkiej liczbie kolizji.
• Mniejsza zależność od gęstości wypełnienia tabeli haszującej.

Wady:

• Wymaga dodatkowej pamięci dla wskaźników w liście wiązanej.
• Wydajność może spadać przy dużej liczbie kolizji z powodu długich łańcuchów.

Przykład implementacji metody łańcuchów:

Możesz tylko przeanalizować funkcję insert, ale podaję cały kod dla wygody.

class HashTableChaining:
    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 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

    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

# Przykład użycia:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Wynik: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Wynik: None

7.3 Metoda numer dwa – otwarte adresowanie

Metoda otwartego adresowania polega na poszukiwaniu kolejnej dostępnej komórki w tablicy, jeśli występuje kolizja. Istnieją różne strategie znajdowania nowej komórki: liniowe próbkowanie, kwadratowe próbkowanie i podwójne haszowanie.

Zalety:

• Nie wymaga dodatkowej pamięci do przechowywania wskaźników.
• Bardziej kompaktowe przedstawienie danych.

Wady:

• Wydajność może znacznie spadać przy wysokiej gęstości wypełnienia tabeli.
• Wymaga więcej zasobów obliczeniowych do rozwiązywania kolizji.

Przykłady strategii otwartego adresowania

Liniowe próbkowanie (Linear Probing):

• Próbkowanie z krokiem 1: index = (index + 1) % size.
• Proste, ale może prowadzić do "klasteryzacji".

Kwadratowe próbkowanie (Quadratic Probing):

• Próbkowanie z krokiem zwiększającym się kwadratowo: index = (index + i^2) % size.
• Zmniejsza problem klasteryzacji, ale jest trudniejszy do zaimplementowania.

Podwójne haszowanie (Double Hashing):

• Użycie drugiej funkcji haszującej do obliczania kroku: index = (index + i * hash2(key)) % size.
• Mniej problemów z klasteryzacją, ale trudniejsza implementacja.

Przykład implementacji metody otwartego adresowania (liniowe próbkowanie): Podaję cały działający kod, dla prostoty możesz przeanalizować tylko funkcję insert

class HashTableOpenAddressing:
    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)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

# Przykład użycia:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Wynik: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Wynik: None

7.4 Wpływ kolizji na tabelę haszującą

Wpływ kolizji na wydajność.

Średni czas dostępu:

• W idealnych warunkach (bez kolizji) średni czas dostępu do elementów w tabeli haszującej wynosi O(1).
• Kolizje zwiększają czas dostępu, ponieważ wymagana jest obsługa łańcuchów lub próbkowanie komórek, co zwiększa liczbę operacji.

Zwiększenie długości łańcuchów:

• W metodzie łańcuchów zwiększenie długości łańcuchów przy dużej liczbie kolizji może prowadzić do liniowego czasu dostępu O(n) dla operacji wyszukiwania, wstawiania i usuwania.
• Długie łańcuchy zwiększają liczbę porównań potrzebnych do znalezienia lub wstawienia elementu.

Złożoność przestrzenna:

• W metodzie łańcuchów wymagana jest dodatkowa pamięć do przechowywania wskaźników w listach wiązanych.
• W metodzie otwartego adresowania wypełnienie tabeli powyżej określonego poziomu (zwykle około 70-80%) znacznie zwiększa liczbę kolizji i tym samym czas dostępu.

Klasteryzacja: W metodzie otwartego adresowania (szczególnie przy liniowym próbkowaniu) występuje klasteryzacja, gdy kilka kolejnych komórek staje się zajętych, co zwiększa prawdopodobieństwo kolizji i pogarsza wydajność.

Przykład analizy wpływu kolizji na wydajność:

To dla tych, którzy lubią zagłębiać się głębiej

import time
import random

# Liniowe próbkowanie
class HashTableOpenAddressing:
    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)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

# Generowanie dużej ilości danych do wstawienia
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# Wstawianie danych i mierzenie czasu
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"Czas wstawiania: {time.time() - start_time:.6f} sekund")

# Wyszukiwanie danych i mierzenie czasu
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"Czas wyszukiwania: {time.time() - start_time:.6f} sekund")