Как написать класс для ключа в HashMap, чтобы минимизировать коллизии

«Как написать класс для ключа в HashMap, чтобы минимизировать коллизии» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Для минимизации коллизий в HashMap ключ должен правильно реализовывать equals() и hashCode(). Основные правила:

  1. Равные объекты по equals() должны возвращать одинаковый hashCode()
  2. Разные объекты должны стараться возвращать разные хэши (но это не строгое требование)
  3. Хэш-функция должна быть эффективной

Пример хорошего ключа:

data class UserKey(val id: String, val email: String) {
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false
        other as UserKey
        return id == other.id && email == other.email
    }

    override fun hashCode(): Int {
        var result = id.hashCode()
        result = 31 * result + email.hashCode()
        return result
    }
}

Лучшие практики:

  • Используйте все значимые поля в equals()/hashCode()
  • Для примитивов используйте их напрямую
  • Для объектов вызывайте их hashCode()
  • Умножайте промежуточные результаты на простое число (например 31)