Z jakich komponent składa się tablica haszująca?

Tablica haszowa składa się z dwóch głównych komponentów:

1. Tablica (lub lista) komórek (kubełków): Jest to główna struktura przechowywania. Każda komórka może zawierać jeden lub więcej elementów danych (par klucz-wartość).

2. Funkcja haszująca: Algorytm, który przekształca klucz wejściowy w indeks numeryczny, używany do określenia komórki, w której powinien być przechowywany lub odnaleziony odpowiedni element danych.

Ponadto, do rozwiązywania kolizji (sytuacji, gdy różne klucze są haszowane do tego samego indeksu), stosuje się mechanizmy takie jak:

• Metoda łańcuchowa: W każdej komórce przechowywana jest lista (np. lista powiązana) elementów haszowanych do tego indeksu.
• Metoda otwartego adresowania: W przypadku kolizji, algorytm szuka następnej wolnej komórki, podążając za określoną strategią (liniowe próbkowanie, kwadratowe próbkowanie, podwójne haszowanie).

# Przykład prostej funkcji haszującej
def simple_hash(klucz, rozmiar_tablicy):
    # Przekształcenie klucza na liczbę
    if isinstance(klucz, str):
        wartosc_hash = sum(ord(znak) for znak in klucz)
    elif isinstance(klucz, int):
        wartosc_hash = klucz
    else:
        raise TypeError("Nieobsługiwany typ klucza")

    # Zwrócenie indeksu w zakresie rozmiaru tablicy
    return wartosc_hash % rozmiar_tablicy

# Przykład komponentu tablicy komórek dla metody łańcuchowej
class HashTable:
    def __init__(self, rozmiar):
        self.rozmiar = rozmiar
        self.array = [[] for _ in range(self.rozmiar)] # Tablica list (łańcuchy)

    def wstaw(self, klucz, wartosc):
        indeks = simple_hash(klucz, self.rozmiar)
        self.array[indeks].append((klucz, wartosc)) # Dodanie pary klucz-wartość do listy

    def szukaj(self, klucz):
        indeks = simple_hash(klucz, self.rozmiar)
        for k, v in self.array[indeks]:
            if k == klucz:
                return v
        return None # Klucz nie znaleziony