Хеш-таблицы

живой пример

import java.util.ArrayList;
import java.util.List;

public class Buckets {
    public static void main(String[] args) {
        int[] keys = {31, 9, 18, 25, 44, 12, 7, 20};
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 7; i++) buckets.add(new ArrayList<>());
        int collisions = 0;
        for (int key : keys) {
            List<Integer> bucket = buckets.get(key % 7);
            if (!bucket.isEmpty()) collisions++;
            bucket.add(key);
        }
        System.out.println("корзины: " + buckets);
        System.out.println("коллизий: " + collisions + " из " + keys.length);
    }
}

живой пример

package main

import "fmt"

func main() {
	keys := []int{31, 9, 18, 25, 44, 12, 7, 20}
	buckets := make([][]int, 7)
	collisions := 0
	for _, key := range keys {
		i := key % 7
		if len(buckets[i]) > 0 {
			collisions++
		}
		buckets[i] = append(buckets[i], key)
	}
	fmt.Println("корзины:", buckets)
	fmt.Printf("коллизий: %d из %d\n", collisions, len(keys))
}

живой пример

const keys = [31, 9, 18, 25, 44, 12, 7, 20];
const buckets = Array.from({ length: 7 }, () => []);
let collisions = 0;
for (const key of keys) {
  const bucket = buckets[key % 7];
  if (bucket.length > 0) collisions++;
  bucket.push(key);
}
console.log("корзины:", JSON.stringify(buckets));
console.log(`коллизий: ${collisions} из ${keys.length}`);

живой пример

keys = [31, 9, 18, 25, 44, 12, 7, 20]
buckets = [[] for _ in range(7)]
collisions = 0
for key in keys:
    bucket = buckets[key % 7]
    if bucket:
        collisions += 1
    bucket.append(key)
print("корзины:", buckets)
print(f"коллизий: {collisions} из {len(keys)}")

Свою хеш-таблицу писать почти никогда не нужно — в Java она уже есть. Важнее понимать, что именно берёте с полки: от этого зависит и скорость, и то, найдётся ли объект в таблице вообще.

Эталонная реализация — HashMap. Внутри у неё ровно то, о чём была статья: массив корзин и метод цепочек — записи, попавшие в одну корзину, лежат связанным списком. Номер корзины берут не остатком от деления, а дешёвой битовой операцией по младшим битам хеша: размер массива всегда степень двойки. Чтобы старшие биты не пропадали зря, HashMap сначала подмешивает их к младшим — если этого не делать, ключи с одинаковым «хвостом» хеша свалятся в одну корзину.

Коэффициент заполнения по умолчанию — 0.75: как только записей стало больше трёх четвертей от числа корзин, массив удваивается и все ключи раскладываются заново. Перестройка стоит O(n), поэтому под сто тысяч записей размер задают сразу в конструкторе — иначе таблица переживёт четырнадцать перестроек. Только число в конструкторе это ёмкость, а не число записей, и new HashMap<>(100_000) заведёт 131 072 корзины (ёмкость округляется до степени двойки) с порогом 98 304: на сотне тысяч записей перестройка всё равно случится. Правильно либо посчитать запас руками, new HashMap<>((int) (100_000 / 0.75) + 1), либо с Java 19 сказать прямо, сколько пар ожидается: HashMap.newHashMap(100_000), и он поделит на 0.75 сам.

Ещё одна деталь появилась в Java 8. Если в одну корзину набилось восемь записей, а корзин в таблице уже не меньше 64, список внутри корзины превращается в красно-чёрное дерево. Поиск внутри перегруженной корзины из O(k) становится O(log k) — это страховка от плохой хеш-функции и от специально подобранных данных, которые иначе вырождали бы таблицу в список.

Отсюда честная сложность. get и put — O(1) в среднем, при условии, что хеш-функция раскидывает ключи равномерно. Худший случай — не O(1), а O(log n) благодаря дереву в корзине, и то только если ключи сравнимы (Comparable); иначе HashMap упорядочивает их по запасному признаку, и выигрыш скромнее. Порядка обхода у HashMap нет вообще, и он вправе поменяться после любого расширения — если порядок вставки нужен, берут LinkedHashMap, который дополнительно связывает записи в список. HashSet — это тот же HashMap, где значения не используются.

Грабля, на которую наступают чаще всего: ключ, который меняется после того, как его положили в таблицу. Номер корзины посчитали один раз, при вставке. Изменили поле, участвующее в hashCode, — и объект остался лежать в старой корзине, а искать его теперь будут в новой.

