一、数组和链表介绍
数组和链表是两种基本的数据结构，他们在内存存储上的表现不一样，所以也有各自的特点。
以5位同学去上课时坐座位为例，总结它们的特点和区别。
1.1、数组的特点
- 在内存中，数组是一块连续的区域。
也就是这5位同学必须坐在一起。 - 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。
比如上课时，为了保证五位同学可以坐在一起，必须提前订好五个连续的位置。这样的好处就是能保证五个人可以在一起。但是这样的缺点是，如果来的人不够五个，那么剩下的位置就浪费了。如果临时又多来了个人，那么五个就不够用了，这时可能需要将第六个位置上的人挪走，或者是他们六个人重新去找一个六连坐的位置，效率都很低。如果没有找到符合要求的座位，那么就没法坐了。 - 插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。 比如原来去了四个人，然后后来又去了一个人要坐在第三个位置上，那么第三个到第四个都要往后移动一个位子，将第三个位置留给新来的人。 当这个人走了的时候，因为他们要连在一起的，所以他后面几个人要往前移动一个位置，把这个空位补上。
- 随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。
- 不利于扩展，数组定义的空间不够时要重新定义数组。
1.2、链表的特点
- 在内存中可以存在任何地方，不要求连续。 在教室里五个人可以随便坐。
- 每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。第一个人知道第二个人的座位号，第二个人知道第三个人的座位号...
- 增加数据和删除数据很容易。 再来个人可以随便坐，比如来了个人要坐到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。
- 查找数据时效率低，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。要找到第三个人，必须从第一个人开始问起。
- 不指定大小，扩展方便。链表大小不用定义，数据随意增删。
1.3、各自的优缺点
数组的优点
- 随机访问性强
- 查找速度快
数组的缺点
- 插入和删除效率低
- 可能浪费内存
- 内存空间要求高，必须有足够的连续内存空间
- 数组大小固定，不能动态拓展
链表的优点
- 插入删除速度快
- 内存利用率高，不会浪费内存
- 大小没有固定，拓展很灵活
链表的缺点
- 不能随机查找，必须从第一个开始遍历，查找效率低
它们在读取、插入和删除时时间复杂度对比
| - | 数组 | 链表 |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
二、HashMap是一种哈希表，综合了数组和链表两者的特性
讲完数组和链表，我们再来讲讲HashMap。
伟大的程序员们一直在想：我们能不能综合数组和链表两者的特性，做出一种读取容易，插入、删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表（Hash table）。
哈希表有多种不同的实现方法，最常用的一种方法是拉链法，也叫“链表的数组” ，如图：
哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。这些元素一般情况是通过hash(key)%len的规则存储到数组中，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，1%16=1,2%16=2,3%16=3,4%16=4,5%16=5,17%16=1,33%16=1。所以1、17以及33都存储在数组下标为1的位置。
三、HashMap源码解析
3.1、HashMap类图结构
3.2、HashMap数据结构和重要概念
在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是指针（引用）。所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
从上图中我们知道HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。
见HashMap的源码（JDK1.8）：
transient Node<K,V>[] table;
// Node是单向链表，它实现了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// 构造函数：Hash值 键 值 下一个节点
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断两个node是否相等，若key和value都相等，返回true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
可以看出，HashMap里面实现一个静态内部类Node（JDK1.8之前的应该是Entry），其重要的属性有key、value、next，从属性key、value我们就能很明显的看出来Node就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Node<K,V>[] table，Map里面的内容都保存在Node<K,V>[] table里面。
3.3、HashMap的存取实现
存储
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);
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中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标）， 如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。
这里有一个特殊的地方。在JDK1.6中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
如下源码：
static final int TREEIFY_THRESHOLD = 8;
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
红黑树源码：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
...
// 红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子树
TreeNode<K,V> right; // 右子树
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // 颜色属性
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 返回当前节点的根节点
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
...
}
读取
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) {
// 如果第一个节点是TreeNode,说明采用的是数组+红黑树结构处理冲突
// 遍历红黑树，得到节点值
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;
}
有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：
从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
如果第一个节点是TreeNode,说明采用的是数组+红黑树结构处理冲突，遍历红黑树，得到节点值。
归纳
简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Node 对象。HashMap 底层采用一个 Node<K,V>[] 数组来保存所有的 key-value 对，当需要存储一个 Node 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。
3.4、HashMap的resize（rehash）
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
这里有个疑问：为什么默认初始化桶数组大小为16，为什么加载因子的大小为0.75，这两个值的选取有什么特点。
网上有位博主的回答如下，我也是比较认可这种说法。
通过看上面的代码我们可以知道这两个值主要影响的threshold的大小，这个值的数值是当前桶数组需不需要扩容的边界大小。
我们都知道桶数组如果扩容，会申请内存空间，然后把原桶中的元素复制进新的桶数组中，这是一个比较耗时的过程。既然这样，那为何不把这两个值都设置大一些呢，threshold是两个数的乘积，设置大一些就不那么容易会进行扩容了啊。
原因是这样的，如果桶初始化桶数组设置太大，就会浪费内存空间，16是一个折中的大小，既不会像1，2，3那样放几个元素就扩容，也不会像几千几万那样可以只会利用一点点空间从而造成大量的浪费。
加载因子设置为0.75而不是1，是因为设置过大，桶中键值对碰撞的几率就会越大，同一个桶位置可能会存放好几个value值，这样就会增加搜索的时间，性能下降，设置过小也不合适，如果是0.1，那么10个桶，threshold为1，你放两个键值对就要扩容，太浪费空间了。
这里的0.75，据说是Oracle的开发人员经过泊松分布得到的一个值。
怎么设置？
HashMap总共给出了4中构造方法。
1）HashMap（） 不带参数，默认初始化大小为16，加载因子为0.75；
2）HashMap（int initialCapacity） 指定初始化大小；
3）HashMap（int initialCapacity ,float loadFactor）指定初始化大小和加载因子大小；
4）HashMap(Map<? extends K,? extends V> m) 用现有的一个map来构造HashMap。
我在这里还有一个疑问：这里的16在实际使用HashMap的时候，如何根据业务去进行预设呢？
