根据我的理解,我认为:
两个对象具有相同的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。
(源)
其他回答
这将是一个很长的答案,拿着饮料继续阅读…
哈希就是在内存中存储一个键-值对,可以更快地读写。它将键存储在数组中,值存储在LinkedList中。
假设我想存储4个键值对
{
“girl” => “ahhan” ,
“misused” => “Manmohan Singh” ,
“horsemints” => “guess what”,
“no” => “way”
}
为了存储键,我们需要一个4元素的数组。现在我如何将这4个键中的一个映射到4个数组索引(0,1,2,3)呢?
因此java找到单个键的hashCode并将它们映射到特定的数组索引。 哈希码公式是-
1) reverse the string.
2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .
3) So hashCode() of girl would be –(ascii values of l,r,i,g are 108, 114, 105 and 103) .
e.g. girl = 108 * 31^0 + 114 * 31^1 + 105 * 31^2 + 103 * 31^3 = 3173020
哈希和女孩!!我知道你在想什么。你对狂野二重唱的迷恋可能会让你错过一件重要的事情。
为什么java要把它乘以31 ?
因为,31是奇数质数形式为2^5 - 1。奇素数降低了哈希碰撞的概率
这个哈希码是如何映射到数组下标的呢?
答案是,哈希码%(数组长度-1)。在我们的例子中,“girl”被映射为(3173020 % 3)= 1。它是数组的第二个元素。
值“ahhan”存储在与数组索引1相关的LinkedList中。
HashCollision -如果您尝试使用上面描述的公式查找密钥“误用”和“horsemints”的hasHCode,您将看到两者都给出相同的1069518484。Whooaa ! !〇教训
2个相等的对象必须具有相同的hashCode,但如果没有保证 hashCode匹配,则对象相等。所以它应该存储 这两个值都对应于1号桶的“误用”和“horsemints” (1069518484% 3)。
现在哈希图看起来是-
Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 –
现在,如果有人试图找到键“horsemints”的值,java很快就会找到它的hashCode,对它进行模块化,并开始在LinkedList对应的索引1中搜索它的值。因此,这样我们就不需要搜索所有的4个数组索引,从而使数据访问更快。
但是,等一下。有3个值在那个linkedList对应的数组索引1,它如何找出哪一个是值为关键“horsemints”?
其实我撒谎了,我说HashMap只是在LinkedList中存储值。
它将两个键值对存储为映射条目。实际上Map是这样的。
Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 –
现在你可以看到,当遍历对应于ArrayIndex1的linkedList时,它实际上会将linkedList的每个条目的key与horsemints进行比较,当它找到一个时,它会返回它的值。
希望你读得开心:)
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
常言道,一图胜千言。我说:有些代码胜过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”中的第一个元素。如果已经有一个元素,则向列表中追加一个新节点。
记住这里对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");
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并不完美,但它足够独特,可以为您提供或多或少的恒定访问。