живой пример

import java.util.HashMap;
import java.util.Map;

public class MutableKey {
    static class Order {
        int id;
        Order(int id) { this.id = id; }
        @Override public int hashCode() { return Integer.hashCode(id); }
        @Override public boolean equals(Object o) { return o instanceof Order other && other.id == id; }
    }

    public static void main(String[] args) {
        Map<Order, String> orders = new HashMap<>();
        Order order = new Order(1);
        orders.put(order, "оплачен");
        System.out.println("сразу после put: " + orders.get(order));
        order.id = 2;
        System.out.println("после правки ключа: " + orders.get(order));
    }
}

Отсюда правило: ключи хеш-таблицы делают неизменяемыми, а hashCode и equals переопределяют вместе и по одним и тем же полям. Сам контракт односторонний, и его стоит произнести точно: равные по equals объекты обязаны давать равный hashCode, а обратное не требуется, неравные могут совпадать по хешу, это и есть коллизия. Нарушение первого правила ломает поиск (равный ключ ищут в другой корзине), совпадение хешей у неравных лишь замедляет его. Разошлись поля — и два равных объекта попадут в разные корзины (или, наоборот, окажутся неразличимы).

Три мелочи, за которые платят в проде. Память. Каждая запись HashMap это объект-узел: заголовок, хеш, ссылки на ключ, значение и следующий узел, около 32 байт, плюс место в массиве корзин с запасом по коэффициенту заполнения, плюс сами объекты ключа и значения; на миллионе записей это десятки мегабайт сверх данных, и HashMap<Long, Long> тратит на пару восемь байт полезных и около шестьдесят служебных. null. HashMap принимает один null-ключ и сколько угодно null-значений, отчего get не отличает «ключа нет» от «значение null» (для этого containsKey); TreeMap при естественном порядке null-ключ отвергает, а ConcurrentHashMap отвергает и null-ключи, и null-значения. Потоки. HashMap рассчитана на один поток: две одновременные записи молча теряют пары, а в Java 7 могли ещё и зациклить цепочку в корзине. Для нескольких потоков берут ConcurrentHashMap, которая блокирует одну корзину, а не всю таблицу; как она устроена, разбирает статья про HashMap изнутри.

Свою хеш-таблицу писать почти никогда не нужно — в Go она встроена в язык. Важнее понимать, что именно берёте с полки: от этого зависит и скорость, и то, найдётся ли значение в таблице вообще.

Эталонная реализация — map[K]V. С Go 1.24 внутри у неё «швейцарская таблица» (Swiss Table): открытая адресация группами по восемь слотов, у каждой группы байты-метки с семью битами хеша, и поиск сначала сравнивает метки всей группы разом, а уже потом сами ключи. До 1.24 устройство было ближе к цепочкам: корзины по восемь записей с переполнением в дополнительные корзины. Номер группы берут по битам хеша, а сам хеш солят случайным числом, своим для каждой таблицы: подобрать ключи, которые сложатся в одну корзину, снаружи нельзя.

Коэффициент заполнения — 7/8 для швейцарской таблицы (раньше 6,5 записи на корзину из восьми): дальше таблица удваивается и ключи раскладываются заново, причём большая таблица разбита на части, и растут они по отдельности, чтобы одна вставка не стоила O(n) разом. Под сто тысяч записей размер задают сразу: make(map[string]int, 100_000), и это именно ожидаемое число записей, делить на коэффициент не нужно. Удаление таблицу не сжимает: миллион записей вставили, удалили, а память осталась; освобождает её только новая таблица.

Отсюда честная сложность. Чтение и запись — O(1) в среднем, и худший случай защищён не деревом в корзине, как в Java, а случайной солью: злонамеренный вход не может знать, куда лягут ключи. Порядка обхода у map нет, и это не просто «не гарантирован»: среда выполнения нарочно начинает обход со случайного места, чтобы никто не полагался на порядок. Нужен порядок — собирают ключи в срез и сортируют, slices.Sorted(maps.Keys(m)). Множество это map[K]struct{}: пустая структура не занимает памяти.

Ключом может быть только сравнимый тип: числа, строки, указатели, массивы и структуры из сравнимых полей. Срез, карта или функция ключом быть не могут, компилятор это не пропустит. Поэтому грабля с изменяемым ключом в Go выглядит иначе: ключ-структура копируется в таблицу при вставке, и правка исходной переменной на таблицу не влияет. А вот ключ-указатель сравнивается по адресу, и две одинаковые по содержимому структуры по разным указателям — разные ключи.

