Коллекции middle
Как устроен HashMap?
Ответ
Массив Node<K,V>[]. Размер — степень двойки (default 16). Индекс: (n-1) & hash(key), hash — XOR верхних 16 бит с нижними. Коллизии — связный список (chaining). Java 8+: при TREEIFY_THRESHOLD=8 И capacity ≥ 64 → red-black tree.
Разбор: Размер таблицы — степень двойки (по умолчанию 16), индекс = (n-1) & hash, где hash перемешивает старшие и младшие биты через XOR; коллизии — связный список, который превращается в красно-чёрное дерево только при длине ≥ 8 И capacity ≥ 64. Ловушки: размер не простое число; индекс именно (n-1) & hash, а не hash & n; и HashMap использует chaining, а не открытую адресацию с линейным пробированием.
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.