Map в Go — это hash table. Под капотом массив бакетов, каждый бакет хранит до 8 пар ключ-значение. Ключ хешируется, по хешу определяется бакет. При коллизиях — overflow бакеты в цепочке. Когда load factor превышает порог, происходит инкрементальное расширение — аллоцируется новая таблица вдвое больше, и данные перемещаются постепенно. Порядок итерации рандомизирован специально, чтобы люди не зависели от него.