Java 中的 HashMap 碰撞安全吗
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1738963/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is HashMap in Java collision safe
提问by changed
I am developing a parser that needs to put key value pairs in hashmap.
我正在开发一个需要将键值对放在 hashmap 中的解析器。
But a key can have multiple values which i can do in this way
但是一个键可以有多个值，我可以这样做
HashMap<String,ArrayList<String>>.
HashMap<String,ArrayList<String>>.
But what happens if number of keys are very large and it start matching with other key's hashcode.
但是如果键的数量非常大并且它开始与其他键的哈希码匹配会发生什么。
Will that rewrite previous key's value ?
那会重写以前键的值吗？
回答by rsp
If the hash of the key in the map collides with an existing key, the Map will re-arrange or keep the keys in a list under that hash. No keys will get overwritten by other keys that happen so be sorted in the same bucket.
如果映射中键的散列与现有键发生冲突，映射将重新排列键或将键保留在该散列下的列表中。任何键都不会被发生的其他键覆盖，因此请在同一个存储桶中进行排序。
If multiple threads are using the map concurrently, you might want to synchronize access to the map if it does not handle concurrent access. (Some standard Maps do, other don't. The Java Collections package does contain wrapper classes that add synchronisation.)
如果多个线程同时使用映射，并且如果映射不处理并发访问，您可能希望同步对映射的访问。（一些标准 Map 可以，其他则不可以。Java Collections 包确实包含添加同步的包装类。）
回答by ChssPly76
Firstly, take a look at Google Collections Multimapwhich would let you assign multiple values per key without having to manually maintain list of values.
首先，看看Google Collections Multimap，它可以让您为每个键分配多个值，而无需手动维护值列表。
Secondly, no - keys that have the same hashcode will not collide. Hash codes are not guaranteed or required to be unique; HashMap maintains a "bucket" of key/value pairs for each hash code internally.
其次，no - 具有相同哈希码的键不会发生冲突。哈希码不保证或要求是唯一的；HashMap 在内部为每个哈希码维护一个键/值对的“桶”。
回答by Chip Uni
HashMap is collision-safe: look at the sourcecodefor put:
HashMap 是碰撞安全的：查看put的源代码：
/**
* 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;
}
and
和
/**
* 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);
}
The entries of the table act like a linked list. When you put a new entry into the same bucket, it just adds to the linked list.
表中的条目就像一个链表。当您将新条目放入同一个存储桶时，它只会添加到链表中。
回答by kodjeff1
I would contribute that a collision is not the same as inserting an identical key. Collisions occur when separate keys hash to the same value. It is understood that anyone who implements the Map interface should be equipped to handle collisions. Thus, the answer to your question is that yes, HashMap in Java does safely handle collisions.
我认为碰撞与插入相同的密钥不同。当不同的键散列到相同的值时会发生冲突。据了解，任何实现 Map 接口的人都应该具备处理冲突的能力。因此，您的问题的答案是肯定的，Java 中的 HashMap 确实可以安全地处理冲突。
However, if an identical key is inserted, then the previous Value associated with that exact same keywill be updated/overwritten. This is not considered a collision per se, but a direct clobbering of what is already there.
但是，如果插入了相同的密钥，则与该完全相同的密钥关联的先前值将被更新/覆盖。这本身不被认为是碰撞，而是对已经存在的东西的直接破坏。
回答by Anthony Mills
It will only overwrite the previous key's value if it is equal to the previous key. There are methods like linear probing, rehashing, buckets, etc., which are used in hash implementations to prevent hashcode collisions from overwriting unequal keys.
如果它等于前一个键，它只会覆盖前一个键的值。有线性探测、重新散列、桶等方法，用于散列实现中以防止散列码冲突覆盖不相等的键。