живой пример

package main

import "fmt"

type Order struct{ ID int }

func main() {
	byValue := map[Order]string{}
	order := Order{1}
	byValue[order] = "оплачен"
	order.ID = 2
	fmt.Println("ключ скопирован при вставке:", byValue[Order{1}], "| по изменённому не найти:", byValue[order] == "")

	byPointer := map[*Order]string{}
	a, b := &Order{1}, &Order{1}
	byPointer[a] = "оплачен"
	fmt.Println("одинаковые структуры по разным указателям — разные ключи:", byPointer[b] == "")
}

Отсюда правило: ключом делают значение, а не указатель, если равенство должно быть по содержимому; и структуру для ключа держат маленькой, потому что она копируется и хешируется целиком. Отдельная ловушка — float64 в ключе: NaN не равен самому себе, и m[math.NaN()] = 1 каждый раз заводит новую запись, которую потом не найти.

Три мелочи, за которые платят в проде. Нулевое значение. Чтение отсутствующего ключа не ошибка, а нулевое значение типа: m["нет"] даёт 0 или "", и «ключа нет» от «значение ноль» отличают второй переменной, v, ok := m[k]. Хуже другое: var m map[string]int без make это nil, читать из него можно, а запись падает с паникой assignment to entry in nil map. Память. Швейцарская таблица держит байт метки на слот плюс сами ключи и значения подряд, без объектов-узлов; map[int64]int64 на миллион записей это порядка 20 МБ, заметно меньше, чем в Java. Горутины. map рассчитана на одну горутину: одновременные запись и чтение среда выполнения ловит и роняет процесс фатальной ошибкой concurrent map writes, которую не поймать через recover. Для нескольких горутин таблицу закрывают sync.RWMutex, а для кеша «пишут редко, читают много» есть sync.Map.

Свою хеш-таблицу писать почти никогда не нужно — в JavaScript их две, и обе встроены. Важнее понимать, что именно берёте с полки: от этого зависит и скорость, и то, найдётся ли значение в таблице вообще.

Эталонная реализация — Map (и Set, который внутри та же таблица без значений). Внутри у неё в V8 массив корзин и метод цепочек, только записи лежат не в узлах, а в отдельном плотном массиве в порядке вставки, а корзина хранит индекс первой записи и цепочку индексов. Отсюда главное внешнее свойство: Map обходится в порядке вставки, и это гарантия стандарта, а не деталь движка. Когда записей становится столько же, сколько корзин, таблица удваивается и ключи раскладываются заново, а удалённые записи уплотняются при очередной перестройке.

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

Отсюда честная сложность. get, set, has, delete — O(1) в среднем; худший случай спасает соль хеша, дерева в корзине, как в Java, здесь нет. Равенство ключей — SameValueZero: как ===, но NaN равен NaN, а +0 равен -0. Для объектов это равенство по ссылке: два объекта с одинаковыми полями — разные ключи. Поэтому грабля с изменяемым ключом в JavaScript вывернута наизнанку: менять поля объекта-ключа можно сколько угодно, таблица его не потеряет, зато найти запись по «такому же» объекту нельзя.

живой пример

const orders = new Map();
const order = { id: 1 };
orders.set(order, "оплачен");
order.id = 2;
console.log("после правки ключа:", orders.get(order));
console.log("по равному объекту:", orders.get({ id: 2 }));
console.log("NaN находит NaN:", new Map([[NaN, "нашёлся"]]).get(NaN));

Отсюда правило: ключом делают примитив, строку или число, если равенство должно быть по содержимому; составной ключ собирают в строку, ${city}:${day}, или заводят вложенные Map. Объект ключом кладут тогда, когда нужен именно «этот самый объект», и чаще через WeakMap, чтобы таблица не мешала сборщику мусора его убрать.

Вторая таблица — обычный объект {}. Это тоже словарь, но с оговорками: ключи приводятся к строкам, obj[1] и obj["1"] одно и то же; у объекта есть прототип, и obj["constructor"] найдётся, хотя вы его не клали, а запись по ключу __proto__ из пользовательского ввода может подменить прототип, это и есть prototype pollution. Словарь из ненадёжных ключей делают через Object.create(null) или берут Map. Движок к тому же переводит объект с тысячами разных ключей в «режим словаря», где доступ медленнее, чем у объекта с фиксированной формой.

