hash table

RU: хеш-таблица

A data structure that maps keys to values by applying a hash function to derive an array index, giving average O(1) insert, lookup, and delete. Collisions are resolved by chaining (a linked list at each bucket) or open addressing (probing for the next free slot); worst-case degrades to O(n) under many collisions.