一个题目来说equals和hashCode
概念原理相关 参见这里
下边程序结果是什么?
...
@Override
public boolean equals(Object obj) {
//类型检查
//...
return this.name.equals(((People) obj).name) && this.age == ((People) obj).age;
}
//@Override
//public int hashCode() {
// return name.hashCode() * 37 + age;
//}
public static void main(String[] args) {
People p1 = new People("foolchild", 24);
System.out.println(p1.hashCode());
Map<People, Integer> hashMap = new HashMap<People, Integer>();
hashMap.put(p1, 1);
System.out.println(hashMap.get(new People("foolchild", 24)));
}
...
扒扒HashMap的put和get
HashMap#put()
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 对put进来的key做hash
int hash = hash(key);
// 根据hash值确定在table中的index位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// e.hash值等于hash并且e.key与key逻辑相等或就是同一个引用,满足的话,就是同一个key,value替换为新值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//这里并发条件下可能造成死循环,resize,可能导致entry的next指针反转
addEntry(hash, key, value, i);
return null;
}
然后来看看hash(key) 和 indexFor()做了什么?
HashMap#hash()
根据key的hashCode再算出一个hashCode,在hashMap resize时,该值不变.为什么要这么算,其数学原理暂时不懂.
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
HashMap#indexFor()
根据hashCode计算该key在table中的index
对于table length 为2^n(n > 0),h & (length - 1) 其实就是 h % length,不过位运算比模运算效率高(之所以采用table采用2^n,这样可以保证平均分配,2^n - 1每一位都是1,然后又是与运算..
)
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
// 对于table.length,为2^n(n > 0)(这个必须的)
// h & (length - 1) 其实就是 h % length,不过前者效率高的多,这样可以保证分配平均
return h & (length-1);
}
最后来看看
hashMap#get()
public V get(Object key) {
if (key == null)
return getForNullKey();
//这里我们讨论的是非空的key,直接看getEntry
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
HashMap#getEntry
只有e.hash == hash(key),且e.key == key 或者e.key equals key才返回e.
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//hash(key) 是否熟悉,忘了的话看上边
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 这段逻辑是否熟悉,忘了的话看上边,再贴一遍吧
// e.hash值等于上hash并且e.key与key逻辑相等或就是同一个引用,满足的话,就是同一个entry,返回改entry
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
结论
最后一行的方法调用链如下:
hashMap.get(new People("foolchild", 24)) -> HashMap#get() -> HashMap#getEntry() -> HashMap#hash(Object k)
因为只重写了equals没重写hashCode,e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k))) hash值的条件肯定过不去啊,
所以上述例子返回null