通过Debug 探寻Java-HashMap 实现原理：
一个简单的例子，代码如下，
测试方法 main:
public static void main(String[] args) {
KeyObj obj1 = new KeyObj("AAAA");
KeyObj obj2 = new KeyObj("BBBB");
KeyObj obj3 = new KeyObj("CCCCC");
KeyObj obj4 = new KeyObj("DDDDD");
HashMap<KeyObj, String> hashMap = new HashMap<KeyObj, String>();
hashMap.put(obj1, "aaaa");
hashMap.put(obj2, "bbbb");
hashMap.put(obj3, "ccccc");
hashMap.put(obj4, "ddddd");
System.out.println(hashMap.values());
}
KeyObj.java
public class KeyObj {
String keyStr;
public KeyObj(String keyStr) {
super();
this.keyStr = keyStr;
}
public String getKeyStr() {
return keyStr;
}
public void setKeyStr(String keyStr) {
this.keyStr = keyStr;
}
@Override
// 覆盖hashCode方法，使得key的单双数分别获得一致的hash值，方便测试
public int hashCode() {
if (keyStr.length() % 2 == 0) {
return 31;
}
return 95;
}
@Override
public boolean equals(Object obj) {
KeyObj obj1 = (KeyObj) obj;
if (this.keyStr.equalsIgnoreCase(obj1.keyStr))
return true;
return false;
}
}
运行测试方法main，Debug查看HashMap:
1.可以看到HashMap其实是有一个名称为table的Entry数组，我们使用HashMap的put方法，本质是把我们的Key-Value作为Entry对象放入到HashMap中。
2.HashMap的table数组初始大小为16.
3.为何我们put了4个对象却只使用了table[10] 与 table[14]?
查看put方法JDK代码：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold); // 3.1 table若为空创建table，16大小
}
if (key == null)
return putForNullKey(value); // 3.2 key若为空放入table[0]
int hash = hash(key); // 3.3 计算放入key的hash，值为调用KeyObj的hashcode方法，再hash
int i = indexFor(hash, table.length);
// 3.4 计算当前put的Enrty在table数组中精确位置(int i),跟踪代码可以很容易看出:
// 3.4.1 精确位置i是由key的hash值与table.length取模
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 3.5 遍历table[i]的Entry
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 3.6 若put相同key的KeyObj,则替换旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);// 3.7 创建Entry,当前table[i]的首节点变为当前put节点Entry对象的next节点，注：JDK8之前每一个table[i]上的Entry使用单链表存储的
return null;
}
理解了put，查看HashMap的get方法就很简单了：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
继续查看第四行getEntry方法：
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)]; // 找到table[i]，并便利该位置节点
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // 找到，返回
return e;
}
return null;
}
其他：
在put函数代码中有一个注释：
JDK8之前每一个table[i]上的Entry使用单链表存储的
一直到JDK7为止，HashMap的结构都是这么简单，基于一个数组以及多个链表的实现，hash值冲突的时候，就将对应节点以链表的形式存储。
这样子的HashMap性能上就抱有一定疑问，如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。
所以在JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树。