Три мелочи, за которые платят в проде. Отсутствующий ключ. get возвращает undefined, и его не отличить от записанного undefined; для этого есть has. Память. Запись Map стоит порядка 30–40 байт служебных плюс сами ключ и значение; миллион записей это десятки мегабайт, а куча Node по умолчанию ограничена. Потоки. В одном потоке гонок нет, Map безопасна между обработчиками событий сама по себе; между воркерами она не разделяется вовсе, туда передают копии через postMessage.

Свою хеш-таблицу писать почти никогда не нужно — в Python на ней стоит весь язык: атрибуты объектов, пространства имён модулей, именованные аргументы. Важнее понимать, что именно берёте с полки: от этого зависит и скорость, и то, найдётся ли значение в таблице вообще.

Эталонная реализация — dict (и set, у которого та же таблица без значений). Внутри у неё открытая адресация: при коллизии следующая ячейка выбирается не соседняя, а вычисленная из старших битов хеша, так что регулярные ключи не слипаются в цепочки. С Python 3.6 таблица «компактная»: массив ячеек хранит только индексы, а записи лежат в отдельном плотном массиве в порядке добавления. Отсюда свойство, которого от хеш-таблицы не ждут: dict обходится в порядке вставки, и с 3.7 это гарантия языка.

Коэффициент заполнения — 2/3: когда занято две трети ячеек, таблица растёт и все ключи раскладываются заново. Перестройка стоит O(n), а задать ёмкость заранее нельзя: конструктор dict числа не принимает, и на сотне тысяч записей таблица переживёт полтора десятка перестроек. Это редко проблема, потому что хеш каждой записи хранится рядом с ней и при перестройке не пересчитывается.

Хеш строк и байтов солится случайным числом при старте интерпретатора (переменная PYTHONHASHSEED его фиксирует): подобрать ключи, которые сложатся в одну цепочку, снаружи нельзя, и дерева в корзине, как в Java, для защиты не нужно. Отсюда честная сложность: чтение и запись O(1) в среднем. Небольшие целые хешируются сами в себя, hash(5) == 5, поэтому словарь с ключами 0, 1, 2 вообще не знает коллизий.

Ключом может быть только хешируемый объект: числа, строки, кортежи из хешируемых, замороженные множества. Список, словарь и множество ключами быть не могут, TypeError: unhashable type, и это защита от той самой грабли с изменяемым ключом. Но у своих классов защиты нет: объект по умолчанию хешируется по адресу, а стоит определить __hash__ через изменяемое поле, и ключ, изменённый после вставки, теряется в старой ячейке, ровно как в Java.

живой пример

class Order:
    def __init__(self, id: int) -> None:
        self.id = id

    def __hash__(self) -> int:
        return hash(self.id)

    def __eq__(self, other) -> bool:
        return isinstance(other, Order) and other.id == self.id


orders = {}
order = Order(1)
orders[order] = "оплачен"
print("сразу после вставки:", orders.get(order))
order.id = 2
print("после правки ключа:", orders.get(order))
try:
    {[1, 2]: "список"}
except TypeError as e:
    print("а список ключом быть не может:", e)

Отсюда правило: ключи хеш-таблицы делают неизменяемыми, а __hash__ и __eq__ определяют вместе и по одним и тем же полям. Язык здесь подстраховывает: класс, в котором определили __eq__ и не определили __hash__, становится нехешируемым автоматически. Для данных берут @dataclass(frozen=True): он сам делает и __eq__, и __hash__ по всем полям и запрещает их менять. Контракт односторонний: равные по __eq__ объекты обязаны давать равный хеш, а неравные могут совпадать по хешу, это и есть коллизия.

Три мелочи, за которые платят в проде. Память. Компактный dict держит на запись индекс, хеш и две ссылки, около 30 байт, плюс запас по коэффициенту заполнения, плюс сами объекты ключа и значения; словарь int → int на миллион пар это около 40 МБ вместе с объектами чисел. Атрибуты объектов лежат в таких же словарях, поэтому __slots__ у класса с миллионом экземпляров экономит гигабайты. Отсутствующий ключ. d[k] бросает KeyError, d.get(k) возвращает None, и «ключа нет» от «значение None» отличают через k in d или d.get(k, default); для счётчиков и группировок есть collections.Counter и defaultdict, которые сами заводят запись. Потоки. Отдельная операция с dict атомарна благодаря глобальной блокировке интерпретатора, а составная «проверить и записать» нет; кеш между потоками закрывают threading.Lock, а самый частый кеш в Python вообще не пишут руками: functools.lru_cache.

