HashMap原理分析

HashMap采用数组+链表的数据结构，只是在jdk1.7和1.8的实现上有所不同。

下面，简单的分析一下，方便自己更加深刻的理解这种典型的key-value的数据结构。

jdk1.7实现原理简单分析

1.7的HashMap数据结构图

在jdk1.8之前，HashMap由数组 + 链表组成，也就是链表散列。数组是HashMap的主体，链表实则是为了解决哈希冲突而存在的，（拉链法解决哈希冲突） 。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

1.7的HashMap类中的常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/** 初始化桶大小，HashMap底层是数组，这个是数组默认的大小 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**  桶的最大值 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/** 默认的负载因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final Entry<?,?>[] EMPTY_TABLE = {};

/** table真正存放数据的数组 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/** map中存放数据的大小 */
transient int size;

/** 桶大小。可以在初始化的时候显示指定 */
int threshold;

/** 负载因子，可以在初始化的时候显示指定 */
final float loadFactor;

loadFactor负载因子

默认的HashMap的容量是16，负载因子是0.75，当我们在使用HashMap的时候，随着我们不断的put数据，当数量达到 16 * 0.75 = 12的时候，就需要将当前的16进行扩容，而扩容就涉及到数据的复制，rehash等，就消耗性能，所谓的负载因子，也可以叫加载因子，用来控制数组存放数据的疏密程度，loadFactor越趋紧与1，说明数组中存放的 entry越多，链表的长度就越长。所以，建议当我们知道HashMap的使用大小时，应该在初始化的时候指定大小，减少扩容带来的性能消耗。

loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

threshold桶大小

threshold桶大小，也叫临界值，threshold = capacity * loadFactor，当HashMap的size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 threshold是衡量数组是否需要扩增的一个标准。

table存放数据的数组

table数组中存放的是Entry类型的数据，下面我们简单看看Entry的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    /** 创建一个新的Entry */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

Entry是一个内部类，其中的key就是写入的键，value就是写入的值，由于HashMap由数组+链表的形式，这里的next就是用于实现链表结构。hash存放的事当前key的hashcode值。

jdk1.8实现原理简单分析

在jdk1.7中HashMap实现原理分析，我们知道当hash冲突很严重的时候，链表的长度就会很长，我们也知道数组和链表的优缺点，简单总结一下：

数组：数据存储是连续的，占用内存很大，所以空间复杂度较高，但是二分查找的时间复杂度为O(1)，简单讲就是，数组寻址容易，插入和删除较为困难。

链表：存储区间零散，所以内存较为宽松，故空间复杂度较低，但是时间复杂的高，为O(n)，简单讲就是，链表寻址困难，插入和删除较为容易。

所以，在jdk1.8中，对HashMap的实现做了相应的修改，jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

1.8的HashMap的数据结构图

1.8的HashMap类的常量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/** 默认的初始容量16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/** 最大的容量 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/** 默认的填充因子 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/** 当桶上的节点数量大于8时，会将链表转为红黑树 */
static final int TREEIFY_THRESHOLD = 8;

/** 当桶上的节点数量小于6时，会将红黑树转为链表 */
static final int UNTREEIFY_THRESHOLD = 6;

/**桶中的结构转为红黑树对应的最小数组大小为64 */
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;

对比1.7中的常量，我们就会发现1.8中做了如下的改变。

1.增加了 TREEIFY_THRESHOLD，当链表的长度超过这个值的时候，就会将链表转换红黑树。

2.Entry修改为 Node，虽然 Node的核心也是 key、value、next。

HashMap插入数据时的流程图

小结

从上面的简单分析中，我们可以知道在jdk1.8之后，对HashMap的实现做了改变，主要在于将链表的长度超过临界值的时候，就将链表转为红黑树，利用红黑树的优点，可以更好的查找元素，使得查询的时间复杂度变为O(logn)

但是，jdk1.8并未有修改HashMap之前的线程安全问题，我们都知道HashMap是线程不安全的，涉及到线程安全的时候，我们应该使用 ConcurrentHashMap。