Hash Table (Hash Map)

Wprowadzenie

Hash Table (Hash Map) to struktura danych, która mapuje klucze na wartości za pomocą funkcji haszującej. Umożliwia wykonywanie operacji wyszukiwania, dodawania i usuwania elementów średnio w czasie stałym O(1), co czyni ją jedną z najszybszych struktur danych.

Jak działa Hash Table?

• Funkcja haszująca (hash function) przekształca klucz na indeks w tablicy
• Klucze o tym samym hashu trafiają do tego samego „koszyka” (bucket)
• W razie kolizji stosowane są metody rozwiązywania: chaining lub open addressing
• Automatyczne powiększanie tablicy przy wysokim współczynniku wypełnienia (load factor)

Metody rozwiązywania kolizji

• Separate Chaining – każdy bucket zawiera listę lub drzewo (najpopularniejsza)
• Open Addressing – Linear Probing, Quadratic Probing, Double Hashing
• Cuckoo Hashing – dwie tablice i dwie funkcje haszujące

Złożoność czasowa

• Średnia: O(1) dla insert, search, delete
• Najgorsza: O(n) przy wielu kolizjach (możliwe przy złej funkcji haszującej)
• Amortyzowana: O(1) dzięki rehashingowi

Hash Table w praktyce (2026)

• Python: dict i set
• JavaScript: Map i Object
• Java: HashMap, ConcurrentHashMap
• C++: std::unordered_map
• Bazy danych (indexy), cachowanie (Redis, Memcached), kompilatory, algorytmy AI

Zastosowanie w AI i uczeniu maszynowym

• Szybkie mapowanie tokenów na ID w tokenizerach LLM
• Implementacja embedding lookup tables
• Cachowanie wyników inferencji i promptów
• Feature stores i deduplikacja danych
• Hash-based nearest neighbor search (Locality-Sensitive Hashing)

Powiązane pojęcia

Hash Function • Collision Resolution • Load Factor • Separate Chaining • Open Addressing • Dictionary • Associative Array • Bloom Filter • Consistent Hashing • Redis • unordered_map