Tablica mieszająca (hash map)
Struktura danych mapująca klucze na wartości w zamortyzowanym czasie O(1) — cegiełka stojąca za dict/HashMap/obiektem w niemal każdym języku.
Funkcja skrótu zamienia klucz na indeks koszyka. Kolizje obsługuje się przez łańcuchowanie (lista powiązana w każdym koszyku — domyślnie w HashMap z Javy) albo adresowanie otwarte (próbkowanie liniowe i kwadratowe — dict w Pythonie, map w Go, HashBrown w Ruście). Rozmiar zwiększa się, gdy współczynnik zapełnienia przekroczy ok. 0,75.
Przy złej funkcji skrótu pesymistycznie O(n). Ataki HashDoS (2011) zmusiły wszystkie języki do skrótów z losowym ziarnem (SipHash). Robin Hood hashing i hopscotch hashing to nowoczesne warianty z lepszą lokalnością cache.