HashMap源码分析

拼搏现实的明天。 2021-10-18 13:12 586阅读 0赞

HashMap概述（非线程安全）

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

线程安全的HashMap：

方法一：通过Collections.synchronizedMap()返回一个新的Map，这个新的map就是线程安全的。 这个要求大家习惯基于接口编程，因为返回的并不是HashMap，而是一个Map的实现。

方法二：重新改写了HashMap，具体的可以查看java.util.concurrent.ConcurrentHashMap. 这个方法比方法一有了很大的改进。

**JDK1.8中HashMap的数据结构**

在[Java][]编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的[数据结构][Link 1]都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结构，但是在jdk1.8里 加入了红黑树的实现，当链表的长度大于8时，转换为红黑树的结构（之前是由负载因子实现存储的,通过红黑树结构存储这点性能是非常好的）。

![aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlL0Q2QTNFQTU5NDgwQzQ3OTU5Rjc4RDFFNDc0NUVDQjQ2LzEzNzUy][]

JDK1.8中HashMap采用了链地址法，链地址法，就是数组加链表的结合。在数组元素上都有一个链表结构，当数据被Hash后，得到准确的数组下标，把数据放在对应下标元素的链表上，当链表的长度大于8时，转换成红黑树结构存储，这点是JDK1.8对HashMap进行处理，在性能上是非常优异的。

**另外说一下JDK1.7中HashMap的数据结构（本章以HashMap1.8来说）**

HashMap中的数据结构是数组+单链表的组合，以键值对(key-value)的形式存储元素的，通过put()和get()方法储存和获取对象。

![aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvMTI2NzkzOS8yMDE3MTIvMTI2NzkzOS0yMDE3MTIwODE5MjQxMzUxNS0xMDI3OTA3MjU5LnBuZw][]

（方块表示Entry对象，横排表示数组table\[\]，纵排表示哈希桶bucket【实际上是一个由Entry组成的链表，新加入的Entry放在链头，最先加入的放在链尾】，）

**HashMap的源码解析**

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。

![aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzc0Qjc3NzEwRTM0MTRBMDI5QjRDM0Q1RTQ0ODRFRTBELzEzNzYw][]

有时两个key会定位到相同的位置，表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

![aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzQ0RTg3Nzc1NzdENDQ2QjdCQ0RENTRBNzc0NDkzNzFCLzEzNzU5][]

HashMap类中有一个非常重要的字段，就是 Node\[\] table，即哈希桶数组，明显它是一个Node的数组。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node\[\] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

![aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzUzQzk0MkM5RTNBMTRDQTQ4Q0U3NjMwOTRBNjIxNzU2LzEzNzU0][]

HashMap的构造函数对下面几个字段进行了初始化

![aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzY2REFFRjkxRDI4NjQ4QzE4RjE1N0FCMUQ2NTc1MTIwLzEzNzYx][]

Node\[\] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最[大数据][Link 2]量的Node(键值对)个数。threshold = length \* Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

**追究HashMap的性能问题：**

HashMap有两个参数影响其性能：初始容量和负载因子。均可以通过构造方法指定大小。

容量capacity是HashMap中bucket哈希桶(Entry的链表)的数量，初始容量只是HashMap在创建时的容量，最大设置初始容量是2^30，默认初始容量是16（必须为2的幂），解释一下，当数组长度为2的n次幂的时候，不同的key通过indexFor()方法算得的数组位置相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，get()的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

负载因子loadFactor是HashMap在其容量自动增加之前可以达到多满的一种尺度，**默认值是0.75。**

Java中HashMap的初始容量设置问题  
          阿里规约建议集合初始化时，指定初始化大小。像HashMap，**默认大小是16**，也就是支持存储最多20个键值对。

**如果不超过20个键值对，可以不设置，如果超出，按如下公式计算后设置：initialCapacity = (需要存储的元素（键值对）个数 / 负载因子) + 1。**

**例如某个需求要存20个key-value得出公式如下：**

**       initialCapacity = (20/0.75)+1;**

[Java]: http://lib.csdn.net/base/javase
[Link 1]: http://lib.csdn.net/base/datastructure
[aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlL0Q2QTNFQTU5NDgwQzQ3OTU5Rjc4RDFFNDc0NUVDQjQ2LzEzNzUy]: /images/20211018/56c8deb422f04cc2967bdb3434c1f061.png
[aHR0cHM6Ly9pbWFnZXMyMDE3LmNuYmxvZ3MuY29tL2Jsb2cvMTI2NzkzOS8yMDE3MTIvMTI2NzkzOS0yMDE3MTIwODE5MjQxMzUxNS0xMDI3OTA3MjU5LnBuZw]: /images/20211018/c00d9f425fa4481184208fdedfd3448c.png
[aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzc0Qjc3NzEwRTM0MTRBMDI5QjRDM0Q1RTQ0ODRFRTBELzEzNzYw]: /images/20211018/c0bc9c11c0c24d889246a5548669a9ea.png
[aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzQ0RTg3Nzc1NzdENDQ2QjdCQ0RENTRBNzc0NDkzNzFCLzEzNzU5]: /images/20211018/f6a607788ce2484b8df5681fdce0a257.png
[aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzUzQzk0MkM5RTNBMTRDQTQ4Q0U3NjMwOTRBNjIxNzU2LzEzNzU0]: /images/20211018/97164d270838431e993c872077288829.png
[aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS81YTMwNzE2NjExNGUyM2UzMDZjZGQ4ODRkYjAyYjhlOS94bWxub3RlLzY2REFFRjkxRDI4NjQ4QzE4RjE1N0FCMUQ2NTc1MTIwLzEzNzYx]: /images/20211018/a7fe49e34af0455fa54a17417dc3a1ed.png
[Link 2]: http://lib.csdn.net/base/hadoop