Java中的HashMap是否安全碰撞

Question

我正在开发一个解析器，它需要将键值对放入hashmap中。

但关键可以有多个值，我可以这样

HashMap<String,ArrayList<String>>做。

但如果键的数量是非常大的，它开始与其他主要的散列码匹配会发生什么。

是否会重写上一个键的值？

Answer 1

如果映射中的关键字的哈希与现有键相撞时，地图会重新安排或保留的钥匙，散列下的列表。没有任何密钥会被其他密钥覆盖，这些密钥会在同一个分组中被排序。

如果多个线程正在使用的地图的同时，你可能会想，如果它不处理的并发访问同步访问地图。 （一些标准的Maps，其他则不包含，Java Collections软件包确实包含增加同步的包装类。）

Answer 2

首先，看看Google Collections Multimap这将让您指定每个键多个值，而无需手动维护值的列表。其次，不具有相同散列码的密钥不会相互冲突。哈希代码不保证或要求唯一; HashMap在内部为每个散列码维护一个“桶”的键/值对。

Answer 3

如果它与前一个键相等，它将只覆盖前一个键的值。有一些方法，如线性探测，重新哈希，桶等，这些方法在哈希实现中用来防止哈希码冲突覆盖不相等的密钥。

Answer 4

的HashMap是碰撞安全：看the sourcecode认沽：

 /** 
     * Associates the specified value with the specified key in this map. 
     * If the map previously contained a mapping for the key, the old 
     * value is replaced. 
     * 
     * @param key key with which the specified value is to be associated 
     * @param value value to be associated with the specified key 
     * @return the previous value associated with <tt>key</tt>, or 
     *   <tt>null</tt> if there was no mapping for <tt>key</tt>. 
     *   (A <tt>null</tt> return can also indicate that 
     *   previously associated <tt>null</tt> with <tt>key</tt>.) 
     */ 
    public V put(K key, V value) { 
     if (key == null) 
      return putForNullKey(value); 
     int hash = hash(key.hashCode()); 
     int i = indexFor(hash, table.length); 
     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))) { 
       V oldValue = e.value; 
       e.value = value; 
       e.recordAccess(this); 
       return oldValue; 
      } 
     } 

     modCount++; 
     addEntry(hash, key, value, i); 
     return null; 
    } 

和

 /** 
     * Adds a new entry with the specified key, value and hash code to 
     * the specified bucket. It is the responsibility of this 
     * method to resize the table if appropriate. 
     * 
     * Subclass overrides this to alter the behavior of put method. 
     */ 
    void addEntry(int hash, K key, V value, int bucketIndex) { 
     Entry<K,V> e = table[bucketIndex]; 
     table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
     if (size++ >= threshold) 
      resize(2 * table.length); 
    } 

像一个链表表行为的条目。当您将新条目放入同一个存储桶时，它只会添加到链接列表中。

Answer 5

我会贡献一个冲突是不一样的插入一个相同的密钥。当单独的键散列为相同的值时会发生冲突。据了解，任何实施Map界面的人都应该配备处理冲突。因此，你的问题的答案是，是的，Java中的HashMap可以安全地处理冲突。

但是，如果插入了相同的密钥，那么与相关联的上一个值将会更新/覆盖完全相同的密钥。这不被视为碰撞本身，而是直接破坏已有的东西。