java hashmap面试题_说一下 HashMap 的实现原理

HashMap深度分析

HashMap 是 Map 的一个实现类，它代表的是一种键值对的数据存储形式。

大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。

HashMap最多只允许一条记录的键为null，允许多条记录的值为null。不保证有序(比如插入的顺序)、也不保证序不随时间变化。

jdk 8 之前，其内部是由数组+链表来实现的，而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。

HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

下面我们先来看一下HashMap内部所用到的存储结构

HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

HashMap基本原理

1、首先判断Key是否为Null，如果为null，直接查找Enrty[0]，如果不是Null，先计算Key的HashCode，然后经过二次Hash。得到Hash值，这里的Hash特征值是一个int值。

2、根据Hash值，要找到对应的数组啊，所以对Entry[]的长度length求余，得到的就是Entry数组的index。

3、找到对应的数组，就是找到了所在的链表，然后按照链表的操作对Value进行插入、删除和查询操作。

4、HashMap概念介绍

变量术语说明

size大小HashMap的存储大小

threshold临界值HashMap大小达到临界值，需要重新分配大小。

loadFactor负载因子HashMap大小负载因子，默认为75%。

modCount统一修改HashMap被修改或者删除的次数总数。

Entry实体HashMap存储对象的实际实体，由Key，value，hash，next组成。

5、HashMap初始化

默认情况下，大多数人都调用new HashMap()来初始化的，我在这里分析new HashMap(int initialCapacity, float loadFactor)的构造函数，代码如下：

publicHashMap(intinitialCapacity,floatloadFactor){// initialCapacity代表初始化HashMap的容量，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。if(initialCapacity <0)thrownewIllegalArgumentException("Illegal initial capacity: "+ initialCapacity);if(initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;// loadFactor代表它的负载因子，默认是是DEFAULT_LOAD_FACTOR=0.75，用来计算threshold临界值的。if(loadFactor <=0|| Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal load factor: "+ loadFactor);// Find a power of 2 >= initialCapacityintcapacity =1;while(capacity < initialCapacity) capacity <<=1;this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table =newEntry[capacity]; init(); }

由上面的代码可以看出，初始化的时候需要知道初始化的容量大小，因为在后面要通过按位与的Hash算法计算Entry数组的索引，那么要求Entry的数组长度是2的N次方。

6、HashMap中的Hash计算和碰撞问题

HashMap的hash计算时先计算hashCode(),然后进行二次hash。代码如下：

// 计算二次Hash inthash = hash(key.hashCode());// 通过Hash找数组索引inti = indexFor(hash, table.length);

先不忙着学习HashMap的Hash算法，先来看看JDK的String的Hash算法。代码如下：

/**

* Returns a hash code for this string. The hash code for a

* <code>String</code> object is computed as

* <blockquote><pre>

* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

* </pre></blockquote>

* using <code>int</code> arithmetic, where <code>s[i]</code> is the

* <i>i</i>th character of the string, <code>n</code> is the length of

* the string, and <code>^</code> indicates exponentiation.

* (The hash value of the empty string is zero.)

*

* @return a hash code value for this object.

*/publicinthashCode(){inth = hash;if(h ==0&& value.length >0) {charval[] = value;for(inti =0; i < value.length; i++) { h =31* h + val[i]; } hash = h; }returnh; }

从JDK的API可以看出，它的算法等式就是s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]，其中s[i]就是索引为i的字符，n为字符串的长度。这里为什么有一个固定常量31呢，关于这个31的讨论很多，基本就是优化的数字，主要参考Joshua Bloch'sEffective Java的引用如下：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

大体意思是说选择31是因为它是一个奇素数，如果它做乘法溢出的时候，信息会丢失，而且当和2做乘法的时候相当于移位，在使用它的时候优点还是不清楚，但是它已经成为了传统的选择，31的一个很好的特性就是做乘法的时候可以被移位和减法代替的时候有更好的性能体现。例如31i相当于是i左移5位减去i，即31i == (i<<5)-i。现代的虚拟内存系统都使用这种自动优化。

现在进入正题，HashMap为什么还要做二次hash呢? 代码如下：

staticinthash(inth){// 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);returnh ^ (h >>>7) ^ (h >>>4); }

回答这个问题之前，我们先来看看HashMap是怎么通过Hash查找数组的索引的。

/**

* Returns index for hash code h.

*/staticintindexFor(inth,intlength){returnh & (length-1); }

其中h是hash值，length是数组的长度，这个按位与的算法其实就是h%length求余，一般什么情况下利用该算法，典型的分组。例如怎么将100个数分组16组中，就是这个意思。应用非常广泛。

既然知道了分组的原理了，那我们看看几个例子，代码如下：

inth=15,length=16; System.out.println(h & (length-1)); h=15+16; System.out.println(h & (length-1)); h=15+16+16; System.out.println(h & (length-1)); h=15+16+16+16; System.out.println(h & (length-1));

运行结果都是15，为什么呢?我们换算成二进制来看看。

System.out.println(Integer.parseInt("0001111", 2) &Integer.parseInt("0001111", 2));System.out.println(Integer.parseInt("0011111", 2) &Integer.parseInt("0001111", 2));System.out.println(Integer.parseInt("0111111", 2) &Integer.parseInt("0001111", 2));System.out.println(Integer.parseInt("1111111", 2) &Integer.parseInt("0001111", 2));

这里你就发现了，在做按位与操作的时候，后面的始终是低位在做计算，高位不参与计算，因为高位都是0。这样导致的结果就是只要是低位是一样的，高位无论是什么，最后结果是一样的，如果这样依赖，hash碰撞始终在一个数组上，导致这个数组开始的链表无限长，那么在查询的时候就速度很慢，又怎么算得上高性能的啊。所以hashmap必须解决这样的问题，尽量让key尽可能均匀的分配到数组上去。避免造成Hash堆积。

回到正题，HashMap怎么处理这个问题，怎么做的二次Hash。

staticinthash(inth){// 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);returnh ^ (h >>>7) ^ (h >>>4); }

这里就是解决Hash的的冲突的函数，解决Hash的冲突有以下几种方法：

1. 开放定址法

线性探测再散列，二次探测再散列，伪随机探测再散列）

2. 再哈希法

3. 链地址法

4. 建立一 公共溢出区

总结

在JDK8中HashMap的底层是：数组+链表(散列表)+红黑树

在散列表中有装载因子这么一个属性，当装载因子*初始容量小于散列表元素时，该散列表会再散列，扩容2倍！

装载因子的默认值是0.75，无论是初始大了还是初始小了对我们HashMap的性能都不好

装载因子初始值大了，可以减少散列表再散列(扩容的次数)，但同时会导致散列冲突的可能性变大(散列冲突也是耗性能的一个操作，要得操作链表(红黑树)！

装载因子初始值小了，可以减小散列冲突的可能性，但同时扩容的次数可能就会变多！

初始容量的默认值是16，它也一样，无论初始大了还是小了，对我们的HashMap都是有影响的：

初始容量过大，那么遍历时我们的速度就会受影响~

初始容量过小，散列表再散列(扩容的次数)可能就变得多，扩容也是一件非常耗费性能的一件事~

从源码上我们可以发现：HashMap并不是直接拿key的哈希值来用的，它会将key的哈希值的高16位进行异或操作，使得我们将元素放入哈希表的时候增加了一定的随机性。

还要值得注意的是：并不是桶子上有8位元素的时候它就能变成红黑树，它得同时满足我们的散列表容量大于64才行的~