Hashmap以及它如何在场景后面工作

快速的问题，以确保我很清楚Java中的HashMap是如何工作的。

这是一个代码示例：

//String key = new String("key"); //String val = new String("value"); String key = "key"; String val = "value"; HashMap map = new HashMap(); map.put(key, val); System.out.println("hashmap object created. Its key hashcode = "+key.hashCode()); // the hashcode is 106079 System.out.println("hashmap object value for key = "+map.get(key)); // Let's store using a key with same hashcode Integer intkey = new Integer(106079); val = "value2"; map.put(intkey, val); System.out.println("hashmap object created. Its intkey hashcode = "+intkey.hashCode()); // this returns 106079 once again. So both key and intkey have the same hashcode // Let's get the values System.out.println("hashmap object value for intkey = "+map.get(intkey)); System.out.println("hashmap object value for key = "+map.get(key)); 

返回的值是预期的。 我在场景后面看到，HashMap的工作原理如下：

1. 得到关键/价值。
2. 从密钥中生成哈希码。
3. 存储桶中的密钥和值对象（在我的情况下，桶号106079）

对于第二个也是如此。

4. 将它存储在同一个存储桶中，但由于这是一个LinkedList，我想将它存储在“下一个可用的分配”中。

为拿到它，为实现它：

1. 拿起密钥，获取哈希码，
2. 看看水桶，
3. 然后查看LinkedList中第一个元素的键，
4. 然后检查密钥是否通过，元素是否匹配，如果没有，则继续下一个，依此类推，直到可以检索到值。

我能正确理解这个概念吗？

非常感谢！

编辑：

非常感谢，所以要完成： – Java HashMap如何在内部存储条目 – Java HashMap如何使用相同的哈希代码处理不同的对象？

和：

• 应该没有那么多“桶”
• 存储桶与条目不同。 存储桶是共享相同存储桶＃的所有条目的逻辑集合（在Java情况下，它是密钥的hashCode（）的函数）。 如其他答案所述，存储桶溢出可以通过多种方式实现，不一定在List中。
• 还有其他现有的冲突解决方案： http ： //en.wikipedia.org/wiki/Hash_table#Collision_resolution
• 它使用Object的equals方法来比较和检索同一个桶中的对象。

Answer 1

还请注意，HashMap可以通过多种方式实现哈希码冲突解决 ，而不仅仅是如上所述使用链表

Java的HashMap实现不仅使用LinkedList策略来处理具有相同key.hashCode()值的键值。

此外，您可能想阅读本文

Answer 2

是的，你的理解是正确的。 请注意，为单个存储桶分配了许多哈希码：在新的HashMap中，共有16个桶，每个桶总共分配了2 32/16 = 2 ^28个哈希码。

Answer 3

您的理解是可以的，但考虑到有几个实现。 HashMap用于存储值的实际哈希码可能不是106079.这是一个实现（java-6-openjdk）：

 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 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; } 

请注意hash方法，它包含以下内容：

 /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

所以在这个JVM的例子中，它不使用106079作为哈希，因为HashMap重新创建一个哈希来“硬化”它。

我希望有所帮助