Массив бакетов; ключ хешируется в индекс. Коллизии: chaining (список в бакете) или open addressing. В среднем O(1) для вставки и поиска. Load factor влияет на производительность.