Что такое хеш-таблица (hashmap)?

Что такое хеш-таблица (HashMap)?

Хеш-таблица (HashMap) — это структура данных, которая реализует интерфейс Map и использует хеш-функцию для быстрого поиска, вставки и удаления элементов по ключу. HashMap хранит пары ключ-значение и обеспечивает очень быстрый доступ в среднем случае. Это одна из самых важных и часто используемых структур данных в программировании, особенно в Android разработке.

Принцип работы

HashMap использует массив корзин (buckets), в каждой из которых хранятся элементы:

// Простое использование HashMap
val map: HashMap<String, Int> = hashMapOf(
    "apple" to 5,
    "banana" to 3,
    "orange" to 7
)

// Доступ по ключу (O(1) в среднем)
val count = map["apple"]  // 5

// Вставка нового элемента (O(1) в среднем)
map["grape"] = 10

// Удаление (O(1) в среднем)
map.remove("banana")

// Проверка наличия ключа
if ("apple" in map) {
    println("Apple found")
}

// Итерация
for ((fruit, count) in map) {
    println("$fruit: $count")
}

Как работает хеширование

1. При добавлении элемента вычисляется хеш ключа: hashCode = key.hashCode()
2. Хеш преобразуется в индекс массива: index = hashCode % arrayLength
3. Элемент кладётся в корзину по этому индексу
4. Если в корзине уже есть элементы (коллизия), они образуют цепь (в Java 8+ это красно-чёрное дерево)

data class User(val id: Int, val name: String) {
    override fun hashCode(): Int {
        return id.hashCode() * 31 + name.hashCode()
    }
    
    override fun equals(other: Any?): Boolean {
        return other is User && id == other.id && name == other.name
    }
}

val users: HashMap<Int, User> = hashMapOf(
    1 to User(1, "Alice"),
    2 to User(2, "Bob")
)

val user = users[1]  // Быстрый поиск!

Временная сложность операций

Load Factor и Rehashing

// Load factor = количество элементов / размер массива
// По умолчанию rehashing происходит при load factor >= 0.75

val map = HashMap<String, String>()
// Начальная вместимость: 16 элементов
// Когда элементов будет 12, HashMap увеличит размер вдвое до 32
// Все элементы перехешируются в новый массив (дорогая операция!)

Различия между HashMap, LinkedHashMap и TreeMap

// HashMap — быстро, порядок не гарантирован
val hashMap = HashMap<String, Int>()
hashMap["c"] = 3
hashMap["a"] = 1
hashMap["b"] = 2
println(hashMap)  // Может быть в любом порядке

// LinkedHashMap — сохраняет порядок вставки
val linkedMap = LinkedHashMap<String, Int>()
linkedMap["c"] = 3
linkedMap["a"] = 1
linkedMap["b"] = 2
println(linkedMap)  // {c=3, a=1, b=2}

// TreeMap — отсортирован по ключам (O(log n))
val treeMap = TreeMap<String, Int>()
treeMap["c"] = 3
treeMap["a"] = 1
treeMap["b"] = 2
println(treeMap)  // {a=1, b=2, c=3}

Практический пример в Android

// Кэширование данных пользователей
class UserCache {
    private val cache: HashMap<String, User> = HashMap()
    private val accessTime: HashMap<String, Long> = HashMap()
    
    fun put(id: String, user: User) {
        cache[id] = user
        accessTime[id] = System.currentTimeMillis()
    }
    
    fun get(id: String): User? {
        // Проверка времени кэша (например, 5 минут)
        val lastAccess = accessTime[id] ?: return null
        if (System.currentTimeMillis() - lastAccess > 5 * 60 * 1000) {
            cache.remove(id)
            accessTime.remove(id)
            return null
        }
        return cache[id]
    }
    
    fun clear() {
        cache.clear()
        accessTime.clear()
    }
}

// Подсчёт частоты элементов
fun countFrequency(list: List<String>): HashMap<String, Int> {
    val frequency = HashMap<String, Int>()
    
    for (item in list) {
        frequency[item] = (frequency[item] ?: 0) + 1
    }
    
    return frequency
}

val words = listOf("kotlin", "java", "kotlin", "python", "java", "kotlin")
val freq = countFrequency(words)
println(freq)  // {kotlin=3, java=2, python=1}

Важные моменты

1. null ключи — HashMap может содержать один null ключ
2. equals() и hashCode() — для корректной работы нужны правильные реализации
3. Thread-safety — HashMap не синхронизирован, используй ConcurrentHashMap для многопоточности
4. Коллизии — неизбежны, Java их обрабатывает, но они снижают производительность
5. Итерация — изменение HashMap во время итерации вызывает ConcurrentModificationException

// Опасно!
val map = hashMapOf(1 to "a", 2 to "b")
for ((key, value) in map) {
    if (key == 1) map.remove(key)  // ConcurrentModificationException!
}

// Правильно
for ((key, value) in map.toList()) {  // Копируем перед итерацией
    if (key == 1) map.remove(key)  // OK
}

HashMap — это фундаментальная структура данных, которая должна быть в арсенале каждого разработчика.