Хеш-таблиця
Сховище ключ-значення з O(1) пошуком через хеш-функцію.
A hash table (or hash map) is a structure that can map keys to values. A hash table uses a hash [function](/uk/terms/hash-function) to compute an index into an array of buckets or slots, from which the desired value can be found. In an ideal case, the hash function will assign each key to a unique bucket, but most hash table designs employ some form of collision resolution.
graph LR
Center["Хеш-таблиця"]:::main
Rel_index_database["index-database"]:::related -.-> Center
click Rel_index_database "/terms/index-database"
Rel_relational_database["relational-database"]:::related -.-> Center
click Rel_relational_database "/terms/relational-database"
Rel_object["object"]:::related -.-> Center
click Rel_object "/terms/object"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧠 Перевірка знань
🧒 Простими словами
Уяви гардероб у театрі. Ти даєш пальто і отримуєш номерок. Коли хочеш забрати пальто, даєш номер, і гардеробник йде прямо до потрібного місця. Хеш-таблиці працюють так само — 'номерок' обчислюється з твого ключа!
🤓 Expert Deep Dive
Ідеальне хешування гарантує O(1) для статичних наборів. Cuckoo hashing досягає O(1) у гіршому випадку для пошуку. Robin Hood hashing зменшує дисперсію. Swiss Tables (Google) використовують SIMD. Узгоджене хешування (Consistent hashing) мінімізує переміщення даних при зміні розміру кластера.