Waaruit bestaat een hash-tabel?

Een hashtabel bestaat uit twee hoofdcomponenten:

1. Array (of lijst) van cellen (bakken): Dit is de hoofdstructuur voor opslag. Elke cel kan één of meerdere gegevensitems bevatten (sleutel-waardeparen).

2. Hashfunctie: Een algoritme dat de invoersleutel omzet in een numerieke index, die wordt gebruikt om te bepalen in welke cel het bijbehorende gegevensitem moet worden opgeslagen of gevonden.

Daarnaast worden mechanismen gebruikt om collisions op te lossen (situaties waarin verschillende sleutels naar dezelfde index hashen), zoals:

• Kettingmethode: In elke cel wordt een lijst (bijvoorbeeld een gekoppelde lijst) van elementen opgeslagen die naar die index zijn gehasht.
• Open adressering: Bij een collision zoekt het algoritme de volgende vrije cel volgens een bepaalde strategie (lineair zoeken, kwadratisch zoeken, dubbele hashing).

# Voorbeeld van een eenvoudige hashfunctie
def simple_hash(sleutel, array_grootte):
    # Converteer de sleutel naar een getal
    if isinstance(sleutel, str):
        hash_waarde = sum(ord(karakter) for karakter in sleutel)
    elif isinstance(sleutel, int):
        hash_waarde = sleutel
    else:
        raise TypeError("Niet-ondersteund sleuteltype")

    # Geef de index terug binnen de array grootte
    return hash_waarde % array_grootte

# Voorbeeld van een component van de array van cellen voor de kettingmethode
class HashTable:
    def __init__(self, grootte):
        self.grootte = grootte
        self.array = [[] for _ in range(self.grootte)] # Array van lijsten (kettingen)

    def insert(self, sleutel, waarde):
        index = simple_hash(sleutel, self.grootte)
        self.array[index].append((sleutel, waarde)) # Voeg het paar sleutel-waarde toe aan de lijst

    def search(self, sleutel):
        index = simple_hash(sleutel, self.grootte)
        for k, v in self.array[index]:
            if k == sleutel:
                return v
        return None # Sleutel niet gevonden