HashMap是我们最常见也是最长使用的数据结构之一，它的功能强大、用处广泛。而且也是面试常见的考查知识点。常见问题可能有HashMap存储结构是什么样的？HashMap如何放入键值对、如何获取键值对应的值以及如何删除一个键值对。今天我们就来看看HashMap底层的实现原理。下面我们就开始进入正题，分析一下hashmap源码的实现原理。

HashMap的构造方法有好几个，在这里我们就不一一介绍，只说一下我们最常见的HashMap无参构造方法。上面的构造方法中，有几个变量需要我们这里说明一下：

另外在HahsMap中，我们通过数组加链表的方式来存储Entry节点（Entry数据结构用于存储键值对）。这里所谓的数组即是上面提到的table，它是一个Entry数组，table对象中节点初始化值均为null，当我们新插入的节点第一次散列到该位置时，会将节点插入到table中对应位置。如果后续存在散列位置相同的节点，会以链表的方式解决hash冲突。示意图如下：

put方法是我们最常用方法，我们利用该方法将键值对放入HashMap集合中，那么HashMap到底是什么样的结构，put()方法又做了什么呢？我们下面就来看看put()方法的具体实现。

如果当前传入的key值为null，执行putForNullKey()方法;当key值为null时，hash值为0，将其保存到以table[0]为开头的链表中去。遍历链表，如果存在某节点的key值为null，则用新value直接将其替换。如果未找到key值为null的节点，调用addEntry()方法插入一个key为null的新节点。addEntry方法我们会在后文中介绍。

为什么这里还要对key的hashCode值再调用一次哈希算法呢？简单来说就是为了让传递进来的key散落位置可以更加均匀，具体原因就不在本文中介绍了，网上有很多资料可供借鉴。
接着调用indexFor方法计算当前key值散落在table中的位置，其实就是key%table.length

遍历以table[i]为头结点的链表，查找是否已经有相同的key值的节点存在于链表中。判断条件为if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。这个判断条件十分重要，我们来仔细分析下。首先是e.hash == hash：之前我们已经计算出了当前待处理节点的hash值，并保存在变量hash中，在此我们需要比较当前链表遍历节点key的hash值(e.hash)和hash是否相等。如果我们去看一下addEntry()方法我们会发现，Entry节点的存储位置实际上是由key的hash值来决定的。如果key的hash相同，那么他们的存储位置也相同。(k = e.key) == key || key.equals(k))。先简单的说一下”==”和”equals”的意义，”==”是引用一致性判断，而equals是内容一致性判断。这里的意思也就是说如果两个key对象指向的是同一个对象，或者他们就是同一个对象，则返回true。总结一下，如果hash值相同，则key值相同或是同一个对象的引用，则表示hashmap中存在以key为键值的Entry节点。
如果判断if (e.hash == hash && ((k = e.key) == key || key.equals(k)))判断条件返回为true，则用新值替换老值。

如果没有找到相同的key值，则调用addEntry()方法新增一个指定key和value的Entry节点。

接下来继续看addEntry()方法，假设当前节点为插入到table[bucketIndex]位置的第一个节点

在Entry类的构造方法中有这样一句代码:

即当前新建的entry节点将指向Entry构造方法传递过来的Entry节点e，此时e保存的值为头结点的值，也就是null。该节点创建完之后，又被赋值给table[bucketIndex]，相当于链表的头结点了保存了最新插入的节点。如下图所示我们在table[i]位置插入了Entry

另外在addEntry方法中有如下两句代码

size的值为当前hashMap中存储的节点个数，threshold是一个阈值。如果hashMap中存储的节点个数大于等于threshold，表示我们需要对当前hashMap进行扩容了。每一次扩充容量为之前容量的2倍。我们来看一下resize()方法。

关键代码是这一段

如果resize()之前Entry数组的大小为A,那么newTable数组的大小为2A
transfer(newTable)方法用于将原先entry[]数组中的节点转移到newTable数组中，下面我们来看下transfer()方法具体干了什么。

a. 取src[j]节点的值赋值给e

b. 如果e节点不为null，将src[j]的值置为null

我们来举两个简单的例子说明一下tranfer到底干了什么：
当src[j]不为空时，比方说src[j]中保存的Entry节点key=”key2”,value=”value2”，src[j]指向的下一个节点key=”key1”,value=”value1”，如下图所示：

说完了put我们再来看一下get方法

理解了put方法时如何往hashmap中放入键值对的，那么get()方法也就很好理解了。我们来具体看看get()方法的实现。

别看remove方法这么长，其实它的逻辑很简单

如果让你写一个hashmap的遍历代码，估计大部分人写出下面这段代码。可是HashMap的遍历过程到底是怎么样的，为什么我们每次取值的时候都使用iter.next()来取值的呢？下面我们就来看看HashMap的遍历实现。

HashMap类中有一个私有类EntrySet，它继承自AbstractSet类。EntrySet类中有一个iterator()方法，也就是我们上面在遍历hashMap所调用的iterator()方法，它会返回一个Iterator对象。
我们来看看iterator方法：

iterator()方法中调用了newEntryIterator()方法，接着进入newEntryIterator()方法看看。

newEntryIterator方法又创建了一个EntryIterator对象并返回。这个EntryIterator很关键，我们来具体看看这个类。

EntryIterator类继承自HashItertor类，而且HashIterator类只有一个方法next()。既然EntryIterator继承自HashIterator类，那么EntryIterator到底继承了父类的哪些对象，默认实现了父类的哪些方法呢？我们再看看HashIterator类。

HashIterator类中有四个属性，它们的用处代码注释已经简单明了的介绍了。值得注意的是HashIterator()提供了一个无参的构造方法，然而他并没有对所有的属性进行初始化，在这里我们需要明确的是index的值将会被赋为0。同时后面还有一大段，它干了什么呢？

当前对象实际上为HashIterator对象，HashIterator对象的hasNext()方法十分的简单