HashMap, имеющий нуль как ключ

Question

Как HashMap внутренне различают null и 0 как ключ.

В соответствии с этим post хеш-код для null ключ 0, все верно? Если да, то оба должны идти в одном ковше по индексу 0, и должно быть одно значение в HashMap, но это не так, как работает HashMap.

Может ли кто-нибудь объяснить мне? хеш-код для null ключ в HashMap?

Пример кода:

HashMap<Integer,String> map=new HashMap<Integer,String>(); 
map.put(null, "abc"); 
map.put(0, "xyz"); // will it override the value for null as key? 

System.out.println(map.get(null)); // abc 
System.out.println(map.get(0));  // xyz 

Answer 1

Если да, то оба должны идти в том же ведре с индексом 0 ...

Correct.

и не должно быть одно значение в HashMap

некорректным. Для двух клавиш будет разделяемая запись. Это гарантируется спецификациями Map и HashMap; то есть javadocs говорят, что для каждого отдельного ключа будет отдельная запись. Реализация требуется, чтобы соответствовать спецификации ... и это так.

Перед тем, как Java 8, то, что HashMap обрабатывает столкновений, составляет цепь все записи, содержащие хэш в том же ведре. Логика HashMap.get(key) будет перебирать цепочку для соответствующего ведра, ища запись, соответствующую ключу. (В вашем примере кода, было бы отдельные элементы в цепи для null и Integer(0) ключей.)

В Java 8, работает так же, чтобы начать с, но есть оптимизация для случая, когда ключи все реализуют Comparable и цепи становятся слишком длинными. В этом случае длинные цепочки преобразуются в двоичные деревья ... так, что сканирование цепочки O(N) превращается в поиск дерева O(logN).

Answer 2

Оба случая относятся к hashCode()==0, но equals отличается, следовательно, двумя записями, и оба get возвращают связанные значения.

Случай с нулем:

public V put(null,"abc") {  
     if (key == null) 
        return putForNullKey(value); 
} 
private V putForNullKey(V value) { 
     .. 
     addEntry(0, null, value, 0); ==> 0th index with 0 hashCode 
     return null; 
    } 

Случай с 0:

public V put(K key, V value) {  
     int hash = hash(key.hashCode()); ==> 0 
     int i = indexFor(hash, table.length); ==> 0 
     for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
      Object k; 
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { ==> false 
       .. 
      } 
     } 

     modCount++; 
     addEntry(hash, key, value, i); ==> addition to link list 
     return null; 
    } 

Answer 3

Вы можете иметь некоторые ошибки с хэш.

1, когда ключ 0, хеш-код может не быть 0.Поскольку хэш-код является:

final int hash(Object k) { 
    int h = hashSeed; 
    if (0 != h && k instanceof String) { 
     return sun.misc.Hashing.stringHash32((String) k); 
    } 
    h ^= k.hashCode(); 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

2, когда ключ является пустым, JDK называют специальный метод, чтобы сделать,

if (key == null) 
    return putForNullKey(value); 

Да, когда ключ является нулем, хэш 0. Если вы хотите узнать больше, см. Исходный код JDK.

Answer 4

Это возможно потому, что в HashMap одного Entry не только ключ-значение пары, но и имеет next поле, так что это своего рода простой связанный список и добавление новой записи выглядит следующим образом:

void createEntry(int hash, K key, V value, int bucketIndex) { 
    Entry<K,V> e = table[bucketIndex]; 
    table[bucketIndex] = new Entry<>(hash, key, value, e); 
    size++; 
} 

e Локальная переменная (та, которая уже присутствовала) заканчивается как значение next в Entry для данных hash и bucketIndex.