散列表要解决的一个问题就是散列值的沖突问题通常是两种方法链表法和开放地址法链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位开放地址法是通过一个探测算法当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位javautilHashMap采用的链表法的方式链表是单向链表因此在删除过程中要自己维持prev节点我想不采用双向链表是从节省空间考虑一个典型的查找过程
for(Entry<KV>e=table[indexFor(hashtablelength)];
e!=null;
e=enext){
Objectk;
if(ehash==hash&&
((k=ekey)==key||(key!=null&&keyequals(k))))
returne;
}
HashMap采用链表法而不是开放地址法猜想可能的原因是从实用角度出发对空间和时间效率做出的折中选择采用开放地址法无论是线性探测或者二次探测都可能造成群集现象而双重散列会要求散列表的装填程度比较低的情况下会有比较好的查找效率容易造成空间的浪费
什么是负载因子？负载因子a定义为
a=散列表的实际元素数目（n）/ 散列表的容量（m）
负载因子衡量的是一个散列表的空间的使用程度负载因子越大表示散列表的装填程度越高反之愈小对于使用链表法的散列表来说查找一个元素的平均次数是 （+a）次因此如果负载因子越大对空间的利用更充分然而后果是查找效率的降低如果负载因子太小那么散列表的数据将过于稀疏对空间造成严重浪费
回到HashMap的实现HashMap中的loadFactor其实定义的就是该map对象允许的最大的负载因子如果超过这个系数将重新resize这个是通过threshold字段来判断看threshold的计算
threshold=(int)(capacity*loadFactor);
结合上面的负载因子的定义公式可知threshold就是在此loadFactor和capacity对应下允许的最大元素数目超过这个数目就重新resize以降低实际的负载因子默认的的负载因子是对空间和时间效率的一个平衡选择注意到的一点是resize的规模是现有 capacity的两倍
if(size++>=threshold)
resize(*tablelength);
可能你也注意到了javautilHashMap对key的hash值多做了一步处理而不是直接使用hashCode
staticinthash(inth){
h^=(h>>>)^(h>>>);
returnh^(h>>>)^(h>>>);
}
这个处理的原因在于HashMap的容量总是采用的p次幂而取index（槽位）的方法是
staticintindexFor(inthintlength){
returnh&(length);
}
这一运算等价于对length取模也就是
h % ^p
返回的将是h的p个最低位组成的数字我们假设hash输入是符合简单一致散列然而这一假设并不能推论出hash的p个最低位也会符合简单一致散列也许h的这p个最低位相同的几率很大那么沖突的几率就非常大了优秀的散列函数应该需要考虑所有的位
因此为了防止这些坏的散列函数造成效率的降低HashMap预先对hash值做了处理以考虑到所有的位根据注释也可以知道这个处理我看不懂留待高人解释也许来自于某本算法书也不一定
我们知道javautilHashMap不是线程安全的因此如果在使用迭代器的过程中有其他线程修改了map那么将抛出ConcurrentModificationException这就是所谓failfast策略（速错）这一策略在源码中的实现是通过 modCount域modCount顾名思义就是修改次数对HashMap内容的修改都将增加这个值那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount
HashIterator(){
expectedModCount=modCount;
if(size>){//advancetofirstentry
Entry[]t=table;
while(index<tlength&&(next=t[index++])==null)
;
}
}
在迭代过程中判断modCount跟expectedModCount是否相等如果不相等就表示已经有其他线程修改了map
finalEntry<KV>nextEntry(){
if(modCount!=expectedModCount)
thrownewConcurrentModificationException();
注意到modCount声明为volatile
保证线程之间修改的可见性
