engl.: hash table

Seien

• S die Menge der möglichen Schlüsselwerte (Schlüsselraum) und
• A die Menge von Adressen in einer Hashtabelle (im Folgenden ist A immer die Indexmenge 0 … m − 1 eines Feldes).

Eine Hashfunktion h : S → A ordnet jedem Schlüssel eine Adresse in der Hashtabelle zu.

Als Hashtabelle (HT) der Größe m bezeichnen wir einen Speicherbereich, auf den über die Adressen aus A mit konstantem Aufwand (also unabhängig von m) zugegriffen werden kann.