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可以安全地處理衝突。

但是，如果插入了相同的密鑰，那麼與相關聯的上一個值將會更新/覆蓋完全相同的密鑰。這不被視爲碰撞本身，而是直接破壞已有的東西。