6

HashMap当我们使用put()方法在类中放置一个键实例说“键”和一个值实例说“值”时，HashMap该类在内部做什么。当我们说 时，它如何取回值hashMap.get(key)？

编辑：我不想在这里详细说明，基本上是试图了解大局以及在和操作中的作用equals()和hashcode()方法。put()get()

4

3 回答 3

18

如果您谈论更高的图片，就像下面一样。这里我将项目key称为Map

在放置物品时。

  1. hashcode密钥计算
  2. 如果basket存在hashcode，则使用equals键搜索该篮子中的键的方法来确定是否要添加或替换元素。
  3. 如果不存在，则创建新的篮子（重新散列）并将该元素添加到其中。

得到：

  1. 获取hashcode密钥
  2. 去那个篮子
  3. 在键上迭代使用equals将返回该篮子中的那个元素。
于 2012-07-19T11:49:47.417 回答
1

这就是 IBM jdk 1.6 中所做的（我相信所有供应商都差不多）

编辑

关于你可能equals有hashcode兴趣看到这篇文章。

编辑结束

 /**
 * Maps the specified key to the specified value.
 * 
 * @param key
 *            the key
 * @param value
 *            the value
 * @return the value of any previous mapping with the specified key or null
 *         if there was no mapping
 */
@Override
public V put(K key, V value) {
    return putImpl(key, value);
}

V putImpl(K key, V value) {
    Entry<K,V> entry;
    if(key == null) {
        entry = findNullKeyEntry();
        if (entry == null) {
            modCount++;
            if (++elementCount > threshold) {
                rehash();
            }
            entry = createHashedEntry(null, 0, 0);
        }
    } else {
        int hash = key.hashCode();
        int index = hash & (elementData.length - 1);
        entry = findNonNullKeyEntry(key, index, hash);
        if (entry == null) {
            modCount++;
            if (++elementCount > threshold) {
                rehash();
                index = hash & (elementData.length - 1);
            }
            entry = createHashedEntry(key, index, hash);
        }
        if ((cache != null) && (hash >> CACHE_BIT_SIZE == 0)
                && (key instanceof Integer)) {
            cache[hash] = value;
        }
    }

    V result = entry.value;
    entry.value = value;
    return result;
}
于 2012-07-19T11:36:04.273 回答
1

从onwords 开始，通过使用平衡树而不是链表来存储映射条目，可以提高键中存在大量冲突的对象java 8的性能。HashMap主要思想是，一旦哈希桶中的项目数超过某个阈值，该桶将从使用条目的链接列表切换到平衡树。在高哈希冲突的情况下，这将提高最坏情况下的O(n)性能O(log n).

基本上当一个桶变得太大时（目前：） TREEIFY_THRESHOLD = 8，HashMap动态地用树图的临时实现替换它。这样一来，O(n)我们就会变得更好，而不是悲观O(log n)。

的箱（元素或节点）TreeNodes可以像任何其他箱一样被遍历和使用，但在填充过多时还支持更快的查找。然而，由于绝大多数正常使用的 bin 并没有被过度填充，因此在 table 方法的过程中检查树 bin 的存在可能会被延迟。

Tree箱（即元素全部为 的箱TreeNodes）主要由 hashCode 排序，但在 ties 的情况下，如果两个元素属于相同的“<code>class C implements Comparable<C>”，那么它们的compareTo()方法用于订购。

因为TreeNodes它们的大小大约是常规节点的两倍，所以我们仅在 bin 包含足够的节点时才使用它们。当它们变得太小（由于移除或调整大小）时，它们会被转换回普通垃圾箱（目前：）UNTREEIFY_THRESHOLD = 6。在用户分布良好的情况hashCodes下，很少使用树箱。

链接到java 文档

集合框架增强

于 2017-04-02T14:28:36.227 回答