Java集合框架--HashMap
本篇主要来介绍JDK8的集合框架Map集合里最终的实现类HashMap，从名字的读法来说，Hash与Map。'Map'是集合，那'Hash'呢，Hash其实是指哈希表，也称散列表。
1 哈希表
Hash表，也称散列表，他的主要思想是，将一个key通过一定的散列函数进行运算，映射到表中的特定位置，从而达到访问这个位置的内容，以此来提高查询的速度。
散列表.jpg
从上图我们可以看出，当我们使用一个Key查找对应的Value时，这个key被散列函数，转换成了例外的Key，通过这个Key去获得对应的value
举个大家都有个经历的例子，大家都用过汉语词典。当我们查询某个汉字时，我们会把这个汉字转换成拼音，然后根据拼音，在字典目录查找这个拼音对应的汉字在字典的哪一页，然后在确定具体的目标汉字是那个
从上面的例子，大家可以发现，散列表的好处，可以通过一种转换规则（散列函数）快速的将要找到的目标确认。我们通过拼音快速确认汉字在哪一页，但是如果让我们直接去汉语词典查找这个汉字，可能就有点耗时耗力，可能需要翻遍整本词典。
但同时存在另外一个问题，我们知道汉语有一音多字的情况，按照我们使用字典的习惯，还是先根据汉字，转换成拼音，然后根据目录查找拼音在哪一页，拼音一致的不同汉字都会在这个页数的当页或者后面几页，通过一个个汉字的过滤，我们也能最终确认目标汉字具体的位置。
同样的Hash表也存在这样的问题，目前有两种做法
链地址法：类似字典的做法，相同的Key，对应的目标，连接在一起。形成一个子集合。但这样，也会存在一个，当数据量大的时候，子集合会很大很长。查找的时间也就变长了。HashMap在JDK8版本做了一次优化，后面我们会看到开放地址法：字典的目录，只是显示了这个读音的拼音在哪一页，举例，'liu'这个拼音的汉字有'刘'，'六'，'流'等等，我们查到'liu'这个拼音在100，101页，在第100页的可能包含上面两个'liu'，那开放地址法，会在目录告诉你'刘'在100页，'流'在101页第2行，'六'在101页第三行等。但这样依然会发现，100页的仍然存在两个相同的，即使在细分到多少页，多少行，可能这个冲突的问题仍然存在，因此，开放地址法需要一个良好的，分部均匀的散列函数。
2 HashMap
我们都知道，HashMap在JDK7中，他的数据结构为数组 + 链表，而在JDK8版本中，数据结构优化为数组 + 链表 + 红黑树构成，相比于老版本，数据结构复杂了，但同时查询性能也变得高了。下图展示了HashMap的数据结构。
HashMap数据结构.jpg
2.1 HashMap类结构
HashMap类图.jpg
HashMap实现了Cloneable（对象复制）、Serializable（序列化）、Map（集合），同时又继承自AbstractMap。
PS：不知道大家看到这个类图结构的时候，有没有发现什么有意思的事情，HashMap既然已经继承自AbstractMap，但同时又实现了Map接口。感兴趣的同学可以自己百度百度，在StackOverFlow上面有答案
接下来，我们看一下HashMap类的内部属性和方法：
- 属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30;//默认集合的最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子
static final int TREEIFY_THRESHOLD = 8;//链表长度，大于这个数会转换成红黑树
static final int UNTREEIFY_THRESHOLD = 6;//红黑树的元素数小于这个数时转换成链表
static final int MIN_TREEIFY_CAPACITY = 64;//当数组的大小小于这个数时，即使链表的长度已经达到了8，也只是进行扩容；只有当数组的大小大于等于64时，才会在链表长度达到8时，进行转换成红黑树
transient Node<K,V>[] table;//HashMap数据结构中的数组，长度为2的幂
transient Set<Map.Entry<K,V>> entrySet;//集合中的所有实体
transient int size;//集合中所有实体的个数
transient int modCount;//修改次数，主要是用于迭代时候的快速失败，防止篡改
int threshold;//resize的临界值 threshold = CAPACITY * LOAD_FACTOR
final float loadFactor;负载因子
- 方法
- 无参构造方法
/**
* 默认数组大小16，默认负载因子0.75f
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 指定容量、负载因子构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果入参大于最大数组容量，采用最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
//取大于入参的最小2次幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
}
- 外部集合构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 如果当前集合为空，对当前集合进行扩容。扩容完毕遍历插入到当前集合
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
- Hash散列函数
//获取key的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//数组大小-1对hash值取模，确认key对应的数组下标
i = (table.length - 1) & hash;
- put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key ==> key对应的hash值
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value ==>如果key对应的value存在，是否覆盖
* @param evict if false, the table is in creation mode. ==> false为创建模式
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前为空数组，则进行扩容，第一次采用默认值 16，0.75f
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果对应的key不存在，则直接插入
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))))//如果key已经存在value，则覆盖
e = p;
else if (p instanceof TreeNode) //如果当前链表已经变为红黑树，进行红黑树插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//如果链表中不存在对应的key，则将值插入到链表，如果链表长度大于8，则尝试转换成红黑树
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))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key 用户LinkedHashMap
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//修改次数
if (++size > threshold)//超过最大数，则扩容
resize();
afterNodeInsertion(evict); //LinkedHashMap使用
return null;
}
- HashMap的扩容机制
举个例子说明扩容机制，假设例子所有的key参数不会产生Hash冲突
| 操作步骤 | 说明 |
|---|---|
| 采用无参构造方法创建HashMap | 负载因子默认0.75f |
| put（1, 1） | 初始数组16，负载因子0.75f，最大扩容阈值16*0.75=12 |
| 一直put到put(12,12) | 数组16，负载因子0.75f，此时当前数组占用量=最大扩容阈值了，进行扩容。判断当前数组容量>=16 且<=2^30次方，将数组扩容2倍，最大扩容阈值扩容2倍，然后将数组中的key进行运算，分散到扩容后的数组。JDK7之前会重算所有hash，JDK8中，每次扩容一倍，这样，就不需要所有的都需要重算hash，只要bit位为1的进行当前序列+1即可。 |
- get查找元素
- 根据key通过散列函数，等到实际的数组下标，遍历数组内的链表或者红黑树，查找目标
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))))
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;
}
- remove删除元素
① 根据key获取数组下标
② 如果链表只有一个元素，找到目标
③ 如果是红黑树，查找红黑树，找到返回目标，否则nunll
④ 如果是链表，且有多个元素，循环遍历查找，找到返回目标，否则null
⑤ 找到目标后，判断是否是红黑树，如果是红黑树，删除节点，且平衡红黑树
⑥ 如果是链表，则将此目标的前指针的后指针指向目标的后指针
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
3 总结
针对HashMap的主要内容就上面这些，HashMap的几个特点
- 数据结构：数组 + 链表 + 红黑树
- 非线程安全：上线的源码中，并未看见线程安全的控制
- 无序
- 查询效率快，时间复杂度O(1)
