Map - хеш-таблица: массив бакетов, каждый бакет содержит до 8 пар ключ-значение и указатель на overflow-бакеты при коллизиях. Хеш ключа определяет бакет; при переполнении таблица растёт (примерно в 2 раза) и данные рехешируются.