HashMap

一、原理

首先解释一下什么是叫原理：
原理是指基本规律。多指事物运行的原由或者规律。

二、HashMap原理

HashMap实际上就是哈希（又名散列）表的一种实现原理。

三、哈希表原理

困惑：哈希表是啥玩意？它又是如何实现的呢？
哈希表有多种不同的实现方法，最常用的一种方法是拉链法，我们可以称之为链表的数组（说白了就是一个数组里存着一种链表格式的对象）

三、数组和链表

困惑：数组是啥，链表又是啥？

1. 数组：内存里存储区间连续的数据，这是原理。
2. 链表：内存中存储比较离散，但会标记下一个数据的位置。

四、深入理解HashMap原理

因为HashMap是哈希表的一种实现方式，你先有个概念就是先将这个HashMap想象成一个大数组（水桶又名bucket）那么其实我们put数据的时候就是将key和value封装成了一个Entry对象（下文有讲），首先根据key生成一个hashcode，实际上它是调用了一个hashcode()方法返回了一个int类型的值，然后通过扰乱模型（减少碰撞几率，这里有一个碰撞探测的概念）获取一个下标，这里给大家贴出一片文章：
讲的是将key转化成hashcode为何要这么复杂
看了这篇文章后真的觉得自己的认知和对底层处理方法认识的太少了。
好了，接着讲，那么通过key拿到了下标后，他会去对应的下标位置找是否已经存在数据了，如果存在数据会覆盖，否则会将数据放到这个下标上。

五、碰撞探测以及碰撞后的解决方案

讲到这里，其实还有一种情况发生，那就是HashMap下标发生碰撞，会有这种几率发生的，而且几率还不小（参考上文中知乎的那篇文章就会明白）
解决方案：上文讲到过，Entry这个类，这个类实际上是HashMap中一个静态的内部类，它有三个非常重要的属性，key，value，next，可以根据字段名来分析一下它的含义，key和value不用多说一看就懂，next我观察源码后看到类里这样声明：Node<K,V> next;
原来Entry通过这个字段来实现的链表结构，这个next用来存啥，实际上就是为了解决上述的问题，如果发生了碰撞那么就会在这个下标下用最新的对象覆盖原有对象，并将之前的Entry对象放到新对象的next中。

六、不同的key相同hashcode如何定位value

不同的key相同hashcode发生碰撞后我怎么才能根据指定的key找到对应的value呢，其实很简单，HashMap会遍历这个下标位的链表数据（也就是根据next来去循环遍历）通过equals方法去比对。
HashMap中get方法部分源码：

    if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }

七、HashMap扩容

1. HashMap默认的初始容量（想象成数组）为16。
2. 加载因子为0.75，啥意思？即当元素个数超过容量长度0.75倍时进行扩容，举例默认是容量长度是16，那么当长度为12时开始扩容。
3. 扩容增量：原容量的1倍。

八、总结语

1. 在JDK1.6中，HashMap采用位桶（数组）+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
2. 在JDK1.8中，HashMap采用位桶（数组）+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

总结语：通过我的这篇文章希望你能真正的掌握HashMap的实现原理。