转载

HashMap源码分析

HashMap概述（非线程安全）

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

线程安全的HashMap：

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

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

JDK1.8中HashMap的数据结构

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

HashMap源码分析

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

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

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

HashMap源码分析

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

HashMap的源码解析

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

HashMap源码分析

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

HashMap源码分析

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

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

HashMap源码分析

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

HashMap源码分析

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的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个键值对。