HashMap 是什么？
在我们的印象里，HashMap是一个存储一对一关系的数据结构，
采用hash算法，所以读取和存储效率较高。
问题
- hash算法是如何实现的？
源码
注释
从类的注释我们可以得到以下内容
- HashMap是实现了Map接口的Hash Table
- HashMap几乎和HashTable一样，除了非线程安全和允许null key/value
- HashMap不保证数据顺序保持不变
- 常规操作保证稳定的效率（如get put）
- 遍历效率取决于Hash Table的大小和数据的大小
- HashMap的效率取决于初始容量和加载因数（加载因数表示数据量达到Hash Table容量的多少时，需要扩容）
- 扩容时，会重新排列数据（rehash）
- 初始加载因数是0.75，初始容量请根据实际需要设置（避免过多的扩容或者浪费空间）
- HashMap非线程安全，修改map的结构时，遍历会抛出异常
可以看到注释基本写的很全，会把我们关心的东西说清楚
实现
总结来说如下
- 通过自定义的Node存储Key和Value，记录一个对应关系
- 通过Node数组存储所有对应关系，数组的下标由key的hashcode和数组大小计算得出
- 如果数组下标相同，通过单链表将相同下标的Node保存起来
- 如果单链表的Node个数超过一定阈值，改为红黑树存储
- 如果Node的总个数超过一定阈值，扩容，重新排列Node
简单来看下get和put的实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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)
// 可以看到 下标的计算是 数组大小&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; // 对应下标第一个Node就是要修改的Node
else if (p instanceof TreeNode)
// 如果是以红黑树的形式存储，在树中找到插入或者修改的Node
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))))
// 找到要修改的Node
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// 修改找到的Node
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// modCount表示数据修改了
++modCount;
if (++size > threshold)
// 个数超出阈值，扩容
resize();
afterNodeInsertion(evict);
return null;
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
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))))
// 判断数组中此下标存的第一个是不是要找的Node
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;
}
总结
对于开发使用来说，需要有以下几点注意
- 非线程安全， 应该用封装HashMap的数据结构实现线程安全，或者使用Map m = Collections.synchronizedMap(new HashMap(...));创建线程安全的Map
- 初始大小根据具体使用情况决定，避免过多性能消耗，也不能设置的太大浪费空间
- HashMap遍历的顺序是不稳定的，可能根据数据的增多而变化
备注
此文中源码来源于 Android-28 SDK
