HashMap: chain hashing и битовый спрединг

🧠 HashMap использует chain hashing + битовый спрединг

🔹 Хэш-функция (bit mixing):

int h = key.hashCode();
int hash = h ^ (h >>> 16);

🔹 Выбор бакета:

int idx = hash & (table.length - 1);

📌 Separate chaining: в каждом бакете хранится связный список (Java 8+ превращает списки длиной >8 в красно-черное дерево для ускорения).
📈 Сложность: средняя O(1), в худшем случае O(n) → O(log n) после treeification.
💡 Bit mixing объединяет старшие и младшие биты, чтобы при взятии по модулю power-of-two (маска &) распределение оставалось равномерным.
⚠️ Не для криптографии: это простая битовая операция, а не криптостойкая хэш-функция.

👉 @java_geek