Millest komponentidest koosneb hash-tabel?

Hash-tabel koosneb kahest põhikomponendist:

1. Massiiv (või nimekiri) kottidest (buckets): See on peamine salvestusstruktuur. Iga kott võib sisaldada ühte või mitut andmeelementi (võti-väärtus paar).

2. Hash-funktsioon: Algoritm, mis teisendab sisendi võtme arvuliseks indeksiks, mida kasutatakse vastava elemendi salvestamiseks või leidmiseks kotis.

Lisaks kasutatakse kokkupõrgete (olukordade, kus erinevad võtmed hash'itakse sama indeksisse) lahendamiseks järgmisi mehhanisme:

• Kettide meetod (chaining): Igas kotis hoitakse loend (näiteks seotud loend) elementidest, mis on hash'itud selle indeksi alla.
• Ava aadressimise meetod (open addressing): Kokkupõrke korral otsib algoritm järgmise vaba kasti, järgides määratletud strateegiat (jooneline otsing, kvadratuurne otsing, topelt-hashimine).

# Näide lihtsast hash-funktsioonist
def simple_hash(key, array_size):
    # Muutke võti arvuks
    if isinstance(key, str):
        hash_value = sum(ord(char) for char in key)
    elif isinstance(key, int):
        hash_value = key
    else:
        raise TypeError("Toetamata võti tüüp")

    # Tagastage indeks massiivi suuruse piires
    return hash_value % array_size

# Kettide meetodi komponendi näide
class HashTable:
    def __init__(self, size):
        self.size = size
        self.array = [[] for _ in range(self.size)] # Loend loendist (kettidest)

    def insert(self, key, value):
        index = simple_hash(key, self.size)
        self.array[index].append((key, value)) # Lisa võti-väärtuspaar loendisse

    def search(self, key):
        index = simple_hash(key, self.size)
        for k, v in self.array[index]:
            if k == key:
                return v
        return None # Võti ei leitud