Java基础教程: 手写HashMap
请务必加入微信群，讲座时间会更新，讲座内容会更改，而且优惠信息，讲座资料会在群里发放
一 讲座简介
HashMap 几乎是每一场面试必考知识点，与其费尽心思的看各种博客，还不如自己撸一个，一劳永逸的解决问题。
二 内容大纲
- HashMap的数据结构
数据结构是什么？这种数据结构在内存中是怎么样，是如何实现O(1)的？ - put，get 等方法的实现
Java中的泛型 - Hash算法，以及冲突的解决方法
对象hashcode是如何来的，为何需要hashcode，在hashmap里的“扰动函数”，”==“以及”equal“的区别 - 二叉树、红黑树简介
Java7和Java8中对冲突的解决方式是不一样的 - HashMap 可能导致的死循环
为何说HashMap不是线程安全的，哪些地方可能导致问题？
三 面向人群
初、中级后端Java开发
四 目标
明白HashMap的底层机制，实现原理
五 参考资料
转载 http://blog.51cto.com/zhangfe...
5.1 HashMap原理图
第一，如图所示，HashMap有3个要素：hash函数+数组+单链表
第二，对于hash函数而言，需要考虑些什么？
一是考虑什么数据结构能直接根据下标在O(1)内取到值，当然是数组了
然后要快，对于给定的Key，要能够快速计算出在数组中的index。那么什么运算够快呢？显然是位运算！
要均匀分布，要较少碰撞。说白了，我们希望通过hash函数，让数据均匀分布在数组中，不希望大量数据发生碰撞，导致链表过长。那么怎么办到呢？也是利用位运算，通过对数据的二进制的位进行移动，让hash函数得到的数据散列开来，从而减低了碰撞的概率。
如果发生了碰撞怎么办？上面的图其实已经说明了JDK的HashMap是如何处理hash冲突的，就是通过单链表解决的。那么除了这个方法，还有其他思路么？比如说，如果发生冲突，那么记下这个冲突的位置为index，然后在加上固定步长，即index+step，找到这个位置，看一下是否仍然冲突，如果继续冲突，那么按照这个思路，继续加上固定步长。其实这就是所谓的线性探测来解决Hash冲突的方法！当然JDK8之后给出了红黑树的实现，但路是一步步走的，不是么：）
5.2 定义接口
定义一个接口，对外暴露快速存取的方法。
注意MyMap接口内部定义了一个内部接口Entry。
5.3 实现接口
HashMap的要素之一，就是数组，自然在这里，我们要定义数组，数组的初始化大小，还要考虑扩容的阀值。
5.4 MyHashMap的构造
构造方法有什么好说的呢？
仔细观察下，你会发现，其实这里使用到了“门面模式”。这里的2个构造方法其实指向的是同一个，但是对外却暴露了2个“门面”！
5.5 Entry
HashMap的要素之一
5.6 实现put方法
第一，要考虑是否扩容？
HashMap中的Entry的数量（数组以及单链表中的所有Entry）是否达到阀值？
第二，如果扩容，意味着新生成一个Entry[]，不仅如此还得重新散列。
第三，要根据Key计算出在Entry[]中的位置，定位后，如果Entry[]中的元素为null，那么可以放入其中，如果不为空，那么得遍历单链表，要么更新value，要么形成一个新的Entry“挤压”单链表！
5.7 hash函数
这里参考了JDK的HashMap的hash函数的实现，这里也再次说明了：要想散列均匀，就得进行二进制的位运算！
5.8 resize和rehash
这里可以看出，对于HashMap而言，如果频繁进行resize/rehash操作，是会影响性能的。
resize/rehash的过程，就是数组变大，原来数组中的entry元素一个个的put到新数组的过程，需要注意的是一些状态变量的改变。
5.9 get实现
get很简单，只需要注意在遍历单链表的过程中使用== or equals来判断下即可。
