精选文章 hash冲突解决

hash冲突解决

作者:csdn_9527666 时间: 2021-02-05 09:45:01
csdn_9527666 2021-02-05 09:45:01
【摘要】1 开放寻址法 
如冲突则根据指定步长向后寻找直到找到空位或没有位置 
步长算法: 
1.1 线性探查 步长为1 如threadlocal 
key1:hash(key)+0 
key2:hash(key)+1 
key3:hash(key)+2 
1.2 平方探测法  计算下一次的步长 
key1:hash(key)+0 
key2:hash(key)+1^2 
key3:hash(key...

1 开放寻址法

如冲突则根据指定步长向后寻找直到找到空位或没有位置

步长算法:

1.1 线性探查 步长为1 如threadlocal

key1:hash(key)+0

key2:hash(key)+1

key3:hash(key)+2

1.2 平方探测法  计算下一次的步长

key1:hash(key)+0

key2:hash(key)+1^2

key3:hash(key)+2^2

1.3  随机探测法 步长为随机生成的数  疑问:查询时如何查?如遍历查询有何意义?

缺点:

  • 查找性能不好:这种方法建立起来的哈希表,当冲突多的时候数据容易堆集在一起,这时候对查找不友好;
  • 删除节点不能真实删除浪费内存:删除结点的时候不能简单将结点的空间置空,否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点,只能在被删结点上添加删除标记,而不能真正删除结点;
  • 如果哈希表的空间已经满了,还需要建立一个溢出表,来存入多出来的元素。
  • 为了减少冲突,负载因子要小些,导致内存浪费

 

2 再哈希

有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数  直到不再冲突

也存在不能删除的问题? 如删除某元素后,查询另一个key调用第二个哈希函数后查询为null 无法确定继续处理还是key不存在?

缺点: 增加了计算时间

 

3 建立公共溢出区

将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

缺点:  如未能命中哈希表 需要遍历查找溢出表 查询效率低

 

4 拉链法(或成树法, 树是一种特殊的链表。树形转化后 插入更慢(相比于头插法) 查询更快(冲突节点数目较多时))

如出现冲突,将其作为链表一个节点加入头或者尾巴处(分为头插法和尾插法)

拉链法的优点:

  • 处理冲突的方式简单,且无堆集现象,一般不会发生冲突,因此平均查找长度较短;
  • 由于拉链法中各链表上的结点空间是动态申请的,所以它更适合造表前无法确定表长的情况;
  • 删除结点操作易于实现,只要简单地删除链表上的相应的结点即可。

拉链法的缺点:需要额外的存储空间。

从HashMap的底层结构中我们可以看到,HashMap采用是数组+链表/红黑树的组合来作为底层结构,也就是开放地址法+链地址法的方式来实现HashMap。

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:[kuangbin带你飞]专题1-23 专题一 简单搜索 POJ 1426 Find The Multiple 用深搜dfs枚举结果+习得llu

下一篇:matplotlib 设置绘图时显示中文

您可能感兴趣

  • 服务器断电导致大量虚拟机丢失的解决过程

    一、服务器数据恢复故障描述机房突然断电导致整个存储瘫痪,加电后存储依然无法使用。经过用户方工程师诊断后认为是断电导致存储阵列损坏。 整个存储是由12块日立硬盘(3T SAS硬盘)组成的RAID-6磁盘阵列,被分成一个卷,分配给几台Vmware的ESXI主机做共享存储。整个卷中存放了大量的Windows虚拟机,虚拟机基本都是模板创建的,因此系统盘都统一...

  • touchstart click 冲突

    通过preventDefault()方法,可以阻止后面事件的触发。 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <style> *{ padding: 0...

  • DHCP服务开启了,为什么老是网络冲突

    <b> <a target="_blank" href="http://www.hnbkhb.com/ " >河南</a> <a target="_blank" href="http://www.hnzzfk.com/ " >河南</a> <a target="_blank" href="http://www.0371fkyy...

  • 日记 [2006年12月25日]-FC6继续探索中-成功解决rmvb卡的问题

    周六日用yum慢死了,今天又在百度上寻找资源,发现了linuxsir.org 哈哈,有Feoora Core 专区也 [url]http://bbs.linuxsir.org/forumdisplay.php?f=40[/url]   ...

  • Oracle解决ora-01653 无法通过1024扩展

    1.oracle查询表空间是否已满 select dbf.tablespace_name,dbf.totalspace "总量(M)",dbf.totalblocks as 总块数,dfs.freespace "剩余总量(M)",dfs.freeblocks "剩余块数",(dfs.freespace / dbf.totalspace) * 100 ...

  • 成功解决洗衣机莫名其妙的F1错误

    先感慨一下:软件编了N年,网络也弄了N年,没想到在51上写的第一篇博客是关于洗衣机的。 切入正题:最近一段时间一直被洗衣机困扰,之前出现的问题是,洗着洗着,就开始进水的同时不停的排水,而且这种情况并不是一直出现,而是有时候出现,偶尔又不出现,因为常常把洗衣机开着不管,结果就是不但没把衣服洗了,而且白白流掉的水比我半年正常使用的水还多。自...

  • 解决:QH6249 qh_lib_check: Incorrect qhull library called.

    在执行一个python文件的时候,突然报一下错误: QH6248 qh_lib_check: Incorrect qhull library called. Caller uses reentrant Qhull wh...

  • Oracle创建视图权限不足(解决)

    问题: 使用scott登录Oracle以后,创建视图,提示“权限不够”,怎么解决? 回答: 这是因为scott这个帐户目前没有创建视图的权限。解决方法为: 首先使用system帐户进行登录, 〈--注:其中“tiger”为安装Oracle时所指定的密码(可修改): --修改用户密码: alter user myUser...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
hash冲突解决介绍:华为云为您免费提供hash冲突解决在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多hash冲突解决的相关内容。| 移动地址: hash冲突解决 | 写博客