当前位置：HashMap底层原理分析
2018/10/26 16:23 分类： 技术交流 浏览：256
定义
Map集合即key-value的集合，HashMap为Map接口的实现，表示无序，散列的key-value集合。
HashMap是我们使用非常多的Collection，它是基于哈希表的 Map 接口的实现，以key-value的形式存在。在HashMap中，key-value总是会当做一个整体来处理，系统会根据hash算法来来计算key-value的存储位置，可以通过key快速地存、取value。
HashMap存储示意图
Jdk1.8中，HashMap底层基于数组、链表、红黑树实现。在HashMap中，初始化一个数组长度为16的数组。在创建一个map对象后调用put方法，传入key值及value值，此时将key值进行hash运算得到的hash值作为该entry键值对在数组中的索引位置。此时确定该位置后，首先去判断该位置是否为null，如果为null，则将entry存储在该位置，如果不为null，此时将entry以链表的方式存储在数组中。当链表长度大于8时，将链表结构转为红黑树继续存储entry。
底层代码实现；
HashMap提供了4个构造函数：
HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
HashMap(Map<? extends K, ? extends V> m)：传入一个map以构造一个新的map，使用默认加载因子（0.75）。
在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8; (jdk1.8以后才有)
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组，总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
int threshold;
// 负载因子
final float loadFactor;
}
在类中定义的全局变量中
数组默认初始化的容量为2的4次方，最大容量为2的30次方，都必须为2的幂次；
负载因子为0.75，以此来作为判断是否需要进行数组是否需要扩容的重要依据。在创建map对象时，如果没有指定初始容量大小以及负载因子，则使用默认的全局变量，其中负载因子不能大于1，否则就没有了意义。
TREEIFY_THRESHOLD该参数作为链表是否转化为红黑树的依据，在存储entry键值对的过程中,如果链表的长度过长，会导致在取值的过程中，遍历链表的深度过深，浪费性能，因此，hashmap底层判断链表长度是否大于8，大于8后将链表转化为红黑树，而当红黑树节点小于6时，则转化为链表。
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;
//检测table是否为空，如果为空，则使用扩容函数进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果通过hash值取模得到的桶为空，则直接把新生成的节点放入该桶
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//以下为该桶不为空的逻辑
Node<K,V> e; K k;
//判断桶的第一个元素的key值是否相同（hash值相同，且能equals）
//如果相同，则返回当前元素（函数末尾进行统一处理）
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);
//插入之后，检查是否达到了转成红黑树结构的标准
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果在遍历过程中，发现了key值相同，则返回当前元素（函数末尾进行统一处理）
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;
//如果onlyIfAbsent为ture，则在oldValue为空时才替换
//否则直接替换
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//修改次数+1
//map的size加1，然后判断是否达到了threshold，否则进行扩容
//threshold由Node[] table的长度及loadFactor控制
if (++size > threshold)
resize();
//执行回调函数
afterNodeInsertion(evict);
return null;
}
putVal方法的主要逻辑是这样的：
1、如果数组还没有初始化（数组长度是0），则先初始化
2、通过hash方法计算key的hash值，进而计算得到应该放置到数组的位置
3、如果该位置为空，则直接放置此处
4、如果该位置不为空，而且元素是红黑树，则插入到其中
5、如果是链表，则遍历链表，如果找到相等的元素则替换，否则插入到链表尾部
6、如果链表的长度大于或等于8，则将链表转成红黑树
Get方法
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;
//如果table不为空，则再进行查询操作
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//先检查第一个元素是否key相同
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;
}
getVal方法执行逻辑如下：
1.判断表是否为空或者待查找的桶不为空
2.首先检查待查找的桶的第一个元素是否是要找的元素，如果是直接返回
3.桶内红黑树，则调用getTreeNode()查找红黑树
4.桶内是链表，遍历链表寻找节点
总结
在hashmap中，并没有在构造方法中初始化数组，而是在调用put方法时，初始化数组。此时判断数组长度是否为空，如果为空则使用默认的容量大小，初始化一个长度为16的数组；如果不为空则根据当前数组长度以及负载因子的乘积，确定是否需要对数组进行扩容，调用resize方法，扩容以后数组长度为当前数组长度的两倍，此时需要对链表和红黑树进行拆分，包括每一次新增，删除等操作都会红黑树结构进行重新的调整，因此时损耗行能的，这里不做过多的讲解。
赞 1
