Зачем нам нужен LinkedHashMap, если keySet() поддерживает порядок для HashMap?
public class HashMapKeySet {
public static void main(String[] args) {
Map<HashCodeSame,Boolean> map=new HashMap();
map.put(new HashCodeSame(10),true);
map.put(new HashCodeSame(2),false);
for(HashCodeSame i:map.keySet())
System.out.println("Key: "+i+"\t Key Value: "+i.getA()+"\t Value: "+map.get(i)+"\t Hashcode: "+i
.hashCode());
System.out.println("\nEntry Set******");
for(Map.Entry<HashCodeSame, Boolean> i:map.entrySet())
System.out.println("Key: "+i.getKey().getA()+"\t Value: "+i.getValue()+"\t Hashcode: "+i.hashCode());
System.out.println("\nValues******");
for(Boolean i:map.values())
System.out.println("Key: "+i+"\t Value: "+map.get(i)+"\t Hashcode: "+i.hashCode());
}
static class HashCodeSame{
private int a;
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
HashCodeSame(int a){
this.a=a;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
HashCodeSame that = (HashCodeSame) o;
return a == that.a;
}
@Override
public int hashCode() {
return 1;
}
}
}
Если вы могли видеть в приведенном выше примере, я явно сделал, чтобы hashcode() возвращал 1 во всех случаях, чтобы проверить, что происходит, когда в hashmap происходит столкновение key.hashcode(). Что происходит, для этих объектов Map.Entry поддерживается связанный список, такой как
1(key.hashcode()) будет ссылаться на <2,false> будет ссылаться на <10, true>
(как ложное значение вводится после истинного значения, как я понимаю).
Но когда я делаю keySet(), сначала возвращается true, а затем false, вместо false сначала.
Итак, что я предполагаю здесь, так как keySet () является множеством и поддерживает порядок, мы получаем true и false во время итерации. Но, опять же, почему бы нам не сказать, что hashmap поддерживает порядок, поскольку единственный способ получить это по порядку. Или почему мы используем LinkedHashMap?
Key: DS.HashMapKeySet$HashCodeSame@1 Key Value: 10 Value: true Hashcode: 1
Key: DS.HashMapKeySet$HashCodeSame@1 Key Value: 2 Value: false Hashcode: 1
Entry Set******
Key: 10 Value: true Hashcode: 1230
Key: 2 Value: false Hashcode: 1236
Values******
Key: true Value: null Hashcode: 1231
Key: false Value: null Hashcode: 1237
Теперь, когда я добавляю chsnge метод hashcode, чтобы вернуть подобное
@Override
public int hashCode() {
return a;
}
Я получаю обратный заказ. Плюс на добавление
map.put(new HashCodeSame(10),true);
map.put(new HashCodeSame(2),false);
map.put(new HashCodeSame(7),false);
map.put(new HashCodeSame(3),true);
map.put(new HashCodeSame(9),true);
полученный результат есть,
Key: DS.HashMapKeySet$HashCodeSame@2 Key Value: 2 Value: false Hashcode: 2
Key: DS.HashMapKeySet$HashCodeSame@3 Key Value: 3 Value: false Hashcode: 3
Key: DS.HashMapKeySet$HashCodeSame@7 Key Value: 7 Value: false Hashcode: 7
Key: DS.HashMapKeySet$HashCodeSame@9 Key Value: 9 Value: true Hashcode: 9
Key: DS.HashMapKeySet$HashCodeSame@a Key Value: 10 Value: true Hashcode: 10
Entry Set******
Key: 2 Value: false Hashcode: 1239
Key: 3 Value: false Hashcode: 1238
Key: 7 Value: false Hashcode: 1234
Key: 9 Value: true Hashcode: 1222
Key: 10 Value: true Hashcode: 1221
Values******
Key: false Value: null Hashcode: 1237
Key: false Value: null Hashcode: 1237
Key: false Value: null Hashcode: 1237
Key: true Value: null Hashcode: 1231
Key: true Value: null Hashcode: 1231
Теперь это снова заставляет меня задуматься, почему заказ поступает сортированным образом? Кто-нибудь может объяснить мне подробно, как работает keySet(), entrySet() методы hashmap?
2 ответа
HashMap не имеет определенного порядка итераций, и LinkedHashMap имеет определенный порядок итераций.
Сложность с HashMap в том, что легко построить простые примеры, где порядок итераций вполне предсказуем и достаточно стабилен, хотя это не гарантируется.
Предположим, например, что вы сделали это:
Map<String, Boolean> map = new HashMap<>();
String str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for (int i = 0; i < str.length(); i++) {
map.put(str.substring(i, i+1), true);
}
System.out.println(map.keySet());
Результат
[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z]
Привет! Те в порядке! Ну, причина в том, что функция hashCode() в String довольно паршивая, и она исключительно паршивая для односимвольных строк. Вот спецификация String hashCode(). По сути, это сумма и умножение, но для строки из одного символа это просто значение Unicode этого char, Таким образом, хэш-коды односимвольных строк выше 65, 66, ... 90. Внутренняя таблица HashMap всегда является степенью двойки, и в этом случае это 64 записи в длину. Используемая запись таблицы является ключом hashCode() значение смещено вправо на 16 бит и XORed само с собой, по модулю размера таблицы. ( См. Код здесь.) Таким образом, эти односимвольные строки заканчиваются в последовательных сегментах в HashMap таблица, в позициях массива 1, 2, ... 26.
Итерация ключей происходит последовательно через сегменты, поэтому ключи в конечном итоге выходят в том же порядке, в котором они были вставлены. Опять же, это не гарантируется, просто так происходит из-за характеристик различных частей реализации как описано выше.
Теперь рассмотрим HashCodeSame где hashCode() Функция возвращает 1 каждый раз. Добавление нескольких из этих объектов в HashMap приведет к тому, что все они окажутся в одном и том же сегменте, и поскольку итерация проходит последовательно по связанному списку, они будут отображаться в следующем порядке:
Map<HashCodeSame, Boolean> map = new HashMap<>();
for (int i = 0; i < 8; i++) {
map.put(new HashCodeSame(i), true);
}
System.out.println(map.keySet());
(Я добавил toString() метод, который делает очевидную вещь.) Результат:
[HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(5), HCS(6), HCS(7)]
Опять же, ключи появляются по порядку из-за совпадения реализации, но по другим причинам, чем указано выше.
Но ждать! В JDK 8 HashMap преобразует сегмент из линейного связанного списка в сбалансированное дерево, если в одном сегменте появляется слишком много записей. Это происходит, если более 8 записей попадают в одну корзину. Давайте попробуем это:
Map<HashCodeSame, Boolean> map = new HashMap<>();
for (int i = 0; i < 20; i++) {
map.put(new HashCodeSame(i), true);
}
System.out.println(map.keySet());
Результат:
[HCS(5), HCS(0), HCS(1), HCS(2), HCS(3), HCS(4), HCS(6),
HCS(18), HCS(7), HCS(11), HCS(16), HCS(17), HCS(15), HCS(13),
HCS(14), HCS(8), HCS(12), HCS(9), HCS(10), HCS(19)]
Суть в том, что HashMap не поддерживает определенный порядок итераций. Если вы хотите определенный порядок итераций, вы должны использовать LinkedHashMap или отсортированная карта, такая как TreeMap, К несчастью, HashMap имеет порядок итераций, который является достаточно стабильным и предсказуемым, фактически достаточно предсказуемым, чтобы заставить людей думать, что его порядок четко определен, хотя на самом деле это не так.
Чтобы помочь в решении этой проблемы, в JDK 9 новые реализации коллекций на основе хешей будут рандомизировать свой порядок итераций от запуска к запуску. Например:
Set<String> set = Set.of("A", "B", "C", "D", "E",
"F", "G", "H", "I", "J");
System.out.println(set);
Это напечатало следующее при запуске в различных вызовах JVM:
[I, H, J, A, C, B, E, D, G, F]
[C, B, A, G, F, E, D, J, I, H]
[A, B, C, H, I, J, D, E, F, G]
(Порядок итераций стабилен в течение одного запуска JVM. Также существуют существующие коллекции, такие как HashMap их порядок итераций не рандомизирован.)
Ответьте на свой вопрос в Java doc для LinkedHashMap
Реализация хэш-таблицы и связанного списка интерфейса Map с предсказуемым порядком итераций. Эта реализация отличается от HashMap тем, что поддерживает двусвязный список, проходящий через все его записи. Этот связанный список определяет порядок итераций, который обычно является порядком, в котором ключи были вставлены в карту (порядок вставки). Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставлен в карту. (Ключ k повторно вставляется в карту m, если m.put(k, v) вызывается, когда m.containsKey(k) возвращает true непосредственно перед вызовом.)
Эта реализация избавляет своих клиентов от неуказанного, как правило, хаотического порядка, предоставляемого HashMap (и Hashtable), без увеличения стоимости, связанной с TreeMap. Его можно использовать для создания копии карты, которая имеет тот же порядок, что и оригинал, независимо от реализации оригинальной карты:
void foo(Map m) {
Map copy = new LinkedHashMap(m);
...
}