Zasady działania tablic haszujących

6.1 Definicja i struktura tablicy haszującej

Tablica haszująca to struktura danych, która umożliwia szybkie znajdowanie, wstawianie i usuwanie elementów za pomocą funkcji haszującej do obliczania indeksów w tablicy lub liście. Tablice haszujące są często używane do implementacji tablic asocjacyjnych, znanych również jako słowniki.

Ważne aspekty tablicy haszującej

Tablica to podstawowy składnik tablicy haszującej, przechowuje wskaźniki na elementy lub listy elementów.

Funkcja haszująca: Funkcja, która przekształca klucze słownika na indeksy w tablicy.

Kolidacje: Sytuacja, gdy dwa różne klucze mają tę samą wartość haszującą. Do rozwiązywania kolizji stosowane są różne metody, takie jak łańcuchy (chaining) czy otwarte adresowanie (open addressing).

Przykład słownika:

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

Przykład struktury tablicy haszującej:

6.2 Podstawowe operacje w tablicy haszującej

Podstawowe operacje w tablicy haszującej: wstawianie, wyszukiwanie, usuwanie

1. Wstawianie (Insertion): Proces dodawania nowego elementu (pary klucz-wartość) do tablicy haszującej.

Kroki wstawiania:

1. Oblicz wartość haszującą klucza za pomocą funkcji haszującej.
2. Znajdź indeks w tablicy na podstawie wartości haszującej.
3. Jeśli w tablicy pod tym indeksem już jest element (kolizja), dodaj element do listy (w przypadku łańcuchów) lub znajdź następny dostępny indeks (w przypadku otwartego adresowania).

Przykład wstawiania do tablicy haszującej z użyciem łańcuchów:

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))

# Przykład użycia:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Wyszukiwanie (Search): Proces znajdowania wartości dla danego klucza w tablicy haszującej.

Kroki wyszukiwania:

1. Oblicz wartość haszującą klucza za pomocą funkcji haszującej.
2. Znajdź indeks w tablicy na podstawie wartości haszującej.
3. Sprawdź obecność klucza w liście elementów (w przypadku łańcuchów) lub pod indeksem (w przypadku otwartego adresowania).

Przykład wyszukiwania w tablicy haszującej z użyciem łańcuchów:

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

# Przykład użycia:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Wyjście: 2
print(hash_table.search("grape"))   # Wyjście: None

3. Usuwanie (Deletion): Proces usuwania elementu (pary klucz-wartość) z tablicy haszującej.

Kroki usuwania:

1. Oblicz wartość haszującą klucza za pomocą funkcji haszującej.
2. Znajdź indeks w tablicy na podstawie wartości haszującej.
3. Usuń element z listy (w przypadku łańcuchów) lub ustaw wartość pod indeksem na None (w przypadku otwartego adresowania).

Przykład usuwania z tablicy haszującej z użyciem łańcuchów:

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

# Przykład użycia:
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"))  # Wyjście: None

6.3 Złożoność czasowa tablicy haszującej

Złożoność czasowa operacji w tablicy haszującej

Wstawianie (Insertion):

• Przeciętny przypadek: O(1)
• Najgorszy przypadek: O(n) (w przypadku dużej liczby kolizji lub gdy wszystkie elementy trafiają w to samo miejsce)

Wyszukiwanie (Search):

• Przeciętny przypadek: O(1)
• Najgorszy przypadek: O(n) (w przypadku dużej liczby kolizji lub gdy wszystkie elementy trafiają w to samo miejsce)

Usuwanie (Deletion):

• Przeciętny przypadek: O(1)
• Najgorszy przypadek: O(n) (w przypadku dużej liczby kolizji lub gdy wszystkie elementy trafiają w to samo miejsce)

Wyjaśnienie:

Przeciętny przypadek: W przeciętnym przypadku funkcja haszująca równomiernie rozkłada elementy po tablicy, a każdy element znajduje się w swojej unikalnej komórce, co zapewnia stały czas dostępu O(1).

Najgorszy przypadek: W najgorszym przypadku wszystkie elementy trafiają do jednej komórki z powodu słabej funkcji haszującej lub dużej liczby kolizji. Wtedy tablica haszująca przekształca się w listę wiązaną, a złożoność czasowa operacji staje się O(n).

6.4 Przykłady użycia tablic haszujących

1. Implementacja słownika (tablicy asocjacyjnej)

Tablice haszujące są często używane do implementacji słowników, które pozwalają przechowywać pary klucz-wartość i zapewniają szybki dostęp po kluczu.

Przykład:

# Tworzenie słownika
dictionary = {}

# Wstawianie elementów
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Wyszukiwanie elementu
print(dictionary["banana"])  # Wyjście: 2

# Usuwanie elementu
del dictionary["cherry"]

# Sprawdzanie istnienia klucza
if "apple" in dictionary:
    print("Klucz 'apple' istnieje w słowniku")  # Wyjście: Klucz 'apple' istnieje w słowniku

Teraz już trochę więcej wiesz o słowniku w Pythonie i o tym, jak jest zbudowany.

2. Cache'owanie wyników obliczeń

Tablice haszujące są używane do cache'owania wyników kosztownych obliczeń w celu przyspieszenia kolejnych zapytań.

Przykład:

# Cache do przechowywania wyników
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Przykład kosztownego obliczenia
    cache[x] = result
    return result

# Użycie cache
print(expensive_computation(10))  # Wyjście: 100 (obliczenie i cache'owanie)
print(expensive_computation(10))  # Wyjście: 100 (z cache)

3. Liczenie częstotliwości słów w tekście

Tablice haszujące są używane do liczenia liczby wystąpień każdego słowa w tekście.

Przykład:

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

# Wyjście wyników
for word, count in word_count.items():
    print(f"Słowo '{word}' występuje {count} raz(y)")

4. Wyszukiwanie duplikatów w liście

Tablice haszujące są używane do efektywnego wyszukiwania duplikatów w liście.

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

# Przykład użycia
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Wyjście: [2, 4]