背景
关于hashcode与equals的使用规范，我们已经知道（网上有很多相关介绍）。
1.必须使用同一属性来生成equals和hashcode方法。
2.必须同时重写hashcode和equals方法。
那么为什么会有这样的约定，其背后整个场景逻辑是怎么样的。
什么是hash
关于hash散列表 wiki上的定义如下：
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
比如有如下集合（1:a ,2:b ,3:c ,4:d ,5:e ,6:f ,7:g ,8:h），我想知道键值5对应的value是什么。我只能一个个遍历集合遇到key=5的话把结果返回。
但是如果对象（key:value）存放位置是根据hash算出来的。比如location=hash(key%/20)，此时我们不需要遍历集合直接就能够索引到5:e 这个数据。其本质上是给集合中给个元素赋予了 位置信息（知识）
hashcode 用来干嘛
"什么是hash"中描述了hash表的逻辑，hashcode也是同样的逻辑。通过hashcode我们可以知道数据在集合中的位置（这里说的位置就是逻辑位置其与物理节点对应，具体实现细节该文不做详解）。
如java中Hashtable就是通过hashcode来定位每个元素的,具体逻辑查看如下代码（关于hashtable的知识请见附录一栏）：
int hash = key.hashCode(); //给key计算hashCode(调用具体对象的hashCode)
int index = (hash & 0x7FFFFFFF) % tab.length; //计算在hashtable entry[]数组的下表位置。
当我要插入的时候就是通过hashcode来算出数组下标的位置，然后遍历该table[index]对应的链表。如果存在则把旧值替换否则增加，具体看如下hashTable.put()方法。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
//通过equals方法判断是否存在，如果存在就替换。
V old = entry.value;
entry.value = value;
return old;
}
}
// 不存在的话就把该值添加到 table[index]的第一个节点。
addEntry(hash, key, value, index);
return null;
}
具体addEntry 方法请见附录一栏。
往hashtable/hashset插入数据由于要维持数据的唯一性（hashtable中key唯一，hashset 元素唯一）。首先通过hash判断然后在用equals方法判断。其伪代码如下：
if (object1.hashcode() ！= object2.hashcode)
//在hashtable数据结构中同一个hashcode的数据放在一条链表上。tab[2]:node1 -> node2 -> node3
{
return false;
}
else{
if (object1.equals() ！= object2.equals())
{
return false;
}
}
从抽象意义上来说，hashcode可以判断是初步是否一样，通过equals判断是否完全一样。所以重写equals方法的时候必须重写hashcode。如果hashcode与equals方法对属性的判断不一样，可能在hashcode那一层就会走错方向。在hashtable数据结构中就是两个supObject(a,b),subObject(a,b) (subObject extend supObject，其两个equals方法一样), 算出hashcode不一样导致到hashtable entry[]数组中的下标就不同。
如
tab[3]:supObject
tab[4]:subObject
SupObject 与subObject伪代码见附录：
附录
HashTable.addEntry方法
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e); //tab[index]第一个几点就是刚刚put的新节点。
count++;
}
关于hashtable
为了平衡数组不易插入，链表、数组均不易索引的问题，很容易想到将key值转化为数组的下标、建立一个映射（将字符串转化为整数，或者直接就是整数，先这么简单理解，这也可能产生碰撞），然后再通过指针的方式指向具体的元素，即能快速查找，又能方便插入、删除。具体如下图所示
image.png
参考自：https://www.cnblogs.com/mingaixin/p/5156811.html
SupObject 与subObject类伪代码
SupObject 与subObject类如下所示：
class SupObject{
boolean equals()
{
return (getA() == null ? other.getA() == null : getA().equals(other.getA()))
&& (getB() == null ? other.getB() == null : getB().equals(other.getB()))
}
}
class SubObject{
boolean equals()
{
return (getA() == null ? other.getA() == null : getA().equals(other.getA()))
&& (getB() == null ? other.getB() == null : getB().equals(other.getB()))
}
}
网友评论