根据我的理解,我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
根据我的理解,我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
当前回答
记住这里对hashmap结构的解释,也许有人可以解释Baeldung上的以下段落:-
Java有接口Map的几个实现,每个实现都有自己的特殊性。
但是,现有的Java核心Map实现都不允许Map处理单个键的多个值。
正如我们所看到的,如果我们试图为同一个键插入两个值,第二个值将被存储,而第一个值将被删除。
它还将返回(由put(K键,V值)方法的每个正确实现):
Map<String, String> map = new HashMap<>();
assertThat(map.put("key1", "value1")).isEqualTo(null);
assertThat(map.put("key1", "value2")).isEqualTo("value1");
assertThat(map.get("key1")).isEqualTo("value2");
其他回答
你可以在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是这样工作的(这有点简化,但它说明了基本机制):
它有许多“桶”,用来存储键值对。每个桶都有一个唯一的编号——用来标识该桶。当您将一个键值对放入映射时,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.
每个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