跟着java源码学算法--散列表(hashMap源码分析)

定义

   散列表又叫哈希表，字典表，故名思义，是一种依据hash算法实现的类似字典的数据结构。比如，我们查字典查“王”字，我们会先查W，然后Wang找到最后的页码。这中从W到Wang的过程就相当于我们的Hash运算，获取页码，然后我们进到当前页后，又会发现有“王”、“往”、“网”......等等一堆字，这就是所谓的hash冲突。解决hash冲突的算法常用有四种：

1. 开放定址法
   处理方法又有线性探测法、平方探测法等，以线性探测法为例简单说，比如存放数值89、34、23、45、2、90、33，表长度为10（0-9），插入89:89%10=9,34%10=4,依次存入hash表中，到存入3时发生冲突，线性探测（直线下推），3%10=3+1=4->4+1=5->5+1=6, 依次类推，33存入7行中，如下图

   
   线性探测

2. 链表法
   java采用的此方法，每个冲突点，都是一条链表，冲突值会拼接到链表中

   
   链表法

3. 再哈希法

4. 建立公共溢出区

明天补充完。。