跟着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. 建立公共溢出区

明天补充完。。

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

友情链接更多精彩内容