HashMap源码解析

一、HashMap概述

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射 的顺序，特别是它不保证该顺序恒久不变。 值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类 的静态方法synchronizedMap获得线程安全的HashMap。 Map map = Collections.synchronizedMap(new HashMap());

二、HashMap的数据结构

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是 通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要 hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的 hash值是相同的。

这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有 很多，HashMap底层是通过链表来解决hash冲突的。 图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用 来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。 我们看看HashMap中Entry类的代码： 

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是 用来处理hash冲突的，形成一个链表。

三、HashMap源码分析

1、关键属性先看看HashMap类中的一些关键属性：

transient Entry[] table;//

存储元素的实体数组 transient int size;//

存放元素的个数 int threshold; //临界值 当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量 fifinal flfloat loadFactor; //加载因子 transient int modCount;//被修改的次数

其中loadFactor加载因子是表示Hsah表中元素的填满的程度. 若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查 找效率降低。 反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏 （很多空间还没用，就开始扩容了） 冲突的机会越大,则查找的成本越高. 因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构 中有名的"时-空"矛盾的平衡与折衷. 如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧 张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让 它取默认值0.75就好了。

2、构造方法 

下面看看HashMap的几个构造方法：

public HashMap(int initialCapacity, float loadFactor) { //确保数字合法 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; //初始容量 while (capacity < initialCapacity) //确保容量为2的n次幂，使capacity为大于 initialCapacity的最小的2的n次幂 capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity \* loadFactor); table = new Entry[capacity]; init(); }public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY \* DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY];init(); } 

我们可以看到在构造HashMap的时候如果我们指定了加载因子和初始容量的话就调用第一个构造方 法，否则的话就是用默认的。默认初始容量为16，默认加载因子为0.75。我们可以看到上面代码中13- 15行，这段代码的作用是确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂， 至于为什么要把容量设置为2的n次幂，我们等下再看。 重点分析下HashMap中用的最多的两个方法put和get 

3、存储数据 下面看看HashMap存储数据的过程是怎样的，首先看看HashMap的put方法： 上面程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从 上面程序中可以看出：当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可 以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那 里即可。 我们慢慢的来分析这个函数，第2和3行的作用就是处理key值为null的情况，我们看看 putForNullKey(value)方法：注意：如果key为null的话，hash值为0，对象存储在数组中索引为0的位置。即table[0] 我们再回去看看put方法中第4行，它是通过key的hashCode值计算hash码，下面是计算hash码的函 数： 得到hash码之后就会通过hash码去计算出应该存储在数组中的索引。

HashMap经典面试题 

1.谈一下HashMap的特性？

1.HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。 2.非同步，线程不安全。 3.底层是hash表，不保证有序(比如插入的顺序)

2.谈一下HashMap的底层原理是什么？

基于hashing的原理，jdk8后采用数组+链表+红黑树的数据结构。我们通过put和get存储和获取对象。 当我们给put()方法传递键和值时，先对键做一个hashCode()的计算来得到它在bucket数组中的位置来 存储Entry对象。当获取对象时，通过get获取到bucket的位置，再通过键对象的equals()方法找到正确 的键值对，然后在返回值对象。 

3.谈一下hashMap中put是如何实现的？ 

1.计算关于key的hashcode值（与Key.hashCode的高16位做异或运算） 2.如果散列表为空时，调用resize()初始化散列表 3.如果没有发生碰撞，直接添加元素到散列表中去 4.如果发生了碰撞(hashCode值相同)，进行三种判断 4.1:若key地址相同或者equals后内容相同，则替换旧值 4.2:如果是红黑树结构，就调用树的插入方法 //计算hash值的方法 通过键的hashCode来计算 static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

4.3：链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到 达变成红黑树的阙值8；也可以遍历到有节