int find(String text, String pattern) {
    int m = pattern.length(), n = text.length();
    if (m > n) return -1;
    long base = 256, mod = 1_000_000_007L, high = 1;
    for (int i = 1; i < m; i++) high = high * base % mod;   // base^(m-1)
    long hp = 0, ht = 0;
    for (int i = 0; i < m; i++) {
        hp = (hp * base + pattern.charAt(i)) % mod;
        ht = (ht * base + text.charAt(i)) % mod;
    }
    for (int i = 0; ; i++) {
        if (hp == ht && text.regionMatches(i, pattern, 0, m)) return i;
        if (i + m >= n) return -1;
        ht = ((ht - text.charAt(i) * high % mod + mod) * base + text.charAt(i + m)) % mod;
    }
}

func find(text, pattern string) int {
	m, n := len(pattern), len(text)
	if m > n {
		return -1
	}
	const base, mod = 256, 1_000_000_007
	high := 1
	for i := 1; i < m; i++ {
		high = high * base % mod // base^(m-1)
	}
	hp, ht := 0, 0
	for i := 0; i < m; i++ {
		hp = (hp*base + int(pattern[i])) % mod
		ht = (ht*base + int(text[i])) % mod
	}
	for i := 0; ; i++ {
		if hp == ht && text[i:i+m] == pattern {
			return i
		}
		if i+m >= n {
			return -1
		}
		ht = ((ht-int(text[i])*high%mod+mod)*base + int(text[i+m])) % mod
	}
}

function find(text, pattern) {
  const m = pattern.length, n = text.length;
  if (m > n) return -1;
  const base = 256, mod = 1_000_000_007;
  let high = 1;
  for (let i = 1; i < m; i++) high = high * base % mod;   // base^(m-1)
  let hp = 0, ht = 0;
  for (let i = 0; i < m; i++) {
    hp = (hp * base + pattern.charCodeAt(i)) % mod;
    ht = (ht * base + text.charCodeAt(i)) % mod;
  }
  for (let i = 0; ; i++) {
    if (hp === ht && text.startsWith(pattern, i)) return i;
    if (i + m >= n) return -1;
    ht = ((ht - text.charCodeAt(i) * high % mod + mod) * base + text.charCodeAt(i + m)) % mod;
  }
}

