转载

HashMap源码解析

对于HashMap,如果是java程序员，那么定然不会陌生，对于HashMap，应该说是最常用的一种Map结构了，同样在面试当中也会屡屡被提问到，常见的几种题目：

HashMap的默认容量？
HashMap是如何扩容的？
HashMap的数组大小为什么一定是2的幂？
HashMap为什么是线程不安全的？
Java7到Java8做了哪些改进？为什么？

因为重要，所以我也就学习源码，并且将学习心得记录下来，与大家一起学习。

首先再看HashMap之前，我们来简单回顾一下哈希表

哈希表是由一些基于哈希值的桶和链表所构成的。哈希桶就是可以快速检索的数据结构，举个例子如果要寻找电话本的人的联系方式，我们可以利用拼音的首字母快速定位到这个联系人，存放这些字母的就叫哈希桶。本质上，哈希桶就是将一个元素映射成一个可以快速检索的哈希值。

哈希桶加上数组就构成了哈希表，数组的好处是随机寻址的速度与长度无关，时间复杂度是O(1)，但是哈希表最大的缺点是会发生碰撞，如果多个元素的哈希值是相同的，那么我们就说哈希值发生了碰撞，为了解决这个问题，我们将数组换成了链表，找到哈希值时，通过哈希桶里可以精确的找到所要查找的元素。平均差找时间都是O（1）。在java世界中，我们用来表达哈希表的数据结构就是HashMap。

HashMap源码解析

哈希桶的实现是由hashcode实现的int hashcode 底下有对象：object1,object2....

我们先来看java7的HashMap。

经典的数据结构：数组加链表。

通过查看源码我们可以知晓HashMap的默认容量为你16，如果改变负载因子并且将初始值设为17 结果会怎么样么？再次点开源码，我们会发现他会向上取整为2的幂也就是变成了32.之后我们可以看到负载因子是0.75.

这里有一个问题，就是桶的初始化容量是16个，而我们的HashCode值是-2^31~2^31-1，42亿个数。那么我们怎么从任意一个int变成0~n-1。聪明的你肯定想到了取余这个想法，但是在这个方法有两个缺点：

负数取模还是负数，所以我们需要把负数变为正数
速率较慢

那么我们点开源码发现，为了寻找要插入的元素的索引值，做了一个鬼畜的操作：hash&（length-1）,做这样一个位运算，那么这操作正好可以解释为什么我们需要输进去的HashMap的初始容量是2的幂，我们可以看出hash&（2^n-1），最后的下标就是Hashmap对应的2^n-1的个数下标，之所以把容量定为2的幂，就是因为让2^n-1位运算时拿到的值全部是1，这样做与运算就可以快速找到下标并且分布还是均匀的（妙啊）。

解释完这个问题，我们来看看是怎么扩容的，根据源码，我么可以看到，当所需要的容量超过 原始容量*负载因子（0.75） 时，就需要进行扩容，扩容的大小是之前的两倍。而在扩容的过程中就包含了一个rehash的操作。那么在扩容的时候，会进行transfer也就是将之前的数据进行迁移的操作，遍历所有的元素，并且重新计算哈希值，找到在新表里的索引，把它放进去。这是一个巨坑！！！为了避免高位不同，低位相同，进行了高位与低位的异或操作。

在Java7中的HashMap会有很多问题：

会碰到死锁
CVE-2011-1858 TOMCAT邮件组的讨论

对于死锁问题，其实多数是程序员自己的问题，因为HashMap本身就不是线程安全的，当在多个线程中使用hashmap的时候，就必须给他加入同步的环境.

对于TOMCAT邮件组的讨论，是说一个安全问题，如果我们的多个元素映射成同一个哈希值时，会把哈希表退化成一个链表，而链表的查询的时间复杂度的o（n），那么这个查询速度是很可怕的，如果是被黑客利用精心构造的成千上万个元素，具有同样的哈希值，就可以引起Dos攻击，针对这个问题，sun公司提供了一个小补丁，就是如果检查到元素是String的话那么就该用另外一种不同于默认的hash算法来去避免潜在的危险。