根据我的理解,我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
根据我的理解,我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
当前回答
每个Entry对象表示键值对。如果一个桶有多于1个Entry,则字段next指向其他Entry对象。
有时候,两个不同对象的hashcode可能是相同的。在这种情况下,2个对象将保存在一个桶中,并将显示为LinkedList。入口点是最近添加的对象。该对象引用具有next字段的其他对象,等等。最后一项为空。 当您使用默认构造函数创建HashMap时
数组的大小为16,默认负载平衡为0.75。
(源)
其他回答
你在第三点上错了。两个条目可以具有相同的哈希码,但不相等。看一下HashMap的实现。从OpenJdk中获取。你可以看到它检查哈希值是否相等键值是否相等。如果第三点成立,那么检查键值是否相等就没有必要了。哈希码在键之前进行比较,因为前者是更有效的比较。
如果您有兴趣进一步了解这方面的知识,请参阅Wikipedia关于开放寻址冲突解决的文章,我认为这是OpenJdk实现使用的机制。这种机制与另一个答案中提到的“桶”方法略有不同。
下面是针对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)。
你可以在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中返回该键的相关值对象。
你的第三个断言是不正确的。
两个不相等的对象拥有相同的哈希码是完全合法的。它被HashMap用作“第一遍过滤器”,以便映射可以快速找到具有指定键的可能条目。然后测试具有相同哈希码的键是否与指定的键相等。
您不会希望要求两个不相等的对象不能具有相同的哈希码,否则将限制为232个可能的对象。(这也意味着不同类型甚至不能使用对象的字段来生成哈希码,因为其他类可以生成相同的哈希码。)
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.