Разработчикам не нужно обходить проблему коллизий хешей в HashMap, чтобы достичь корректности программы.
Здесь нужно понять пару ключевых моментов:
- Столкновения являются неотъемлемой чертой хеширования, и они должны быть. Количество возможных значений (в вашем случае Strings, но это относится и к другим типам) значительно больше, чем диапазон целых чисел.
- Каждое использование хеширования имеет способ обрабатывать коллизии, и коллекции Java (включая HashMap) не являются исключением.
- Хеширование не участвует в тестировании на равенство. Это правда, что равные объекты должны иметь одинаковые хеш-коды, но обратное неверно: многие значения будут иметь одинаковый хеш-код. Поэтому не пытайтесь использовать сравнение хеш-кода в качестве замены равенства. Коллекции нет. Они используют хеширование, чтобы выбрать подколлекцию (называемую корзиной в мире коллекций Java), но они используют .equals (), чтобы фактически проверить на равенство.
- Мало того, что вам не нужно беспокоиться о коллизиях, приводящих к некорректным результатам в коллекции, но и для большинства приложений вам также * обычно * не нужно беспокоиться о производительности - хешированные Java-коллекции довольно хорошо справляются с управлением хэш-кодами ,
- Еще лучше: для случая, о котором вы спрашивали (строки как ключи), вам даже не нужно беспокоиться о самих хеш-кодах, потому что класс String в Java генерирует довольно хороший хеш-код. Как и большинство поставляемых классов Java.
Еще немного подробностей, если хотите:
Способ хэширования (в частности, в случае хэшированных коллекций, таких как Java HashMap, о чем вы спрашивали), таков:
HashMap хранит значения, которые вы ему даете, в коллекции вложенных коллекций, называемых сегментами. Они фактически реализованы в виде связанных списков. Их число ограничено: iirc, 16 запускается по умолчанию, и это число увеличивается с увеличением количества элементов на карте. Всегда должно быть больше сегментов, чем значений. Чтобы привести один пример, используя значения по умолчанию, если вы добавите 100 записей в HashMap, будет 256 блоков.
Каждое значение, которое можно использовать в качестве ключа на карте, должно иметь возможность генерировать целочисленное значение, называемое хеш-кодом.
HashMap использует этот хэш-код для выбора сегмента. В конечном итоге это означает принятие целочисленного значения modulo количества сегментов, но до этого в HashMap в Java есть внутренний метод (называемый hash()), который настраивает хэш-код для уменьшения некоторых известных источников объединения.
При поиске значения HashMap выбирает сегмент, а затем ищет отдельный элемент путем линейного поиска по связанному списку, используя .equals().
Итак: вам не нужно обходить коллизии для корректности, и вам обычно не нужно беспокоиться о них из-за производительности, а если вы используете нативные классы Java (например, String), у вас нет беспокоиться о генерации значений хеш-кода тоже.
В случае, когда вам действительно нужно написать свой собственный метод хэш-кода (что означает, что вы написали класс с составным значением, таким как пара имя / фамилия), все становится немного сложнее. Здесь вполне возможно ошибиться, но это не ракетостроение. Во-первых, знайте это: единственное, что вы должны сделать, чтобы убедиться в правильности, - это убедиться, что равные объекты дают одинаковые хеш-коды. Поэтому, если вы пишете метод hashcode () для своего класса, вы также должны написать метод equals (), и вы должны проверить одинаковые значения в каждом из них.
Можно написать метод hashcode (), который является плохим, но правильным, и я имею в виду, что он будет удовлетворять ограничению «равные объекты должны давать равные хэш-коды», но все равно будет работать очень плохо, имея много коллизий .
Каноническим вырожденным наихудшим случаем этого было бы написание метода, который просто возвращает постоянное значение (например, 3) для всех случаев. Это будет означать, что каждое значение будет хэшировано в одно и то же ведро.
Это все равно будет работать , но производительность будет снижаться по сравнению со связным списком.
Очевидно, вы не напишите такой ужасный метод hashcode (). Если вы используете достойную IDE, она способна сгенерировать ее для вас. Так как StackOverflow любит код, вот код для класса имени / фамилии выше.
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;
}
}