theme: channing-cyan

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

HashMap 数据结构与特性

一直在使用HashMap，也知道它是线程不安全的，那么它为什么是线程不安全的呢，这一篇先从HashMap的数据结构和特性说起。

hashMap原理

使用HashMap也很简单，放入key-value即可。

```

public static void main(String[] args) throws InterruptedException {

HashMap map = new HashMap();

map.put(1, "张三");

map.put(2, "李四");

map.put(3, "王五");

map.put(4, "赵六");

System.out.println("size:" + map.size());

}

```

这是我们常用的一种方式，我们不用过多的关心HashMap的内部操作，只需要简单的调用即可。

那HashMap中究竟发生了什么？

打开HashMap的类，我们把new HashMap() 当作入口。

```

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).

// 构造一个具有默认初始容量（16）和默认负载因子（0.75）的空哈希映射。

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

```

负载因子

这里有一个负载因子，听起来很复杂，它其实就是个变量，代表着达到（容量*负载因子）时开始扩容。

至于负载因子为什么默认是0.75，可能取的是个折中值，看到一篇文章在JDK1.7上对负载因子的描述：

```

作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

```

默认容量

查看源码得知，HashMap的默认容量为 1 << 4，也就是16。

当阈值达到（16*0.75）时开始扩容

扩容机制

```

static final int MAXIMUM_CAPACITY = 1 << 30;

```

HashMap的容量是有上限的，必须小于1<<30，换算为1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE

JDK1.7下的扩容机制

除了构造方法和默认构造方法会指定一些默认值外，如果不是第一次扩容，则新容量 = 旧容量 * 2；新阈值 = 新容量 * 负载因子

JDK1.8下的扩容机制

除了构造方法和默认构造方法会指定一些默认值外，如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

数据结构

```

static class Node implements Map.Entry {

final int hash;

final K key;

V value;

Node next;

}

```

hash: key 的hash值；

key: 插入值的键；

value: 值；

next：下一个对象。

通过这个代码结构，就可以看出HashMap是采用链表数据结构，也被称为拉链法。

它最明显的特征就是：存储单元上非连续、非顺序的存储结构，而是在每一个节点里存到下一个节点的指针域。

put操作添加在链表头部还是尾部

JDK 1.7 采用头插法来添加链表元素，存在链表成环的问题，1.8 中做了优化，采用尾插法来添加链表元素。