HashMap的实现方法

分析了一下HashMap这个类后，发现实现机制也挺简单的。当然里面的散列函数比较复杂，还没看明白，但大致就是那么回事了。

首先散列的快速读取是基于数组的，所以，先定义一个数组，存放Entry，大小由capacity决定，默认为16。

 

当调用put(key,value)函数时

1，key调用自身对象的hashcode函数，返回一个int值A。

2，对A进行一次包装hash(A)返回hash值B。这个B会被存储起来。

3，indexFor(B)方法返回int值C，这个C就是即将要保存的最初定义数组中的索引。

indexFor中使用(B & leng -1)使得返回的值始终小于leng(leng为2的幂值)。

4，此处有点绕，得看完Entry定义才能明白。

Enry有四个东西需要保存：hash值，key，value，next Entry。

因为数组大小是一定的，不能无限扩容，所以就利用了链表，一个数组元素里放了一个Entry，当需要存到相同数组元素中时，会把占了位的Entry对象搬出来，然后新建一个Entry对象，这个对象指向原先的对象(新Entry.next Entry = 原Entry)。

理论上讲，不管数组多大，都是可以的，程序照样运行，但链表的检索效率太低，所以，定义了factor即所谓的负载因子，默认为0.75，当负载过大时，会扩容，扩大为原先的2倍，这样可以避免链表过长。

比如，使用默认的构造函数new HashMap()时，数组长度为16，负载因子0.75，当数组中有12个元素时(大于等于12)，进行resize，使得数组长度为32。

当负载因子越小，越容易达到扩容的条件，数组元素中的链表就越短，查询速度就会越快，但会增加重散列的开销。

这个数组的长度一定是2的幂值，我的理解就是方便使用indexFor函数，理论上最好是质数，这里特殊，Java编程思想中也有提到。

 

另外还有两个问题

1，key值为null时，直接存放到数组的第一个元素，即索引为0。

2，当在Entry链表中发现相同key值时，利用equals方法进行比较，相同则覆盖value或取出value。

所以，若干本书上强调，当某个类当散列结构的key时，一定得重写hashcode和equals函数，因为，Object类的hashcode是基于内存地址计算的，相同的对象会返回不同的值。而不同的对象也会产生相同的hashcode，所以得再利用equals函数，进行判定。