初探
HashMap在java中的地位似 学界泰斗 深不可测，又如 三岁孩童 众人皆知。一个入门级别的集合类，在平时编程时都感觉so easy，但每每在面试时都感觉so hard。到底HashMap中隐藏着什么奥秘呢，今天尽量为大家揭开面纱！
- 本文会结合Jdk1.8的优化，对比HashMap和HashTable的区别，来更好的分析HashMap.
- 本文不纠结各名词的定义，只用追求用通俗的话把事情解释清楚，想更清楚了解概念的自己单独去百度、谷歌。
- 文中不当之处，还望指正。
认识数据结构
1、数组
数组结构示意
-----------------------------------------------------------------
| object | object | object | object | object | object |
-----------------------------------------------------------------
↑ ↑ ↑ ↑ ↑ ↑
index1 index2 index3 index4 index5 index6
数组中的元素存储在一个连续性的内存块中，数组声明必须声明数组长度，因此在new一个数组的时候jvm就能计算出所需空间，并未其分配内存。通过数组的下标访问数据是相当高效的，比链表要快很多，因为根据下标和数组元素大小可直接计算出数据偏移量，直接定位数据。
2、链表
-------- -------- -------- -------- --------
| Node | -> | Node | -> | Node | -> | Node | -> | Node |
-------- -------- -------- -------- --------
↑
指针（引用），也就是经常看到的类似 next 的东西，
单向链表每个对象持有下一个对象的指针，
双向链表还会有指向上一个对象的指针。
链表这种数据结构很好定义，HashMap里定义为：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //hash值
final K key; //键
V value; //值
Node<K,V> next; //下一个Node指针
}
链表的访问速度比数组要慢很多，因为必须要从前往后遍历的数，要找到第五个必须从第一个往后找，无法直接像数组一样定位。但这中特殊的数据结构，也给链表带来了灵活性，比如插入、删除等操作，可以只用更改前后节点，而数组必须牵一发动全身。
关于数组与链表的比较这里不多说，有兴趣自己去了解，这也是比较基础的东西。
HashMap的数据结构
数组+链表（拉链结构）
以数组为基础，数组内每个元素都是一个Node链表
-----------------------------------------------------------------
| Node | Node | Node | Node | Node | Node |
-----------------------------------------------------------------
↓ ↓
-------- --------
| Node | | Node |
-------- --------
↓
--------
| Node |
--------
思考两个问题：
- 如何为每个Node分配指定的数组下标（槽位）？
- 一个槽位分配到多个Node的时候怎么办？
模拟一个场景来回答上面两个问题：
槽位的确定是根据每个Node的key值的hash取模来确定的，假设node1的key的hash值为23，HashMap里初始化的数组大小为16，那么 23 % 16 = 7，那就将Node1放入tab[7]，再假设又来了node2，key值的hash为39， 39 % 16 = 7， 这是tab[7]里已经有了node1，因此将node2放在Node1的后面，即node1.next=node2，这就在数组上构成了链表。
这只是简单的思路模拟，实际的算法还请往下慢慢看
重点：HashMap之所以使用拉链结构，主要基于两个原因。
1.发挥数组的快速下标访问；
2.用链表解决hash槽位冲突
HashMap的初始化
HashMap为我们提供了几个构造方法：
//base jdk1.7
//1.无参构造
public HashMap() {
// this(16,0.75) 默认capacity=16，load_factor=0.75(影响因子)
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//2.指定capacity构造
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//3.指定capacity和loadFactor构造
public HashMap(int initialCapacity, float loadFactor) {
//...此处省略非法参数校验异常
this.loadFactor = loadFactor;
//此处并没有处理capacity，将capacity处理为2的N次方在第一个put的时候触发
threshold = initialCapacity;
init(); //子类实现，钩子
}
HashMap在初始化时，并没有初始化内部数组，这也是一种惰性策略，内部数组的初始化会在第一次put的时候触发：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold); //填充数组
}
//...其他暂时省略
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 找到大于等于toSize的2次幂
int capacity = roundUpToPowerOf2(toSize);
//threshold 阀值，控制实际hashmap的容量，capacity*影响因子
//hashmap的实际存放元素个数超过threshold时会进行扩容
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
抛个问题：capacity的大小为什么必须是2的幂次？
HashMap 之 put 方法详解
再次祥看put方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold); //初始化填充数组
}
if (key == null)
//允许放入null键，而HashTable会直接抛出异常
return putForNullKey(value);
//重新计算hash，HashTable直接使用key的hash
//至于为什么需要重新计算hash，这里涉及位运算，简单的说就是让高位参与取模，
//使hash散列更均匀，避免hash碰撞
int hash = hash(key);
//快速计算在数组中的下标，这里的快速二字是有意义的，利用2的幂次的特性，采用高效的位运算求模，这是上面为什么capacity的大小为什么必须是2的幂次的答案。
int i = indexFor(hash, table.length);
//遍历table[i]上的链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果key的hash值以及 key的引用地址或key的equals方法 判断key相等后，用新value替换老value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//代码走到这里说明是个新key-value，需要增加
modCount++; //modCount 记录hashmap的数据结构变动次数，很多地方会使用这个判断hashmap的是否有增加或者删除等操作。
addEntry(hash, key, value, i); //新增Entry
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //触发扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex); //新建Entry
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//这里真正新建，注意一点，新建的Entry在老的Entry前面，而jdk1.8新的在老的后面
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n; //老的Entry，被作为next放在新的后面
key = k;
hash = h;
}
这里差不多该回答capacity的大小为什么必须是2的幂次了，先把 上述代码的 indexFor(hash, table.length); 方法展开：
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
// 这里的快速求模算法要求length必须是2的幂次方，不然不好使
// 常规求模算法效率较这个位运算，效率差太多
return h & (length-1);
}
HashMap规定capacity必须为2的幂次，关键原因就是为了提高求模速度，在老的HashTable中，并无此要求，所以其求模还是使用 % ，效率较低。除此之外，jdk1.8还利用capacity的特性，重写了更高效的扩容算法，有兴趣的可以去看1.8的resize()方法；
//HashTable的求模
int index = (hash & 0x7FFFFFFF) % tab.length;
HashMap 之 get 方法详解
读到这里应该对HashMap有了一定的认识，get方法大家心里估计都有个数了，就是取key的hash值求模，找到下标，然后遍历下标上的链表，用hash和equals挨个对比，相同者get到了。
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
很简答吧！
HashMap 之 红黑树
在jdk1.8中，将hashmap的链表进行了进一步优化，如果单个槽位上的链表长度大于等于8时，会将链表转化为红黑树。至于红黑树是什么，简单来讲就是一个几乎平衡的二叉查找树，比链表的查找效率高很多，就不展开讲解了。看1.8的代码：
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)
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;
else if (p instanceof TreeNode)
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); //放在了尾部，与1.7不一样
// TREEIFY_THRESHOLD = 8
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))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap 和 HashTable 的一些区别
- 线程安全：HashTable使用简单粗暴，使用简单的方法级同步锁，而HashMap完全不管线程安全，所以HashMap不适合多线程下使用，非多线程不可，需考虑其他并发集合；
ps :方法级同步锁锁住的是运行时this对象，不同方法之间也是互斥的！- 效率：HashMap的效率不仅仅是快在无锁上，还有index算法，HashMap采用高效位运算计算index，效率更高，再就是1.8的红黑树和resize()优化，也提高了查找效率；
- Capacity：HashMap要求capacity必须为2的幂次方，HashTable无次要求；
- 散列：HashTable直接使用key的hash值，而HashMap对key的hash值进行位运算，散列更加均匀；
其实现在HashTable留给我的几乎只剩研究对比价值了，使用时其他新的集合框架都有更优秀的表现。
网友评论