Note:文章的内容基于JDK1.7进行剖析。1.8做的改变文章开端进行解说。
一、先来相熟一下咱们罕用的HashMap:
1、概述
HashMap基于Map接口实现，元素以键值对的形式存储，并且容许应用null 建和null 值， 因为key不容许反复，因而只能有一个键为null,另外HashMap不能保障放入元素的程序，它是无序的，和放入的程序并不能雷同。HashMap是线程不平安的。
2、继承关系
public class HashMap<K,V>extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable3、根本属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子0.75
static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默认数组
transient int size; //HashMap中元素的数量
int threshold; //判断是否须要调整HashMap的容量
Note：HashMap的扩容操作是一项很耗时的工作，所以如果能估算Map的容量，最好给它一个默认初始值，防止进行屡次扩容。HashMap的线程是不平安的，多线程环境中举荐是ConcurrentHashMap。
二、常被问到的HashMap和Hashtable的区别
1、线程平安
两者最次要的区别在于Hashtable是线程平安，而HashMap则非线程平安。
Hashtable的实现办法外面都增加了synchronized关键字来确保线程同步，因而相对而言HashMap性能会高一些，咱们平时应用时若无非凡需要倡议应用HashMap，在多线程环境下若应用HashMap须要应用Collections.synchronizedMap()办法来获取一个线程平安的汇合。
Note：
Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的外部类，这个类实现了Map接口，在调用办法时应用synchronized来保障线程同步,当然了实际上操作的还是咱们传入的HashMap实例，简略的说就是Collections.synchronizedMap()办法帮咱们在操作HashMap时主动增加了synchronized来实现线程同步，相似的其它Collections.synchronizedXX办法也是相似原理。
2、针对null的不同
HashMap能够应用null作为key，而Hashtable则不容许null作为key
虽说HashMap反对null值作为key，不过倡议还是尽量避免这样应用，因为一旦不小心应用了，若因而引发一些问题，排查起来很是麻烦。
Note：HashMap以null作为key时，总是存储在table数组的第一个节点上。
3、继承构造
HashMap是对Map接口的实现，HashTable实现了Map接口和Dictionary抽象类。
4、初始容量与扩容
HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。
HashMap扩容时是以后容量翻倍即:capacity2，Hashtable扩容时是容量翻倍+1即:capacity2+1。
5、两者计算hash的办法不同
Hashtable计算hash是间接应用key的hashcode对table数组的长度间接进行取模
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
HashMap计算hash对key的hashcode进行了二次hash，以取得更好的散列值，而后对table数组长度取摸。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
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);}static int indexFor(int h, int length) {
return h & (length-1);三、HashMap的数据存储构造
1、HashMap由数组和链表来实现对数据的存储
HashMap采纳Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表构造，它具备Next指针，能够连贯下一个Entry实体，以此来解决Hash抵触的问题。
数组存储区间是间断的，占用内存重大，故空间简单的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除艰难；
链表存储区间离散，占用内存比拟宽松，故空间复杂度很小，但工夫复杂度很大，达O（N）。链表的特点是：寻址艰难，插入和删除容易。
从上图咱们能够发现数据结构由数组+链表组成，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是依照什么样的规定存储到数组中呢。个别状况是通过hash(key.hashCode())%len取得，也就是元素的key的哈希值对数组长度取模失去。比方上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的地位。
HashMap外面实现一个动态外部类Entry，其重要的属性有 hash，key，value，next。
HashMap外面用到链式数据结构的一个概念。下面咱们提到过Entry类外面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash失去的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，当初怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样咱们发现index=0的中央其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑难不必放心。也就是说数组中存储的是最初插入的元素。到这里为止，HashMap的大抵实现，咱们应该曾经分明了。
public V put(K key, V value) {
if (key == null) return putForNullKey(value); //null总是放在数组的第一个链表中 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); //遍历链表 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果key在链表中已存在，则替换为新value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null;}void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next//如果size超过threshold，则裁减table大小。再散列if (size++ >= threshold) resize(2 * table.length);}
四、重要办法深度解析
1、构造方法
HashMap() //无参构造方法
HashMap(int initialCapacity) //指定初始容量的构造方法
HashMap(int initialCapacity, float loadFactor) //指定初始容量和负载因子
HashMap(Map<? extends K,? extends V> m) //指定汇合，转化为HashMap
HashMap提供了四个构造方法，构造方法中 ，依附第三个办法来执行的，然而前三个办法都没有进行数组的初始化操作，即便调用了构造方法此时寄存HaspMap中数组元素的table表长度仍旧为0 。在第四个构造方法中调用了inflateTable()办法实现了table的初始化操作，并将m中的元素增加到HashMap中。
2、增加办法
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //是否初始化 inflateTable(threshold); } if (key == null) //搁置在0号地位 return putForNullKey(value); int hash = hash(key); //计算hash值 int i = indexFor(hash, table.length); //计算在Entry[]中的存储地位 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); //增加到Map中 return null;}
在该办法中，增加键值对时，首先进行table是否初始化的判断，如果没有进行初始化（调配空间，Entry[]数组的长度）。而后进行key是否为null的判断，如果key==null ,搁置在Entry[]的0号地位。计算在Entry[]数组的存储地位，判断该地位上是否已有元素，如果曾经有元素存在，则遍历该Entry[]数组地位上的单链表。判断key是否存在，如果key曾经存在，则用新的value值，替换点旧的value值，并将旧的value值返回。如果key不存在于HashMap中，程序持续向下执行。将key-vlaue, 生成Entry实体，增加到HashMap中的Entry[]数组中。
3、addEntry()
/*
- hash hash值
- key 键值
- value value值
- bucketIndex Entry[]数组中的存储索引
- /
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); //扩容操作，将数据元素从新计算地位后放入newTable中，链表的程序与之前的程序相同 hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); }createEntry(hash, key, value, bucketIndex);}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;}
增加到办法的具体操作，在增加之前先进行容量的判断，如果以后容量达到了阈值，并且须要存储到Entry[]数组中，先进性扩容操作，空充的容量为table长度的2倍。从新计算hash值，和数组存储的地位，扩容后的链表程序与扩容前的链表程序相同。而后将新增加的Entry实体寄存到以后Entry[]地位链表的头部。在1.8之前，新插入的元素都是放在了链表的头部地位，然而这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部。
4、获取办法：get
public V get(Object key) {
if (key == null) //返回table[0] 的value值 return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue();}
final Entry<K,V> getEntry(Object key) {
if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); 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 != null && key.equals(k)))) return e; } return null;}
在get办法中，首先计算hash值，而后调用indexFor()办法失去该key在table中的存储地位，失去该地位的单链表，遍历列表找到key和指定key内容相等的Entry，返回entry.value值。
5、删除办法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key); return (e == null ? null : e.value);}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length); Entry<K,V> prev = table[i]; Entry<K,V> e = prev; while (e != null) { Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { modCount++; size--; if (prev == e) table[i] = next; else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next;}return e;}
删除操作，先计算指定key的hash值，而后计算出table中的存储地位，判断以后地位是否Entry实体存在，如果没有间接返回，若以后地位有Entry实体存在，则开始遍历列表。定义了三个Entry援用，别离为pre, e ,next。 在循环遍历的过程中，首先判断pre 和 e 是否相等，若相等表明，table的以后地位只有一个元素，间接将table[i] = next = null 。若造成了pre -> e -> next 的连贯关系，判断e的key是否和指定的key 相等，若相等则让pre -> next ,e 失去援用。
6、containsKey
public boolean containsKey(Object key) {
return getEntry(key) != null;}final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.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 != null && key.equals(k)))) return e; } return null;}containsKey办法是先计算hash而后应用hash和table.length取摸失去index值，遍历table[index]元素查找是否蕴含key雷同的值。
7、containsValue
public boolean containsValue(Object value) {
if (value == null) return containsNullValue();Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true;return false;}containsValue办法就比拟粗犷了，就是间接遍历所有元素直到找到value，由此可见HashMap的containsValue办法实质上和一般数组和list的contains办法没什么区别，你别指望它会像containsKey那么高效。
五、JDK 1.8的 扭转
1、HashMap采纳数组+链表+红黑树实现。
在Jdk1.8中HashMap的实现形式做了一些扭转，然而根本思维还是没有变得，只是在一些中央做了优化，上面来看一下这些扭转的中央,数据结构的存储由数组+链表的形式，变动为数组+链表+红黑树的存储形式，当链表长度超过阈值（8）时，将链表转换为红黑树。在性能上进一步失去晋升。
2、put办法简略解析：
public V put(K key, V value) {
//调用putVal()办法实现return putVal(hash(key), key, value, false, true);}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//判断table是否初始化，否则初始化操作if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;//计算存储的索引地位，如果没有元素，间接赋值if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);else { Node<K,V> e; K k; //节点若曾经存在，执行赋值操作 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断链表是否是红黑树 else if (p instanceof TreeNode) //红黑树对象操作 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //为链表， for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //链表长度8，将链表转化为红黑树存储 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //key存在，间接笼罩 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; }}//记录批改次数++modCount;//判断是否须要扩容if (++size > threshold) resize();//空操作afterNodeInsertion(evict);return null;}
如果存在key节点，返回旧值，如果不存在则返回Null。