散列的基本思想：

如果将一个元素放到数组里面，通常情况就是按顺序放，但是在查找的时候，要么执行顺序查找（第一个，第二个，....），要么使用二分查找（先排序，排序涉及到元素的移动），所以提出hash（哈希函数，也叫散列函数），根据散列函数将要存放的对象做一次运算，运算之后会得到一个值，这个值就是元素应该放到数组当中的位置。当想要查找元素的时候，通过散列函数再进行运算，就会直接定位到所要查找的位置。

但会存在一种冲突情况，再去添加元素的时候，所要存放的位置已经有元素了。这时候会提供一个函数叫“再散列”，重新计算值，放到新的位置。如果再散列又出现冲突的情况，就不再进行散列了，而认为这个数组里面的元素已经快满了（比如长度为6，可能装4个元素，就认为数组已经快满了），这时候会开辟一个新的数组（一个长度更大的数组），并且将原来数组里面的元素通过散列放到新的数组里面，这时候空余的空间就更大一些，再往里面放，发生冲突（碰撞）的概率就降低了。而什么时候认为快满了呢？这个是由load factor（负载因子）决定的。比如load factor为0.75时，则表示当一个数组里面75%的位置上已经被占据了元素，那就认为这个数组已经满了，就会开辟一个新的数组。

参看HashMap的构造方法：

HashMap的构造方法

成员变量loadFactor是float类型的，是对于底层所维护的Hash表的负载因子。

成员变量loadFactor

默认的负载因子，值是0.75f（跟数据结构中的hash有关）。

默认的负载因子

默认的初始化容量，必须是2的指数。

默认的初始化容量

Entry类型的表（数组），当需要的时候会重新调整大小，它的长度必须总是2的指数。

会生成一个长度为16的Entry类型的数组

即：HashMap 底层维护一个数组，我们向 HashMap 中所放置的对象实际上是存储在该数组当中。

一个包级别的访问级别，我们自己定义的类在外面没法调用它，只能java.util包下面的类使用。

包访问级别的初始化方法

Entry类型，一个内部类，实现了Map.Entry接口。

类Entry是内部类

HashMap底层维护的Entry类型的数组，每个元素都是Entry类型，Entry类型会维护两个信息，一个是key的信息，一个是value的信息，而key跟value正好是我们往HashMap里面put的那个key跟value。还有一个Entry类型的引用，用于指向下一个Entry类型的引用。

HashMap中的put()方法

当向 HashMap 中 put 一对键值时，它会根据 key 的 hashCode 值计算出一个位置， 该位置就是此对象准备往数组中存放的位置，而这样做就是为了提高查找的效率，使得查找时间不随着 HashMap 的大小而改变。

根据我们传过来的键的hashCode值，通过散列函数计算（根据经验值计算）一个整数值，但这个整数值仅仅是用于存放位置的参考变量，并不是说计算出来这个hash，它就真的存放在那个位置上了。

indexFor()才是真正决定新增加的Entry对象应该放在什么位置上。根据hash跟数组长度进行与运算，通过这个计算，返回存放的真正位置 i 。

indexFor()返回存放的真正位置i

将Entry对象放置到那个真正的位置上，将真正的位置 i 传递给addEntry()方法。

放置Entry对象

首先把位置 i 上的Entry对象 e 先拿出来，接着构造了一个新的Entry对象，将位置 i 指向了新构造的Entry对象。注意：在构造新的Entry对象时，在Entry的构造方法中，e 赋给了next，即新构造的Entry对象的下一个引用指向了位置 i 上的Entry对象。

如果再去增加一个对象，如果正好也是放置到这个位置上，怎么办呢？回到put()方法参看for循环，如果计算出来的那个位置上已经有Entry对象了，顺着链往下走，每次判断上面的对象是不是一样的。

简而言之：如果该位置没有对象存在，就将此对象直接放进数组当中；如果该位置已经有对象存在了，则顺着此存在的对象的链开始寻找（Entry 类有一个 Entry 类型的 next 成员变量，指向了该对象的下一个对象）， 如果此链上有对象的话，再去使用 equals 方 法进行比较，如果对此链上的某个对象的 equals 方法比较为 false，则将该对象放到数组当中，然后将数组中该位置以前存在的那个对象链接到此对象的后面。

之所以需要将数组位置 i 上的Entry对象链到新增的Entry对象的next成员变量上，是因为操作系统的一个理论：最近被访问的元素，在不远的将来还会被访问。

HashMap 的内存实现布局：

HashMap内存布局

（完）