Java HashMap如何使用相同的散列代码处理不同的对象?

根据我的理解，我认为:

两个对象具有相同的hashcode是完全合法的。如果两个对象相等(使用equals()方法)，则它们具有相同的hashcode。如果两个对象不相等，那么它们就不能有相同的hashcode

我说的对吗?

如果我没猜错的话，我有以下问题: HashMap在内部使用对象的hashcode。那么，如果两个对象可以具有相同的hashcode，那么HashMap如何跟踪它使用的键呢?

有人能解释一下HashMap内部是如何使用对象的hashcode的吗?

当前回答

常言道，一图胜千言。我说:有些代码胜过1000字。下面是HashMap的源代码。获得方法:

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

因此，很明显，哈希是用来寻找“桶”的，并且总是在该桶中检查第一个元素。如果不是，则使用键的equals来查找链表中的实际元素。

让我们看看put()方法:

  /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

它稍微复杂一些，但很明显，新元素被放在选项卡中基于哈希计算的位置:

I = (n - 1) & hash这里I是新元素将被放置的索引(或者它是“桶”)。N是TAB数组(“桶”数组)的大小。

首先，尝试将其作为“bucket”中的第一个元素。如果已经有一个元素，则向列表中追加一个新节点。

2016-09-22 20:40:21

其他回答

hashcode决定要检查hashmap的哪个bucket。如果存储桶中有多个对象，则执行线性搜索以查找存储桶中的哪个项目等于所需的项目(使用equals()方法)。

In other words, if you have a perfect hashcode then hashmap access is constant, you will never have to iterate through a bucket (technically you would also have to have MAX_INT buckets, the Java implementation may share a few hash codes in the same bucket to cut down on space requirements). If you have the worst hashcode (always returns the same number) then your hashmap access becomes linear since you have to search through every item in the map (they're all in the same bucket) to get what you want.

大多数情况下，编写良好的hashcode并不完美，但它足够独特，可以为您提供或多或少的恒定访问。

2011-06-27 13:34:13

你的第三个断言是不正确的。

两个不相等的对象拥有相同的哈希码是完全合法的。它被HashMap用作“第一遍过滤器”，以便映射可以快速找到具有指定键的可能条目。然后测试具有相同哈希码的键是否与指定的键相等。

您不会希望要求两个不相等的对象不能具有相同的哈希码，否则将限制为232个可能的对象。(这也意味着不同类型甚至不能使用对象的字段来生成哈希码，因为其他类可以生成相同的哈希码。)

2011-06-27 13:34:39

两个对象相等，意味着它们具有相同的hashcode，而不是相反。 2个相等的对象------>他们有相同的hashcode 2个对象具有相同的hashcode ----xxxxx—>，它们不相等

HashMap中的Java 8更新

在代码中执行这个操作

myHashmap.put("old","old-value");
myHashMap.put("very-old","very-old-value");

所以，假设你的hashcode为“old”和“very old”两个键返回的hashcode是相同的。然后会发生什么。

myHashMap是一个HashMap，假设最初您没有指定它的容量。所以每个java的默认容量是16。所以现在只要你使用new关键字初始化hashmap，它就创建了16个桶。现在当你执行第一个语句

myHashmap.put("old","old-value");

然后计算“old”的hashcode，因为hashcode也可以是非常大的整数，所以，Java内部做了这个(hash是hashcode， >>>是右移)

hash XOR hash >>> 16

为了给出一个更大的图，它会返回一个索引值，在0到15之间。现在，键值对“old”和“old-value”将被转换为Entry对象的键值实例变量。然后这个entry对象会被存储在bucket中，或者你可以说在一个特定的索引处，这个entry对象会被存储。

入口是Map接口- Map中的一个类。条目，带有这些签名/定义

class Entry{
          final Key k;
          value v;
          final int hash;
          Entry next;
}

现在当你执行下一条语句时

myHashmap.put("very-old","very-old-value");

“very old”给出了与“old”相同的哈希码，所以这个新的键值对再次被发送到相同的索引或相同的存储桶。但是因为这个存储桶不是空的，所以Entry对象的下一个变量被用来存储这个新的键值对。

并且它将存储为每个具有相同hashcode的对象的链表，但TRIEFY_THRESHOLD的值为6。在此之后，链表转换为以第一个元素为根的平衡树(红黑树)。

2017-07-16 17:27:23

HashMap是一个Entry对象数组。

把HashMap看作是一个对象数组。

看看这个对象是什么:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

每个Entry对象表示一个键值对。如果一个桶有多个Entry，下一个字段引用另一个Entry对象。

有时候，两个不同对象的哈希码可能是相同的。在这种情况下，两个对象将保存在一个bucket中，并将显示为链表。入口点是最近添加的对象。该对象引用具有下一个字段的另一个对象，以此类推。最后一项指向null。

当使用默认构造函数创建HashMap时

HashMap hashMap = new HashMap();

数组的大小为16，默认负载平衡为0.75。

添加新的键-值对

计算键的hashcode 计算元素应该放置的位置哈希% (arrayLength-1)(桶号) 如果你试图用一个已经保存在HashMap中的键添加一个值，那么值将被覆盖。否则元素被添加到桶中。

如果存储桶已经有至少一个元素，则添加一个新元素并将其放置在存储桶的第一个位置。它的下一个字段指向旧元素。

删除

计算给定键的hashcode 计算桶号哈希% (arrayLength-1) 获取桶中第一个Entry对象的引用，并通过equals方法遍历给定桶中的所有条目。最终我们会找到正确的入口。如果没有找到所需的元素，则返回null

2013-08-28 15:58:57