def find(text: str, pattern: str) -> int:
    m, n = len(pattern), len(text)
    if m > n:
        return -1
    base, mod = 256, 1_000_000_007
    high = pow(base, m - 1, mod)                      # base^(m-1)
    hp = ht = 0
    for i in range(m):
        hp = (hp * base + ord(pattern[i])) % mod
        ht = (ht * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if hp == ht and text[i:i + m] == pattern:
            return i
        if i + m >= n:
            return -1
        ht = ((ht - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return -1

живой пример

import java.util.*;

public class TrieDemo {
    static final class Node {
        final Map<Character, Node> next = new HashMap<>();
        boolean end;
    }

    static final class Trie {
        private final Node root = new Node();

        void add(String word) {
            Node n = root;
            for (char c : word.toCharArray()) n = n.next.computeIfAbsent(c, k -> new Node());
            n.end = true;
        }

        List<String> withPrefix(String prefix) {
            Node n = root;
            for (char c : prefix.toCharArray()) {
                n = n.next.get(c);
                if (n == null) return List.of();
            }
            List<String> out = new ArrayList<>();
            collect(n, new StringBuilder(prefix), out);
            return out;
        }

        private void collect(Node n, StringBuilder path, List<String> out) {
            if (n.end) out.add(path.toString());
            for (var e : new TreeMap<>(n.next).entrySet()) {
                path.append(e.getKey());
                collect(e.getValue(), path, out);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String w : List.of("молоко", "молот", "мост", "масло")) trie.add(w);
        System.out.println(trie.withPrefix("мол"));
        System.out.println(trie.withPrefix("мо"));
        System.out.println(trie.withPrefix("мы"));
    }
}

живой пример

package main

import (
	"fmt"
	"sort"
)

type node struct {
	next map[rune]*node
	end  bool
}

func newNode() *node { return &node{next: map[rune]*node{}} }

type trie struct{ root *node }

func (t *trie) add(word string) {
	n := t.root
	for _, c := range word {
		if n.next[c] == nil {
			n.next[c] = newNode()
		}
		n = n.next[c]
	}
	n.end = true
}

func (t *trie) withPrefix(prefix string) []string {
	n := t.root
	for _, c := range prefix {
		if n = n.next[c]; n == nil {
			return nil
		}
	}
	var out []string
	collect(n, []rune(prefix), &out)
	return out
}

func collect(n *node, path []rune, out *[]string) {
	if n.end {
		*out = append(*out, string(path))
	}
	keys := make([]rune, 0, len(n.next))
	for c := range n.next {
		keys = append(keys, c)
	}
	sort.Slice(keys, func(i, j int) bool { return keys[i] < keys[j] })
	for _, c := range keys {
		collect(n.next[c], append(path, c), out)
	}
}

func main() {
	t := &trie{root: newNode()}
	for _, w := range []string{"молоко", "молот", "мост", "масло"} {
		t.add(w)
	}
	fmt.Println(t.withPrefix("мол"))
	fmt.Println(t.withPrefix("мо"))
	fmt.Println(t.withPrefix("мы"))
}

живой пример

class Trie {
  constructor() { this.root = { next: new Map(), end: false }; }

  add(word) {
    let n = this.root;
    for (const c of word) {
      if (!n.next.has(c)) n.next.set(c, { next: new Map(), end: false });
      n = n.next.get(c);
    }
    n.end = true;
  }

  withPrefix(prefix) {
    let n = this.root;
    for (const c of prefix) {
      n = n.next.get(c);
      if (!n) return [];
    }
    const out = [];
    const collect = (node, path) => {
      if (node.end) out.push(path);
      for (const c of [...node.next.keys()].sort()) collect(node.next.get(c), path + c);
    };
    collect(n, prefix);
    return out;
  }
}

const trie = new Trie();
for (const w of ["молоко", "молот", "мост", "масло"]) trie.add(w);
console.log(trie.withPrefix("мол"));
console.log(trie.withPrefix("мо"));
console.log(trie.withPrefix("мы"));

живой пример

class Trie:
    def __init__(self):
        self.root = {}          # буква -> поддерево, "$" -> конец слова

    def add(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node["$"] = True

    def with_prefix(self, prefix):
        node = self.root
        for c in prefix:
            node = node.get(c)
            if node is None:
                return []
        out = []

        def collect(n, path):
            if "$" in n:
                out.append(path)
            for c in sorted(k for k in n if k != "$"):
                collect(n[c], path + c)

        collect(node, prefix)
        return out


trie = Trie()
for w in ["молоко", "молот", "мост", "масло"]:
    trie.add(w)
print(trie.with_prefix("мол"))
print(trie.with_prefix("мо"))
print(trie.with_prefix("мы"))

• new HashMap<>(100_000) даёт порог 98 304 и ещё одну перестройку: ёмкость округляется до степени двойки; нужно HashMap.newHashMap(100_000) или (int)(n / 0.75) + 1.
• Контракт односторонний: равные по equals обязаны давать равный хеш, обратное не требуется; узел HashMap стоит около 32 байт плюс корзины, один null-ключ разрешён, а для потоков берут ConcurrentHashMap.

• make(map[K]V, n) принимает ожидаемое число записей; из nil-карты можно читать, запись паникует; с Go 1.24 внутри швейцарская таблица с открытой адресацией и случайной солью, а обход нарочно начинается со случайного места.
• Ключ только сравнимого типа: структура копируется при вставке, указатель сравнивается по адресу; одновременные записи из горутин роняют процесс фатальной ошибкой, для них sync.RWMutex или sync.Map.

• Map обходится в порядке вставки и сравнивает ключи по SameValueZero: объекты по ссылке, NaN равен NaN; составной ключ собирают в строку; ёмкость заранее не задать.
• Объект {} как словарь приводит ключи к строкам и тянет прототип: для чужих ключей Object.create(null) или Map; get не отличает отсутствие от undefined, для этого has.

• dict с 3.6 компактный и обходится в порядке вставки, порог 2/3, ёмкость заранее не задать; хеш строк солится при старте интерпретатора; hash(5) == 5.
• Ключ только хешируемый: список и словарь отвергаются, свой класс с __eq__ без __hash__ нехешируем сам; __hash__ и __eq__ по одним полям, лучше @dataclass(frozen=True); отдельная операция атомарна, составная нет.