根据我的理解,我认为:

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

我说的对吗?

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

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


当前回答

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html上找到很好的信息

总结:

HashMap的工作原理是哈希

put(key, value): HashMap将key和value对象都存储为Map.Entry。Hashmap应用hashcode(key)来获取桶。如果有碰撞,HashMap使用LinkedList存储对象。

get(key): HashMap使用key Object的hashcode来查找桶的位置,然后调用keys.equals()方法来识别LinkedList中的正确节点,并在Java HashMap中返回该键的相关值对象。

其他回答

下面是针对Java 8版本的HashMap机制的粗略描述(它可能与Java 6略有不同)。


数据结构

哈希表 哈希值通过key上的Hash()计算,它决定对给定的键使用哈希表的哪个桶。 链表(单个) 当桶中的元素数量较小时,使用单链表。 红黑树 当一个桶中的元素数量很大时,使用红黑树。


类(内部)

地图。条目 在map中表示单个实体,即键/值实体。 HashMap。节点 节点的链表版本。 它可以表示: 哈希桶。 因为它有哈希属性。 单链表中的节点(因此也是链表的头)。 HashMap。TreeNode 节点的树版本。


字段(内部)

节点[]表 桶表(链表的头)。 如果一个bucket不包含元素,那么它就是null,因此只占用一个引用的空间。 设置<地图。入口> entrySet 实体的集合。 int大小 实体数量。 负载系数浮动 在调整大小之前,指示允许的哈希表有多满。 int阈值 下一个要调整大小的大小。 公式:阈值=容量* loadFactor


方法(内部)

int散列(关键) 按键计算哈希值。 如何映射哈希到桶? 使用以下逻辑: static int hashToBucket(int tableSize, int hash) { return (tableSize - 1) & hash; }


关于能力

在哈希表中,容量是指桶数,可以从table.length中获取。 Also可以通过threshold和loadFactor计算,因此不需要定义为类字段。

可以通过:capacity()得到有效容量


操作

按键查找实体。 首先通过哈希值找到桶,然后循环链表或搜索排序树。 用键添加实体。 首先根据key的哈希值找到桶。 然后试着找出它的值: 如果找到,则替换该值。 否则,在链表的开头添加一个新节点,或插入到排序树中。 调整 当达到阈值时,将哈希表的容量(table.length)翻倍,然后对所有元素重新哈希以重建表。 这可能是一次昂贵的手术。


性能

获取并放置 时间复杂度为O(1),因为: 桶通过数组索引访问,因此是O(1)。 每个桶中的链表长度较小,可见为O(1)。 树的大小也是有限的,因为当元素数量增加时将扩展容量并重新哈希,所以可以将其视为O(1),而不是O(log N)。

常言道,一图胜千言。我说:有些代码胜过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”中的第一个元素。如果已经有一个元素,则向列表中追加一个新节点。

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并不完美,但它足够独特,可以为您提供或多或少的恒定访问。

我不会详细介绍HashMap是如何工作的,但是会给出一个例子,这样我们就可以通过将HashMap与现实联系起来来记住它是如何工作的。

我们有Key, Value,HashCode和bucket。

在一段时间内,我们将把它们与以下内容联系起来:

一个社会 HashCode ->社会地址(总是唯一的) 社会中的房子 Key ->房屋地址。

使用Map.get(key):

Stevie想去他的朋友(Josse)的房子,他住在一个VIP社会的别墅里,让它成为javalavers社会。 Josse的地址是他的SSN(每个人都不一样)。 有一个索引,我们可以根据社会安全号找到协会的名字。 这个索引可以被认为是一个找出HashCode的算法。

SSN协会名称 92313(Josse’s) -爪哇 13214—AngularJSLovers 98080—javalover 53808 -生物爱好者


这个SSN(密钥)首先给我们一个HashCode(来自索引表),它只是社会的名字。 现在,多个房子可以在同一个社会中,所以HashCode可以是公共的。 假设,社会对两个房子都是公用的,我们如何识别我们要去哪个房子,是的,通过使用(SSN)密钥,它只是房子的地址

使用Map.put(关键字,值)

这将通过查找HashCode为该值找到一个合适的社会,然后存储该值。

我希望这能有所帮助,而且这是可以修改的。

hashmap是这样工作的(这有点简化,但它说明了基本机制):

它有许多“桶”,用来存储键值对。每个桶都有一个唯一的编号——用来标识该桶。当您将一个键值对放入映射时,hashmap将查看键的哈希码,并将该对存储在标识符为键的哈希码的bucket中。例如:密钥的哈希码为235 ->,存储在桶号为235的桶中。(注意,一个桶可以存储多个键-值对)。

当您在hashmap中查找一个值时,通过给它一个键,它将首先查看您给出的键的哈希代码。然后,hashmap将查看相应的存储桶,然后它将通过equals()比较您给出的键与存储桶中所有对的键。

现在,您可以看到这对于在map中查找键-值对是多么高效:通过键的哈希代码,哈希映射立即知道要在哪个bucket中查找,因此它只需要测试该bucket中的内容。

看看上面的机制,你也可以看到对键的hashCode()和equals()方法有什么必要的要求:

If two keys are the same (equals() returns true when you compare them), their hashCode() method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket). If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use equals() to tell them apart.