首页 > 代码库 > HashMap源码分析
HashMap源码分析
本篇博文的目录：
一：HashMap简介
二：HashMap的结构
三：HashMap的源码分析
3.1： 成员变量
3.2: 构造函数
3.3：内部类
3.4：put方法
3.5：get方法
3.4: 其余方法
四：HashMap的最重要的几个问题
五：总结
前言：HashMap作为在Java中的高频率使用的一个数据存储容器，其属于key、value非常流行的方式，我们几乎每天都要使用Hashmap用来存放数据，比如FreeMarker、mybatis中，都是通过HashMap包装数据，然后把数据传给框架去解析后找到具体的数据，可以说使用率相当广泛。同时，它也是我们面试中的基本属于必考的问题，记得小Y我在刚不久前的面试中，大约面试了7、8家，可谓关于HashMap的是属于非常容易出现的问题，所以说学好HashMap不仅对我们深入理解Java数据结构有益。更对我们求职找工作也是不可获取的一部分，本期博客，我们就来聚焦HashMap，挖一下HashMap的底层原理，看它究竟是如何工作的。说明：本次源码分析基于jdk1.6，如果你看到的版本和我的不一致，很可能是jdk版本不一样
一：HashMap简介
HashMap是属于键值形式的，这点上不同于list和数组的形式，像list这种结构的数据。它只能记录单一数据，无法对数据进行说明。而数组，它适合用来记录一序列类型相同数据，有很大的局限性。而HashMap这种方式非常合理并且在计算机系统中是高频出现的，举个栗子，比如我们要记录一个文件的属性，比如文件的大小、文件格式、文件类型等等，那么就可以采用HashMap来存储，map.put("FileSize","1024MB"),map.put("isRead",true)等等，可谓是一把记录数据的利器。同时，它继承于AbstractMap、实现了Map接口和cloneable、Serializable接口，这就说明了它具备一定的克隆能力和可序列化能力（详情参考以下代码：public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable），可序列化的话，那么它就可以写入磁盘里，这样实现了数据的持久化。
二：HashMap的结构
HashMap属于一个类，维护有成员变量，它是采用数组+链表的形式来容纳数据的，因此在它的类中维护着一个静态内部类，名字叫做Entry,这就是其维护的数组，那么它的链表是什么呢？链表指的是在数组的节点上，有一个next指针，指针指向下一个Entry，这就在其节点上形成了一个链表，这么说可能有点抽象，我们来画一张图来直观的感受一下：如果在其节点上，衍生出来的具有指针的就是其链表结构
三：HashMap的源码分析
3.1：成员变量
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { static final int DEFAULT_INITIAL_CAPACITY = 16; //默认的初始容量（必须是2的次方） static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量值。 2的30次方 static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的加载因子（如果你构造方法中没有传入的话，会用这个） transient Entry[] table;//维护的数组（长度必须为2的次方） transient int size;//大小（用transient表示该字段无法被序列化） int threshold;//因为它表示的是resize也就是扩容的指标，我们暂且把它称为扩容临界值 final float loadFactor;//加载因子 transient volatile int modCount;//修改表的次数，比如你put一次这个值就会+1
从维护的成员变量中，我们可以发现它有自己的容量大小、还有数组、大小、加载因子等。这些东西具体是干嘛的我们会接着往下讲，大家先知道有这么一个概念，我们继续往下看。
3.2：HashMap的构造函数
public HashMap(int initialCapacity, float loadFactor) {//HashMap的构造函数 初始容量 加载因子 if (initialCapacity < 0) //初始容量如果小于0 throw new IllegalArgumentException("Illegal initial capacity: " +//抛出异常 initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)//默认初始容量大于最大容量 initialCapacity = MAXIMUM_CAPACITY;// if (loadFactor <= 0 || Float.isNaN(loadFactor))//加载因子小于0 或者不是一个数字 throw new IllegalArgumentException("Illegal load factor: " +//抛出异常 loadFactor); int capacity = 1;//容量=1 while (capacity < initialCapacity)//小于初始容量 capacity <<= 1;//左移1位，相当于乘以2 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();//初始化 } public HashMap(Map<? extends K, ? extends V> m) { // 构造一个映射关系与指定Map相同的新 HashMap this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); } void init() {//初始化 }
从上面可以看出HashMap具有四个构造函数，我们依次看一下：
第一个构造函数：使用自定义的初始容量、和加载因子，首先对初始容量进行校验不能小于0（否则会抛异常），然后其不能大于最大容量值（否则还是用最大容量值），再校验加载因子不能小于0,还必须是数字。再初始化加载因子和上面的成员变量数组、扩容临界值为容量*加载因子。但是一般这个构造函数我们用的不是很多，一般都会选择使用无参的构造函数。
第一个构造函数：只有一个初始容量的参数，会默认调用第一个构造函数，把加载因子设为默认的加载因子。
第三个构造函数：也就是无参构造函数，默认会初始化加载因子（0.75）,初始化扩容临界值，初始化数组
第四个构造函数：这个构造函数用的很少，主要是构造一个映射关系与指定Map相同的新 HashMap
3.3：内部数组类
static class Entry<K,V> implements Map.Entry<K,V> {//内部类 -数组
final K key; //键值
V value;//值
Entry<K,V> next;//下一个值
final int hash;//hash值
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {// 构造函数
value = http://www.mamicode.com/v;//值>
可以看到HashMap内部维护的数组是有key、value属性，同时其拥有一个指针，指向下一个Entry，默认的构造函数构造的时候会把所有的成员变量构造进去。这是就是为什么说HashMap是数组+链表的结构的原因。
3.4：put方法
在看put方法之前，我们先来看一下两个很重要的方法：
static int hash(int h) {//通过传入的hashcode来计算hash值
h ^= (h >>> 20) ^ (h >>> 12);//异或运算，右移12位和右移20位计算hash值
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {//通过hashcode找在哈希表中的位置，返回具体的位置
return h & (length-1);//采用的是异或运算等价于 hash%(table.length) length是2的次方数
}//正好获取了数组的位置
这两个方法，hash()方法主要是进行计算传入的hashcode的哈希值，而indexFor主要是用过hash值和数组的长度来返回一个int型的数字，这个方法主要是寻找在一个数组中插入的位置。
好了，接下来我们看具体的put()方法：
public V put(K key, V value) { //放入的方法（键和值）
if (key == null)//如果键为null的情况
return putForNullKey(value);//返回处理键为null的方法
int hash = hash(key.hashCode());//通过键的hashcode生成一个唯一hash值
int i = indexFor(hash, table.length);//根据哈希值在数组中找位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//从位置处开始遍历循环链表，如果e不为null。证明该位置已经有元素了
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//比较hash值和键相等，如果key相同
V oldValue = http://www.mamicode.com/e.value;//把数组中的值存储起来>
看put方法，传入的是key和value两个值，首先呢，判断键如果为null的情况下，会有一个处理null的方法，这也就直接说明了HashMap是允许键为null的。如果不为null，通过键的hashcode传入Hash方法，计算hash值，再把其hash值传入indexFor方法，找其在数组中的位置，也就是要把值放入的位置，然后开始在数组中遍历，假设我们是第一个存入的值，那么它此时Entry为null，就不会走for循环，我们继续放下走，给修改次数+1，调用addEntry方法：
void addEntry(int hash, K key, V value, int bucketIndex) { //添加entry对象
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//新建一个entry
if (size++ >= threshold)//如果size>扩容临界值
resize(2 * table.length); //数组的原有长度扩大两倍
}
这个方法主要是用来给指定的数组位置添加entry对象的，我们看一下它会new一个Entry对象，然后在计算出来的位置进行构造生成对象，放入我们传入的key和value的值。同时，这里进行了对数组长度的判断，如果大于扩容临界值，就会对其进行resize,也及时扩容操作，扩容是数组长度的2倍。
以上讲解的是初次进入数组的情况，那么假如我们计算出来的位置上，已经有元素存在，怎么办？
我们来继续看代码，在我们计算出位置以后，此时位置上有元素，这就说明了e！=null，那么就会进入for循环，然后进行对数组上的链表进行遍历（注意此时是链表），如果找到key相同的entry元素，那么就会对其value值进行覆盖，如果没有找到，也就是说链表上此时没有相同的key，那么就会走addentry方法，在计算出来的位置上，在链表的首部创建一个新的Entry对象，此时就把键和值放入进去了。
3.5:get方法
public V get(Object key) {//get方法，通过键获取值
if (key == null) //如果键为null的情况下
return getForNullKey();//处理键为null的情况
int hash = hash(key.hashCode());//通过键的hashcode计算哈希
for (Entry<K,V> e = table[indexFor(hash, table.length)];//找到数组中存放的位置
e != null;
e = e.next) {//遍历循环
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))//比较数组中的数的哈希键和传入的键的哈希值，只有其hash值相同、并且键相同（通过==和equals确保）
return e.value;//返回数组中的数对应的值
}
return null;//如果找不到就返回null
}
我们来看get方法，get方法首先会传入一个键值，判断其是否非空，然后计算hash值，然后再回链表进行遍历，如果找到和传入的key相同的元素，直接取其value值返回，如果找不到就返回null。get方法比较简单，就是一个遍历寻找值的过程，这里也很好理解，需要注意的就是其还有进行比对Hash值
3.6：其他方法
我们先来看一下其扩容方法：
void resize(int newCapacity) { //扩容方法
Entry[] oldTable = table;//旧的数组表
int oldCapacity = oldTable.length; //取旧数组的长度
if (oldCapacity == MAXIMUM_CAPACITY) {//最大的容量
threshold = Integer.MAX_VALUE;//扩容临界值=最大int值
return;
}
Entry[] newTable = new Entry[newCapacity];//创建新的数组
transfer(newTable);//转移数据
table = newTable;//新数组
threshold = (int)(newCapacity * loadFactor);//
}
void transfer(Entry[] newTable) { //转移到新的数组中
Entry[] src = http://www.mamicode.com/table;>
扩容方法，首先还是虚拟一个旧数组。然后新建一个新的数组，主要是为了存放数据，再通过transfer方法，进行遍历循环，把数组挨个复制到新的数组里面，一定要注意的此时的新数组的长度是旧数组的2倍。
再来看看我们常用的几个方法：
public int size() {//计算HashMap大小的方法
return size;//返回size的值
}
public boolean isEmpty() {//判断map是不是空
return size == 0;//用0和size的值做比较，是0返回true，否则返回false
}
size()方法，直接返回size成员变量的大小，isEmpty（）判断map是不是空的，直接比较0和size的大小，很简单。这里一看代码才恍然大悟，原来是这么做的，所以我们要养成经常多看源码的习惯。
四：HashMap几个重要的问题（面试中经常遇到的）
1: HashMap是如何put的？
答：是通过key的hashcode方法再计算hash值，然后再计算存放在数组中的位置，构建一个Entry对象，把key、value值包装进去，存入在数组中。
2：如果在放入值的时候，已经有键存在了，怎么办？
答：它会比较key的hash值和内存地址、内容，如果相同，就会用新值替换原来的旧值
3：HashMap如果在存放值的时候产生了Hash冲突怎么办？
答：Hash冲突指的是，计算出来的位置在同一处，那么它就会遍历该处的链表，如果有相同的key，它就会覆盖原来的旧值，如果没有它会在链表中创建一个entry对象，把具体的key、value封装进去，添加到链表的首部
4：HashMap允许键为空吗？存放的键为空怎么办？
答：允许，如果键为空，它会在数组的第一个位置上创建entry元素，以null作为key，值作为键放入到数组中
5；我们都知道数组是有长度限制的，如果数组的长度超过限制怎么办？
数组的长度超过了限制，HashMap会调用resize()方法，对其进行扩容，扩容的临界值是数组容量*加载因子，如果按照默认的，那么默认容量是16，加载因子是0.75，也就是要16*0.75=12,数组中的容量超过12就会进行扩容，扩容的长度是原来的2倍，也就是16*2=32
7：在看了HashMap源码后，你应该注意什么？
注意第一点：减少哈希冲突，因为一旦放入链表中，以后总是要遍历链表，效率差。要尽量把元素直接放入数组中，而非链表，根据实际情况，重写hashCode和equals方法。
注意第二点：HashMap底层是数组，尽量减少扩容，所以HashMap放入元素的时候，应该估算数组的大小，避免扩容操作
注意第三点：尽量不要修改默认的加载因子0.75，这个数字是经过科学计算来的
8：HashMap是线程安全的吗？如果要它变成线程安全的，应该怎么做？
答：HashMap是非线程安全的，也并不是同步的。如果要线程安全，可以使用concurrenthashmap这个类，也可以用Collections.syzchronizedMap(HashMap map),进行构造会返回一个新的HashMap此时的hashMap就是线程安全的。
五：总结
本篇博文对HashMap进行了一个讲解，主要是放在了其put方法和get方法上的讲解上，同时回答了一些常见的hashMap的问题，希望大家有一定的收获。学习hashMap对我们的java学习来说非常重要，如有问题，大家可以留言，我们一起探讨，本篇博文就介绍到这里，如有错误，还望指出，谢谢。
HashMap源码分析