No kādiem komponentiem sastāv hash tabula?

Hesšanas tabula sastāv no diviem galvenajiem komponentiem:

1. Masīvs (vai saraksts) šūnām (buckets): Tas ir galvenā glabāšanas struktūra. Katra šūna var saturēt vienu vai vairākus datu elementus (atslēgas-vērtības pāri).

2. Hesšanas funkcija: Algoritms, kas pārvērš ienākošo atslēgu skaitliskā indeksā, kas tiek izmantots, lai noteiktu, kur jāglabā vai jāatrod attiecīgais datu elements.

Turklāt, kolīziju (situāciju, kad dažādi atslēgas tiek hesētas uz vienu un to pašu indeksu) risināšanai tiek izmantoti šādi mehānismi:

• Ķēžu metode (chaining): Katras šūnas satur sarakstu (piemēram, saistītu sarakstu) elementiem, kas hesēti uz šo indeksu.
• Atvērtās adresēšanas metode (open addressing): Kolīzijas gadījumā algoritms meklē nākamo brīvo šūnu, sekojot noteiktai stratēģijai (vienkāršs meklējums, kvadrātveida meklējums, dubultā hesēšana).

# Vienkāršas hesšanas funkcijas piemērs
def simple_hash(key, array_size):
    # Pārvērst atslēgu skaitlī
    if isinstance(key, str):
        hash_value = sum(ord(char) for char in key)
    elif isinstance(key, int):
        hash_value = key
    else:
        raise TypeError("Nepalaidīgs atslēgas tips")

    # Atgriezt indeksu masīva robežās
    return hash_value % array_size

# Ķēžu metodes komponenta piemērs
class HashTable:
    def __init__(self, size):
        self.size = size
        self.array = [[] for _ in range(self.size)] # Saraksts ar sarakstiem (ķēdēm)

    def insert(self, key, value):
        index = simple_hash(key, self.size)
        self.array[index].append((key, value)) # Pievienot atslēgas-vērtības pāri sarakstam

    def search(self, key):
        index = simple_hash(key, self.size)
        for k, v in self.array[index]:
            if k == key:
                return v
        return None # Atslēga nav atrasta