Thinking in Java之HashMap源码分析(五)

package com.kiritor;

public class Student {
String name;

public Student(String aa) {
// TODO Auto-generated constructor stub
name = aa;
}

@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
return this.name.equals(((Student) obj).name);
}

public static void main(String[] args) throws InterruptedException {

HashMap hashMap = new HashMap<>();
hashMap.put(new Student("AA"), "HEHE");
hashMap.put(new Student("AA"), "HEHE");
System.out.println(new Student("AA").name.equals(new Student("AA").name));
System.out.println(hashMap.size());

}

}
结果为：true 2 明显和我们的初衷背离了，因此这是我们序注意的地方。

思考2：hash冲突

一个有意思的情况出现：

我们仔细思考可以发现的是不同的hashCode产生的索引可能相同，这就是hash冲突，如何解决
这一问题呢？其实这里就是“链表数组”的IMBA之处了。详细的处理情况还是在for循环中。

[java]
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
} 简单的分析下：假设table[0]！=null，其键为key1,当第二次插入的时候key2的哈希码虽然和key1不同，

但是获得的索引却是0，产生了hash冲突。进入for循环体，由于key1、key2的哈希不同，所以if判断为false

之后key1=key1.next(说法不准，这里直接就以key当做键值对元素吧)，再然后执行for之后的插入语句

[java]
// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null;

// 如果i索引处的Entry为null，表明此处还没有Entry。
modCount++;
// 将key、value添加到i索引处。
addEntry(hash, key, value, i);
return null; key2被插入进key1的位置，同时key2.next指向的是key1，ok看明白了吗？这样hash冲突的问题就

通过链表数组的形式被解决了。简单的用图形展示

这里HashMap解决hash冲突的方法就是通过链地址法来的。

这里笔者也给出其他的冲突解决方式，有兴趣的朋友可以研究下：

1）开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

2）再哈希法

3）链地址法

4）建立一 公共溢出区

4、读取元素
说完了元素的存储，我们来看看，HashMap是如何来读取元素的吧，这里我们简要的分析

下get(key)方法

[java]
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);

return null == entry null : entry.getValue();
}

public V get(Object key) {
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);

return null == entry null : entry.getValue();
} 对于key为空