Millelt koosneb hash-tabel?

Hash-tabel koosneb fikseeritud suurusega massiivist (ämber või slot) ja hash-funktsioonist.

• Massiiv (Ämbrid/Slotid): Esindab järjestust, kus hoitakse "võti-väärtus" paare. Massiivi suurus määrab võimalike kohtade arvu elementide salvestamiseks.

• Hash-funktsioon: Muudab võtme täisarvuks (hash-kood), mida kasutatakse selleks, et määrata indeksi koht massiivis (ämbris), kus vastav väärtus salvestatakse või kust võetakse.

Lisaks võib olla:

• Kollisioonide lahendamise strateegia: Mehhanism olukordade jaoks, kus erinevad võtmed genereerivad sama hash-koodi ja viitavad samale massiivi kohale. Tüüpilised strateegiad:
  • Jadastamine (Separate Chaining): Iga massiivi koht hoiab viidet seotud nimekirjale (või muule andmestruktuurile), mis sisaldab kõiki "võti-väärtus" paare, mille hash-koodid viitavad sellele kohale.
  • Ava aadressimine: Kollisiooni korral otsitakse vaba kohta massiivis kindla reegli järgi (näiteks lineaarne või kvadraatne sondimine).