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