HashMap 你了解多少

HashMap是如何存放对象

---

在JAVA中最基本的结构有两种，一种是数组，另一种就是模拟指针，也就是我们说的引用。首先可以把HashMap内部的存储结构理解为一个数组，任一一个对象放进来，通过对象Key的hashCode方法，得到对象Key哈稀后的一个整数值，然后根据对象计算的hashCode通过某种策略计算出它要放置的数组中的位置。具体按什么策略来决定放置的位置呢？比较容易能想到的就是通过hashCode与数组长度进行的取模 (hashCode % array.length)，但取模运算的效率比较低，在HashMap中的实现是：

/**

* Returns index for hash code h.

*/

static int indexFor(int h, int length) {

    return h & (length-1);

}

将hashCode值与数组长度减1的值做了个与运算，计算出的结果就是放置数组的索引（因为这一实现，又引出了另一个有意思的话题"HashMap的空间的大小是如何影响自身效率的"，见第二部分）。那现在对HashMap的存放对象有一个初步的认识，存放对象是通过数组来实现，存的时候对象存在哪，取的时候去哪取，都是通过对象KEY的HashCode值来计算存储的数组索引，从而实现读与取。如果H只是通过目前分析的访求来存放对象的话，肯定是不行的，因为不同对象的hashCode值很可能是一样的，其碰撞概率并不低，如字符串"a"与值为97的Integer对象的hashCode值就一样。那这样的问题H是如何解决的呢？上面的分析基础还是很有价值的，H的实现也是在之前分析基础之上，进行了改良。还是通过数组来存，但存的不是单一对象，而是数组中的每个对象都是一个链表结构，为了方便理解，图示:

 

通过上图，可以很直观的理解H的存储结构，H查找对象分两步走，一通过对应的hashCode确定对象应该放置的数组位置，第二步则是在数组对应的链表进行遍历，通过key的equals方法来找到链表中对应的对象(不存在返回NULL)。

 

如何定义HashMap的大小

---

HashMap会在空间占用达到阀值时，会触发resize()操作，resize将会对现有数组进行扩容，HashMap里的所有对象都需要重要进行hash计算，然后把对象放置到新的位置，这将的操作是应该尽量避免的，存储大量对象的时候，更是如此。HashMap

假设有1000个对象要放到MAP中进行存储，假设我们不希望对象在PUT的过程中HashMap发生resize操作，那该定义多大的才保险？1000？NO! HashMap会在数组使用数达到一个阀值的时候进行resize操作，阀值的定义是这样的：

threshold = (int)(capacity * loadFactor)；

HashMap中的loadFactor默认为0.75，所以如果定义一个size为1000的HashMap，当数组占用超过750，就会触发resize操作。所以如果要存放1000个对象，可以假设在极端情况下，这1000个对象的hashCode都不一样，那HashMap需要至少定义1334（1000/0.75），才能确保存放1000个对象的情况下，一定不会出现resize操作。

 

除了上述分析的，定义合适的大小避免HashMap触发resize操作外，HashMap的大小还会影响其内部数组的使用率。HashMap是通过对象的hashCode值来决定放置数组的位置，代码如下：

 /**

* Returns index for hash code h.

*/

static int indexFor(int h, int length) {

    return h & (length-1);

}

通过代码可以发现，当数组大小被定义为2的次方大小，数组的所有位置才都会有命中的可能，如大小为8时，数组的8个位置都可以命中，如大小改为7，那数组的最后一位（即下标为6）的位置，不会有对象落在这个位置上。