在进行HashMap的底层实现原理的分析之前，先介绍一下Map实现类的结构：

一、Map实现类的结构：

|---Map:双列数据，存储 key-value 对的数据    ----类似于高中的函数： y = f(x)
      |--- HashMap：作为Map的主要实现类；线程不安全的，效率高；可以存储null的key和value
          |--- LinkedHashMap：能够保证在遍历Map元素时，可以按照添加的数据实现遍历。
                  原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素，对于频繁的遍历操作，LinkedHashMap执行效率高于HashMap。
      |--- TreeMap：保证按照添加的 key-value对进行排序，实现排序遍历。此时考虑 key的自然排序或者定制排序。底层使用的是红黑树
      |--- HashTable:作为古老的实现类；线程安全，效率低；不可以存储null的key和value
          |--- Properties:常用来处理配置文件。key和value都是String类型

二、底层实现原理：

先以jdk7为例去说明，

HashMap map = new HashMap():
在实例化以后，底层创建了长度是16的一维数组Entry[] table。

在可能执行过很多次put操作之后：

map.put(key1,value1):
    首先,调用key1所在类的hashCode()计算key1的哈希值，此哈希值经过某种算法计算之后，得到在Entry数组中的存放位置。
    如果此位置上的数据为空，此时的key1-value1添加成功。 ---->情况1
    如果此位置上的数据不为空，(意味着此位之上存在一个或多个数据(以链表形式存在))，比较key1和已经存在的一个或多个数据的
    哈希值：
    如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功 ---->情况2
        如果key1的哈希值与已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals()比较：
            如果equals()返回false：此时key1-value1添加成功。 ---->情况3
            如果此时equals()返回true：使用value1替换value2。 ---->情况4

补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。

    在不断地添加过程中，会涉及到扩容问题，当超出临界值且要存放的位置非空时进行扩充，默认的扩容方式：扩容为原来容量的2倍，并将原来的数据复制过来。

jdk 8相比较于jdk 7在底层实现方面的不同：

1. new HashMap():底层没有创建一个长度为16的数组(类似于单例模式中的懒汉式)
2. jdk 8底层的数组是：Node[]，而非Entry[]。
3. 首次调用put()方法时，底层创建长度为16的数组。
4. jdk 7底层结构只有：数组 + 链表，jdk 8中底层结构：数组 + 链表 + 红黑树。
   当数组的某一个索引位置上的元素以链表形式存在的数组个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所有数组改为使用红黑树存储。

 如若有不正确的地方，请多多指正~

    远风，一个正在努力的年轻人。