Java的HashMap非常的常用本篇研究它的实现算法最后希望计算出内存占用性能的量化数据然后得出什么时候使用HashMap什么时候不能滥用的结论
HashMap实际上是一个数组数组里面的每个元素都是一个链表每个元素在通过put方法放入HashMap中的时候要按照如下步骤进行根据该元素自身提供的hashcode计算出散列值该散列值就是数组的下标将新元素放入该数组位置的链表中先来看一下数组的定义[java] view plaincopy /** * The table resized as necessary Length MUST Always be a power of two */ transient Entry[] table
这是一个数组transient关键字告诉我们它不会参与序列化既然是一个数组总有数目上限也就意味着如果存入HashMap的元素太多导致数组大小不能够存放所有的链表的时候数组大小必须要能够调整所以首先来考察一下数组容量的相关算法
第一Entry是什么类型？
[java] view plaincopy static class Entry<KV> implements MapEntry<KV> { final K keyV valueEntry<KV> nextfinal int hash
/** * Creates new entry */ Entry（int h K k V v Entry<KV> n） { value = vnext = nkey = khash = h}……
public final boolean equals（Object o） { if （！（o instanceof MapEntry））
return falseMapEntry e = （MapEntry）oObject k = getKey（）Object k = egetKey（）if （k == k || （k ！= null && kequals（k））） { Object v = getValue（）Object v = egetValue（）if （v == v || （v ！= null && vequals（v）））
return true} return false}
public final int hashCode（） { return （key==null ？ keyhashCode（）） ^（value==null ？ valuehashCode（））}……
这是一个HashMap类的内部静态类实现了MapEntry接口接受两个模板参数K和Vkey和hash一旦在构造函数中被初始化就不可改变并且由于有next的存在Entry可以构成一个单向链表
比较重要的是equals和hashCode方法代码先列出来后面再解释
第二初始容量的设定大多数都在下面的构造函数里面用于指定的initialCapacity不准小于也不能超过最大值并且最终的capicity必须是的n次方还有如果使用了无参数的构造函数默认会创建一个拥有个元素的数组
[java] view plaincopy public HashMap（int initialCapacity float loadFactor） { if （initialCapacity < ）
throw new IllegalArgumentException（Illegal initial capacity + initialCapacity）if （initialCapacity > MAXIMUM_CAPACITY）
initialCapacity = MAXIMUM_CAPACITYif （loadFactor <= || FloatisNaN（loadFactor））
throw new IllegalArgumentException（Illegal load factor + loadFactor）
// Find a power of >= initialCapacity int capacity = while （capacity < initialCapacity）
capacity <<=
thisloadFactor = loadFactorthreshold = （int）（capacity * loadFactor）table = new Entry[capacity]init（）}
第三什么时候应该调整数组的大小？
算法是这样有一个变量size保存了实际数组已经使用了多少个元素并且如果size的值达到了变量threshold的值就必须扩充数组的容量threshold=capicity*loadFactorcapicity是数组最大的容纳元素个数loadFactor可以在构造函数中制定否则采用默认值fcapicity的最大值是<<（也就是的次方）由此我们可以看到HashMap最多存放亿多个链表
第四如何调整数组大小？
答案是倍很像C++里面的vector的分配策略
[java] view plaincopy void addEntry（int hash K key V value int bucketIndex） { Entry<KV> e = table[bucketIndex]table[bucketIndex] = new Entry<KV>（hash key value e）if （size++ >= threshold）
resize（ * tablelength）}
第五为什么数组大小必须是的倍数？
在后面介绍散列值算法的时候会回答
