java的HashMap

上一篇文章看了java里面的Map和AbstractMap。

这两个分别是Map的接口和抽象类。

今天要看看java里面的HashMap。

HashMap的结构图为：

HashMap中，键值对保存在HashMap.Entry里面。而Entry主要保存与一个Entry数组table里面。

HashMap根据key的hash值以及数组长度，通过类似取模的方式来判断该Entry存放在table的哪个位置。就是因为这样子，所以Entry会遇到多个Entry存放在同一个table下标的情况。

HashMap.Entry实现了Map.Entry。HashMap.Entry里面有一个类型为HashMap.Entry的next成员变量。当多个Entry放在table的同一个位置的时候，就是以类似链表的形式保存的。

table的默认长度是12。当HashMap里面保存的Entry个数大于table的长度*0.75（DEFAULT_LOAD_FACTOR，该值可以自己设置）的时候，table会自动扩展为原来长度的2倍。所以，我看得出，HashMap里面故意把table的长度限制为2的幂次方。

而这样子做，是因为决定Entry应该保存在table的哪一个地方的那个方法导致的，该方法为：

static int indexFor(int h, int length) {
    return h & (length-1);
}

其中，h是一个和key的hash值相关的值，length是table的长度。在这里可以看得出，为了提高效率，jdk没有使用取模的方式，而是通过h & (length-1)的方式来变相取模。而这个方法来取模，如果length不是2的幂次方，那么就说明table里面有一些下标，是永远不会使用到的。

HashMap里面，还有几个为用户留的方法：

• init()    当HashMap初始化完之后，会调用这个方法。
• HashMap.Entry.recordAccess(HashMap<K,V> m)    当保存在HashMap里面的值，被覆盖setValue的时候，会调用该方法。
• HashMap.Entry.recordRemoval(HashMap<K,V> m)    当保存在HashMap里面的值，被remove的时候，会调用改方法。

其他功能接口在这里就不说了。