Ответ 1
Разработчикам не нужно обойти проблему хеш-коллизий в HashMap, чтобы обеспечить правильность программы.
Здесь есть пара ключевых моментов:
- Коллизии являются неотъемлемой чертой хеширования, и они должны быть. Количество возможных значений (строки в вашем случае, но оно относится и к другим типам) значительно больше, чем диапазон целых чисел.
- Каждое использование хеширования имеет способ обработки коллизий, а сборка Java (включая HashMap) не является исключением.
- Хэширование не участвует в тестировании равенства. Это правда, что равные объекты должны иметь одинаковые хэш-коды, но обратное неверно: многие значения будут иметь один и тот же хэш-код. Поэтому не пытайтесь использовать сравнение хэш-кода в качестве замены равенства. Коллекций нет. Они используют хеширование для выбора подсетей (называемых ведром в мире Java Collections), но они используют .equals() для проверки равенства.
- Вам не только не нужно беспокоиться о столкновениях, вызывающих неправильные результаты в коллекции, но и для большинства приложений вы также * обычно * не должны беспокоиться о производительности - Java hashed Collections делает довольно хорошую работу по управлению хэш-кодами,
- Еще лучше, для случая, о котором вы спрашивали (строки как ключи), вам даже не нужно беспокоиться о самих хэш-кодах, потому что класс Java String генерирует довольно хороший хэш-код. Таким образом, большинство предоставленных Java-классов.
Более подробная информация, если вы хотите:
Как работает хэширование (в частности, в случае хеш-коллекций, таких как Java HashMap, о чем вы спрашиваете):
-
В HashMap хранятся значения, которые вы даете ему в коллекции подкатегорий, называемых кодами. Они фактически реализованы как связанные списки. Их число ограничено: iirc, 16 для начала по умолчанию, и число увеличивается с увеличением количества элементов на карте. Всегда должно быть больше ковшей, чем значений. Чтобы привести один пример, используя значения по умолчанию, если вы добавите 100 записей в HashMap, будет 256 кодов.
-
Каждое значение, которое может использоваться как ключ на карте, должно иметь возможность генерировать целочисленное значение, называемое хэш-кодом.
-
HashMap использует этот хэш-код для выбора ведра. В конечном итоге это означает, что для целочисленного значения
moduloколичество ведер, но до этого у Java HashMap есть внутренний метод (называемыйhash()), который изменяет хэш-код для уменьшения некоторых известных источников комков. -
При поиске значения HashMap выбирает ведро, а затем ищет отдельный элемент путем линейного поиска связанного списка, используя
.equals().
Итак: вам не нужно работать с коллизиями для правильности, и вам обычно не нужно беспокоиться о них за производительность, и если вы используете собственные классы Java (например, String), у вас нет беспокоиться о генерации значений хэш-кода.
В случае, когда вам нужно написать свой собственный метод hashcode (это означает, что вы написали класс с составным значением, например, имя и фамилия), все становится немного сложнее. Здесь совершенно неправильно, но это не ракетостроение. Во-первых, знайте об этом: единственное, что вы должны сделать, чтобы обеспечить правильность, - обеспечить равные объекты равными хэш-кодами. Поэтому, если вы пишете метод hashcode() для своего класса, вы также должны написать метод equals(), и вы должны изучить одинаковые значения в каждом.
Можно написать метод hashcode(), который является плохим, но правильным, под которым я подразумеваю, что он будет удовлетворять условию "равные объекты должны приводить к равным хэш-кодам", но все же выполнять очень плохо, имея много столкновений.
Каноническим вырожденным наихудшим случаем этого было бы написать метод, который просто возвращает постоянное значение (например, 3) для всех случаев. Это означало бы, что каждое значение будет хэшировано в одно и то же ведро.
Он по-прежнему будет работать, но производительность снизится до уровня связанного списка.
Очевидно, вы не будете писать такой ужасный метод hashcode(). Если вы используете достойную среду IDE, она способна генерировать ее для вас. Так как StackOverflow любит код, вот код для класса firstname/lastname выше.
public class SimpleName {
private String firstName;
private String lastName;
public SimpleName(String firstName, String lastName) {
super();
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result
+ ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result
+ ((lastName == null) ? 0 : lastName.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SimpleName other = (SimpleName) obj;
if (firstName == null) {
if (other.firstName != null)
return false;
} else if (!firstName.equals(other.firstName))
return false;
if (lastName == null) {
if (other.lastName != null)
return false;
} else if (!lastName.equals(other.lastName))
return false;
return true;
}
}