Является ли Hashmap списком ссылок, если я постоянно возвращаю один и тот же хэш-код для каждого объекта
Я знаю о внутренней реализации hashmap, и мне нужно понять, что, предположим, у меня есть class Student, и я предоставил плохую реализацию hashcode(), поэтому она всегда возвращает 1.
Теперь предположим, что у меня есть фрагмент ниже
Student s1=new Student("Jack");
Student s2=new Student("James");
Student s3=new Student("John");
.
.
.
.
.
till `n` times
Map<Student,String> studentMap=new HashMap<>();
studentMap.put(s1,"1000");
studentMap.put(s2,"1001");
studentMap.put(s3,"1002");
.
.
.
.
.
till `n` times
как мы знаем, put() метод внутренне вызывается hashcode(), чтобы найти положение корзины, теперь для каждого Student объекта хэш-код равен, поэтому будет происходить коллизия хэш-кода, и независимо от того, какая позиция корзины была рассчитана ранее, список ссылок на длинные записи был построен на одном и том же для всех Student объектов.
Теперь, если он становится списком ссылок, то get() становится дорогим, потому что для каждого объекта с одинаковым хэш-кодом он должен пройти через каждый узел списка ссылок, чтобы получить значение ввода key, поэтому здесь кажется, что цель нарушается, поскольку производительность снижается.
Поэтому я просто хочу знать, работает ли реализация так, или мне нужно исправить свое понимание. Пожалуйста, предложите мне лучшие статьи, сообщения или ответы, которые дадут мне полную ясность таких концептуальных сценариев.
тогда как избавиться от этого, помимо хорошей реализации hashcode(), какая лучшая альтернативная коллекция у нас есть в java для решения такого сценария
@ user9634982: единственная практическая альтернатива - реализовать Comparable и использовать TreeMap, чтобы гарантировать время O (log n) - хотя после того, как вы внедрили Comparable, современные версии HashMap также деградируют до TreeMap вместо связанного списка.
Хорошо, не могли бы вы опубликовать соответствующий код для достижения того же, как можно имитировать Treemap, реализуя Comparable для вышеуказанного сценария.
@jack после еще одного размышления, мне все еще кажется, что правильная реализация хеш-кода кажется лучшим вариантом - три строки кода против десятков, представленных в принятом ответе. Указание на это не способствует?
Ответы 1
Да, реализация HashMap такая же, как вы описали. Согласно документам:
Обратите внимание, что использование множества ключей с одним и тем же hashCode() — верный способ снизить производительность любой хеш-таблицы. Чтобы улучшить воздействие, когда ключи являются сопоставимыми, этот класс может использовать порядок сравнения ключей, чтобы помочь разорвать связи.
Вот простой пример того, как реализация hashCode и Comparable влияет на производительность HashMap:
class Student {
protected final String name;
public Student(String name) {
this.name = name;
}
@Override
public int hashCode() {
return 1;
}
}
class StudentComparable extends Student implements Comparable<StudentComparable> {
public StudentComparable(String name) {
super(name);
}
@Override
public int compareTo(StudentComparable o) {
return this.name.compareTo(o.name);
}
}
class StudentHashcode extends Student {
public StudentHashcode(String name) {
super(name);
}
@Override
public int hashCode() {
return Objects.hash(name);
}
}
При запуске этого кода:
public class Test {
public static void main(String[] args) {
int records = 20000;
System.out.println("Run #1: Without comparable nor hashCode");
populateMap(records, Student::new);
System.out.println("Run #2: With comparable");
populateMap(records, StudentComparable::new);
System.out.println("Run #3: With hashCode");
populateMap(records, StudentHashcode::new);
}
public static void populateMap(int records, Function<String, Student> builder){
Map<Student, Integer> map = new HashMap<>(records);
Student last = null;
long start = System.currentTimeMillis();
for (int i = 0; i < records; i++) {
last = builder.apply("Student:" + i);
map.put(last, i);
}
System.out.println("Insert took: " + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
map.get(last);
System.out.println("Get took: " + (System.currentTimeMillis() - start));
}
}
Дайте этот вывод на моем ноутбуке с OpenJDK 15:
Run #1: Without comparable
Insert took: 6573
Get took: 1
Run #2: With comparable
Insert took: 132
Get took: 0
Run #3: With hashCode
Insert took: 26
Get took: 0
Хорошо, не могли бы вы опубликовать соответствующий код для достижения того же, как можно имитировать Treemap, реализуя Comparable для вышеуказанного сценария.
@user9634982 user9634982 Я добавил пример реализации Comparable в ответ.
Да, все они будут помещены в одно и то же ведро с упомянутой вами проблемой «связанного списка».