本文的源码是基于JDK1.8版本，在学习HashMap之前，先了解数组和链表的知识。

数组：
数组具有遍历快，增删慢的特点。数组在堆中是一块连续的存储空间，遍历时数组的首地址是知道的（首地址=首地址+元素字节数 * 下标），所以遍历快（数组遍历的时间复杂度为O(1) ）；增删慢是因为，当在中间插入或删除元素时，会造成该元素后面所有元素地址的改变，所以增删慢（增删的时间复杂度为O(n) ）。

链表：
链表具有增删快，遍历慢的特点。链表中各元素的内存空间是不连续的，一个节点至少包含节点数据与后继节点的引用，所以在插入删除时，只需修改该位置的前驱节点与后继节点即可，链表在插入删除时的时间复杂度为O(1)。但是在遍历时，get(n)元素时，需要从第一个开始，依次拿到后面元素的地址，进行遍历，直到遍历到第n个元素（时间复杂度为O(n) ），所以效率极低。

HashMap:
Hash表是一个数组+链表的结构，这种结构能够保证在遍历与增删的过程中，如果不产生hash碰撞，仅需一次定位就可完成，时间复杂度能保证在O(1)。  在jdk1.7中，只是单纯的数组+链表的结构，但是如果散列表中的hash碰撞过多时，会造成效率的降低，所以在JKD1.8中对这种情况进行了控制，当一个hash值上的链表长度大于8时，该节点上的数据就不再以链表进行存储，而是转成了一个红黑树。

hash碰撞：
hash是指，两个元素通过hash函数计算出的值是一样的，是同一个存储地址。当后面的元素要插入到这个地址时，发现已经被占用了，这时候就产生了hash冲突

hash冲突的解决方法：
开放定址法(查询产生冲突的地址的下一个地址是否被占用，直到寻找到空的地址)，再散列法，链地址法等。hashmap采用的就是链地址法，jdk1.7中，当冲突时，在冲突的地址上生成一个链表，将冲突的元素的key，通过equals进行比较，相同即覆盖，不同则添加到链表上，此时如果链表过长，效率就会大大降低，查找和添加操作的时间复杂度都为O(n)；但是在jdk1.8中如果链表长度大于8，链表就会转化为红黑树，下图就是1.8版本的（图片来源https://segmentfault.com/a/1190000012926722），时间复杂度也降为了O(logn)，性能得到了很大的优化。

下面通过源码分析一下，HashMap的底层实现

首先，hashMap的主干是一个Node数组（jdk1.7及之前为Entry数组）每一个Node包含一个key与value的键值对，与一个next指向下一个node，hashMap由多个Node对象组成。

Node是HhaspMap中的一个静态内部类 ：

static class Node<K,V> implements Map.Entry<K,V> {          final int hash;          final K key;          V value;          Node<K,V> next;            Node(int hash, K key, V value, Node<K,V> next) {             this.hash = hash;              this.key = key;              this.value = value;              this.next = next;          }            public final K getKey()        { return key; }          public final V getValue()      { return value; }          public final String toString() { return key + "=" + value; }           //hashCode等其他代码     }

再看下hashMap中几个重要的字段：

//默认初始容量为16，0000 0001 左移4位 0001 0000为16，主干数组的初始容量为16，而且这个数组 //必须是2的倍数(后面说为什么是2的倍数)static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16   //最大容量为int的最大值除2static final int MAXIMUM_CAPACITY = 1 << 30;   //默认加载因子为0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;   //阈值，如果主干数组上的链表的长度大于8，链表转化为红黑树 static final int TREEIFY_THRESHOLD = 8;   //hash表扩容后，如果发现某一个红黑树的长度小于6，则会重新退化为链表 static final int UNTREEIFY_THRESHOLD = 6;   //当hashmap容量大于64时，链表才能转成红黑树 static final int MIN_TREEIFY_CAPACITY = 64;