地图如何在内部输入重复密钥？

Question

我很困惑，当地图遇到重复密钥 - 它进入同一个桶，因此它检查相同的密钥并用新值替换。

当插入不同的关键字时会发生什么情况。

是否检查密钥以及它存储密钥的位置？

Answer 1

我假设你在谈论HashMap。让我们来看看source：

386  public V put(K key, V value) { 
387   if (key == null) 
388    return putForNullKey(value); 
389   int hash = hash(key.hashCode()); 
390   int i = indexFor(hash, table.length); 
391   for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
392    Object k; 
393    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
394     V oldValue = e.value; 
395     e.value = value; 
396     e.recordAccess(this); 
397     return oldValue; 
398    } 
399   } 
400 
401   modCount++; 
402   addEntry(hash, key, value, i); 
403   return null; 
404  } 

所以这里发生了什么就是put()方法散列键和访问相应的桶。然后，它遍历条目包含那里，如果发现其主要equal S中的给定键的条目，它将替换该条目与给定值值，即：

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; 

---

Entry是包含键值对的类。

Answer 2

地图不允许重复键。如果插入了具有相同密钥的元素，旧值将替换为新值。

例如：假设我的地图如下：

Key  Value Bucket 
A  Val1 1 
B  Val2 2 
C  Val3 1 

坎结构：

Bucket 1 : A -> C 
Bucket 2 : B 

当有人试图进入另一元件（C，VAL6）其中C是键;那么在插入之后地图结构将如下：

Key  Value Bucket 
A  Val1 1 
B  Val2 2 
C  Val6 1 

因此，值在地图中被替换。

坎结构：

Bucket 1 : A -> C 
Bucket 2 : B 

我们解决你问题的第二部分：当具有相同值的不同关键在同一个桶进入它只是增加桶（内部每个桶可能是就像一个ArrayList，其中元素添加在列表的末尾）。

例如：让我们假设我们正在加入以下对（d，缬氨酸7）上述地图和假设密钥d映射到桶1。然后在地图上结构将在插入之后，如下所示：

Key  Value Bucket 
A  Val1 1 
B  Val2 2 
C  Val6 1 
D  Val7 1 

坎结构：

Bucket 1 : A -> C -> D 
Bucket 2 : B 

Answer 3

当重复键输入，它只是替换为新的值前一个键的值。当一个不同的键被输入到同一个桶中时，它首先检查它是否是重复的，如果不是，那么它将添加该键并且它是相应的值。

Answer 4

A HashMap“bucket”是一个链表。列表中的每个元素都包含键，值，键的散列和指向列表中下一个元素的指针。

所以，当发生散列冲突时，散列表将迭代桶中的每个条目。它将输入哈希与插入密钥哈希以及输入密钥的输入密钥进行比较。如果他们都是平等的，它会取代价值。如果它通过整个存储桶而没有匹配，则会向存储桶中添加条目。