根据我的理解，我认为:
两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法)，则它们具有相同的hashcode。 如果两个对象不相等，那么它们就不能有相同的hashcode
我说的对吗?
如果我没猜错的话，我有以下问题: HashMap在内部使用对象的hashcode。那么，如果两个对象可以具有相同的hashcode，那么HashMap如何跟踪它使用的键呢?
有人能解释一下HashMap内部是如何使用对象的hashcode的吗?
当前回答
import java.util.HashMap;
public class Students {
String name;
int age;
Students(String name, int age ){
this.name = name;
this.age=age;
}
@Override
public int hashCode() {
System.out.println("__hash__");
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
System.out.println("__eq__");
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Students other = (Students) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
public static void main(String[] args) {
Students S1 = new Students("taj",22);
Students S2 = new Students("taj",21);
System.out.println(S1.hashCode());
System.out.println(S2.hashCode());
HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}
Output:
__ hash __
116232
__ hash __
116201
__ hash __
__ hash __
2
因此，在这里我们可以看到，如果对象S1和S2都有不同的内容，那么我们可以非常确定，我们覆盖的Hashcode方法将为两个对象生成不同的Hashcode(116232,11601)。因为有不同的哈希码，所以它甚至不需要调用EQUALS方法。因为不同的Hashcode保证对象中不同的内容。
public static void main(String[] args) {
Students S1 = new Students("taj",21);
Students S2 = new Students("taj",21);
System.out.println(S1.hashCode());
System.out.println(S2.hashCode());
HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}
Now lets change out main method a little bit. Output after this change is
__ hash __
116201
__ hash __
116201
__ hash __
__ hash __
__ eq __
1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally calls Equal method to verify this.
Conclusion
If hashcode is different , equal method will not get called.
if hashcode is same, equal method will get called.
Thanks , hope it helps.
其他回答
常言道，一图胜千言。我说:有些代码胜过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”中的第一个元素。如果已经有一个元素，则向列表中追加一个新节点。
下面是针对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)。
这将是一个很长的答案，拿着饮料继续阅读…
哈希就是在内存中存储一个键-值对，可以更快地读写。它将键存储在数组中，值存储在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的实现。从OpenJdk中获取。你可以看到它检查哈希值是否相等键值是否相等。如果第三点成立，那么检查键值是否相等就没有必要了。哈希码在键之前进行比较，因为前者是更有效的比较。
如果您有兴趣进一步了解这方面的知识，请参阅Wikipedia关于开放寻址冲突解决的文章，我认为这是OpenJdk实现使用的机制。这种机制与另一个答案中提到的“桶”方法略有不同。
import java.util.HashMap;
public class Students {
String name;
int age;
Students(String name, int age ){
this.name = name;
this.age=age;
}
@Override
public int hashCode() {
System.out.println("__hash__");
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
System.out.println("__eq__");
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Students other = (Students) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
public static void main(String[] args) {
Students S1 = new Students("taj",22);
Students S2 = new Students("taj",21);
System.out.println(S1.hashCode());
System.out.println(S2.hashCode());
HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}
Output:
__ hash __
116232
__ hash __
116201
__ hash __
__ hash __
2
因此，在这里我们可以看到，如果对象S1和S2都有不同的内容，那么我们可以非常确定，我们覆盖的Hashcode方法将为两个对象生成不同的Hashcode(116232,11601)。因为有不同的哈希码，所以它甚至不需要调用EQUALS方法。因为不同的Hashcode保证对象中不同的内容。
public static void main(String[] args) {
Students S1 = new Students("taj",21);
Students S2 = new Students("taj",21);
System.out.println(S1.hashCode());
System.out.println(S2.hashCode());
HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}
Now lets change out main method a little bit. Output after this change is
__ hash __
116201
__ hash __
116201
__ hash __
__ hash __
__ eq __
1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally calls Equal method to verify this.
Conclusion
If hashcode is different , equal method will not get called.
if hashcode is same, equal method will get called.
Thanks , hope it helps.
推荐文章
- Java 8接口方法中不允许“同步”的原因是什么?
- 如何找到Java堆大小和内存使用(Linux)?
- 使用Enum实现单例(Java)
- RabbitMQ与通道和连接之间的关系
- buildSessionFactory()配置方法在Hibernate中已弃用?
- Spring MVC -如何获得所有的请求参数在一个地图在Spring控制器?
- 如何在Java中按两个字段排序?
- 文件之间的差异。路径中的分隔符和斜杠
- 在方法参数中使用NotNull注释
- Spring MVC中处理可选参数的@RequestParam
- Tomcat:如何查找正在运行的Tomcat版本?
- “java”、“javaw”和“javaws”之间有什么区别?
- 将Date对象转换为日历对象
- 在Java中保存最后N个元素的大小有限的队列
- 如何运行一个类从Jar不是主类在其清单文件
