Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
HashMap и хеш-таблицы: как это работает
Хеш-таблица — это структура данных, которая хранит пары ключ-значение и обеспечивает очень быстрый поиск. HashMap в Java — это реализация хеш-таблицы с функцией хеширования.
Базовый принцип: Хеш-функция
Хеш-функция преобразует ключ в индекс массива:
// Упрощённый пример:
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 30);
map.put("Bob", 25);
map.put("Charlie", 35);
// Внутри работает так:
// 1. Вычислим хеш ключа: hash("Alice") → 15
// 2. Найдём индекс: index = hash % tableSize → 15 % 16 = 15
// 3. Сохраним в массив[15] → ("Alice", 30)
public class SimpleHashMap<K, V> {
private static final int INITIAL_CAPACITY = 16;
private Entry<K, V>[] table;
private int size = 0;
public void put(K key, V value) {
if (key == null) {
// null ключ хранится специально
putForNullKey(value);
return;
}
int hash = key.hashCode();
int index = hash % table.length; // Модульная операция
// Если место занято (collision) — сохраним в цепочку (chain)
if (table[index] == null) {
table[index] = new Entry<>(key, value, hash);
size++;
} else {
// Collision handling: добавим в цепочку
addEntryToChain(index, key, value);
}
}
}
Внутренняя структура HashMap
Индекс | Содержимое
────────┼──────────────────────────────────
0 | null
1 | ("Bob", 25) → ("Danny", 28) ← Цепочка
2 | ("Alice", 30)
3 | null
4 | ("Charlie", 35)
... | ...
15 | null
Проблема 1: Коллизии (Collisions)
Когда два разных ключа дают один и тот же хеш-индекс:
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 30);
map.put("Bob", 25);
// Если hash("Alice") % 16 == 1 и hash("Bob") % 16 == 1
// Это коллизия! Оба должны быть в позиции [1]
Решение 1: Chaining (Цепочки)
Java использует linked list для коллизий:
// Структура Entry в HashMap:
private static class Node<K, V> {
final K key;
V value;
Node<K, V> next; // Указатель на следующий элемент при коллизии
}
// При коллизии:
table[1] = new Node("Alice", 30,
new Node("Bob", 25, null));
// Поиск Alice:
node = table[1]; // Получим Alice
while (node != null) {
if (node.key.equals("Alice")) return node.value; // Нашли
node = node.next;
}
Решение 2:红-Black Tree (с Java 8+)
Если в одной цепочке больше 8 элементов, HashMap конвертирует её в дерево:
// Когда цепочка становится слишком длинной:
if (treeifyBin(tab, hash)) return; // Конвертируем в красно-чёрное дерево
// Это улучшает производительность поиска с O(n) до O(log n)
Проблема 2: Load Factor и Rehashing
Когда HashMap становится слишком заполнена, нужно увеличить размер:
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = 0.75f; // При 75% заполненности будет resize
this.threshold = (int)(capacity * loadFactor); // = 12 для capacity 16
}
public void put(K key, V value) {
// ...
if (++size > threshold) {
resize(); // Создаём новый массив в 2 раза больше
}
}
private void resize() {
// Старый размер: 16, новый: 32
Node<K, V>[] oldTable = table;
table = new Node[oldTable.length * 2];
// Перехешируем все элементы в новую таблицу
// hash % 16 != hash % 32, поэтому нужно пересчитать индексы
for (Node<K, V> e : oldTable) {
while (e != null) {
int newIndex = e.hash % table.length;
table[newIndex] = new Node<>(e.key, e.value, e.hash);
e = e.next;
}
}
}
Практический пример использования
public class UserRepository {
private final Map<UUID, User> userCache = new HashMap<>();
public void addUser(User user) {
userCache.put(user.getId(), user);
// O(1) в среднем случае
}
public User getUserById(UUID id) {
return userCache.get(id);
// O(1) в среднем, O(n) в худшем (все коллизии)
}
public void removeUser(UUID id) {
userCache.remove(id);
// O(1) в среднем
}
}
// Использование:
public static void main(String[] args) {
Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 100);
scores.put("Bob", 85);
scores.put("Charlie", 92);
System.out.println(scores.get("Alice")); // 100 (быстро!)
System.out.println(scores.containsKey("David")); // false (быстро!)
scores.replace("Bob", 90);
scores.forEach((name, score) ->
System.out.println(name + ": " + score)
);
}
Сложность операций
// В среднем (average case):
put(K, V) → O(1)
get(K) → O(1)
containsKey(K) → O(1)
remove(K) → O(1)
// В худшем случае (all collisions):
put(K, V) → O(n)
get(K) → O(n)
containsKey(K) → O(n)
remove(K) → O(n)
// С Java 8+ (красно-чёрные деревья):
// Худший случай улучшен до O(log n)
Важно: hashCode и equals
Для правильной работы HashMap нужно реализовать оба метода:
public class User {
private UUID id;
private String name;
// ✅ Правильная реализация:
@Override
public int hashCode() {
return Objects.hash(id, name);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
User user = (User) obj;
return Objects.equals(id, user.id) && Objects.equals(name, user.name);
}
}
// Правило: если equals(obj) == true, то hashCode() должны быть одинаковыми
User user1 = new User(UUID.randomUUID(), "Alice");
User user2 = new User(user1.id, "Alice");
if (user1.equals(user2)) {
assert user1.hashCode() == user2.hashCode(); // ДОЛЖНЫ быть равны!
}
Map<User, Integer> map = new HashMap<>();
map.put(user1, 100);
map.get(user2); // Вернёт 100, т.к. equals == true
Распространённые ошибки
Ошибка 1: Изменение ключей
// ❌ ОПАСНО! Никогда не меняй ключи после put:
Map<StringBuilder, Integer> map = new HashMap<>();
StringBuilder key = new StringBuilder("Alice");
map.put(key, 100);
key.append("123"); // Изменили key!
map.get(new StringBuilder("Alice")); // null! Ломается структура HashMap
// ✅ Используй immutable ключи:
Map<String, Integer> map = new HashMap<>(); // String immutable
map.put("Alice", 100);
Ошибка 2: Не реализовал hashCode/equals
// ❌ Без переопределения:
class User {
UUID id;
String name;
// hashCode и equals из Object — работают по адресу в памяти!
}
User u1 = new User(id1, "Alice");
User u2 = new User(id1, "Alice");
Map<User, Integer> map = new HashMap<>();
map.put(u1, 100);
map.get(u2); // null! u1 != u2 по памяти
Ошибка 3: Null ключи
// HashMap позволяет один null ключ:
Map<String, Integer> map = new HashMap<>();
map.put(null, 100);
map.put("Alice", 200);
System.out.println(map.get(null)); // 100
System.out.println(map.get("Alice")); // 200
// Но вот это опасно в TreeMap (не может быть null):
Map<String, Integer> tree = new TreeMap<>();
tree.put(null, 100); // NullPointerException!
Альтернативы HashMap
// Если нужна thread-safety:
Map<String, Integer> map = new ConcurrentHashMap<>(); // Lock striping
// Если нужен порядок insertion:
Map<String, Integer> map = new LinkedHashMap<>(); // Doubly linked list
// Если нужен порядок сортировки ключей:
Map<String, Integer> map = new TreeMap<>(); // Red-Black Tree O(log n)
// Если нужна слабая ссылка (GC может удалить):
Map<String, Integer> map = new WeakHashMap<>();
Вывод
HashMap — это:
- Быстрая структура благодаря хеширванию
- Нужно правильно реализовать hashCode/equals на ключах
- Обработка коллизий через цепочки или деревья
- Rehashing когда заполненность превышает load factor
- O(1) в среднем, но может быть O(n) в худшем
Велико важно понимать эту структуру для написания эффективного кода и прохождения собеседований.