没有合适的资源?快使用搜索试试~ 我知道了~
Multi-copy Cuckoo Hash.pptx
需积分: 17 1 下载量 29 浏览量
2020-01-07
19:54:00
上传
评论
收藏 1.93MB PPTX 举报
温馨提示
北大杨仝老师,Dagang Li, Rong Du, Ziheng Liu, Tong Yang, Bin Cui. Multi-copy Cuckoo Hashing. To appear in ICDE 2019.Multi-copy Cuckoo Hash PPT,帮助理解论文
资源推荐
资源详情
资源评论
Multi-copy
Cuckoo Hash
1
Cuckoo hash
概念:
Cuckoo hashing 使用 d 个 hash 函数给每个 item 提供备用的桶,核心两个词: multiple hashing 和
relocation
特点:
可以达到很高的 load ratio 以及最差的查找耗时是 O(1) ,由于优秀的查找性能,经常被用在存储
系统、数据库、隐私和安全、 网络架构、数据处理。但是良好的查找性能是以插入时复杂的冲突
处理为代价的。多次重插后也可能还是失败。
插入算法描述( d=2 ) :
使用 hashA 、 hashB 计算对应的 key 位置:
1 、两个位置均为空,则任选一个插入;
2 、两个位置中一个为空,则插入到空的那个位置
3 、两个位置均不为空,则踢出一个位置后插入,被踢出的对象调用该算法,再找其另一个位
置,循环直到插入成功。
4 、如果被踢出的次数达到一定的阈值还未插入成功,则认为 hash 表已满,并进行 rehash
查找:
先看在不在 hashA 对应的位置,再看在不在 hashB 对应的位置
Cuckoo hash
(b) 里面显然直接去找 c ,需要的运算更少,但是无法知道走 a 需要的迭代更多还是走 c 需要的
迭代更多(分别是踢三次,踢两次)
(c) 造成死循环了
当哈希表的容量超过默认容量时,必须调整 table 的大小。当容量已经达到最大可能值时,那么
该方法就将容量调整到下一个素数返回,这时,需要创建一张新表,将原表的映射到新表中。
影响 Cuckoo hashing 性能的三大因素
总体来说有三个因素影响了 Cuckoo hashing 的性能:
•
插入时的循环踢出。由于标准 Cuckoo hashing 不能预测哪个 item 有空的备用 buckets ,只能通过
BFS 或者是随机的方式去决策。会浪费时间不说,还可能造成死循环。 (multi-copy)
•
插入失败的损耗太大。传统的 cuckoo hashing 会 rehash ,把所有插入的读出来,重新算一个 hash
函数,然后再放入一个更大的表。 (stash)
•
一个循环中多桶检查。查找一个 item 的时候,所有的备用桶都需要访问,影响了查找性能,尤其
在表很大,需要把表放在外部内存的情况下。 (pre-screening)
Altera FPGA development board ( SRAM 333MHz , SDRAM 200MHz )
哈希计算 1CLK
片上 SRAM 读 3CLK ,写 1CLK
片下 SDRAM 读 18CLK ,写 1CLK
剩余23页未读,继续阅读
资源评论
iroy33
- 粉丝: 110
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 阿里云api网关请求签名示例(java实现).zip
- 通过示例学习 Android 的 RxJava.zip
- 通过多线程编程在 Java 中发现并发模式和特性 线程、锁、原子等等 .zip
- 通过在终端中进行探索来学习 JavaScript .zip
- 通过不仅针对初学者而且针对 JavaScript 爱好者(无论他们的专业水平如何)设计的编码挑战,自然而自信地拥抱 JavaScript .zip
- 适用于 Kotlin 和 Java 的现代 JSON 库 .zip
- yolo5实战-yolo资源
- english-chinese-dictionary-数据结构课程设计
- mp-mysql-injector-spring-boot-starter-sql注入
- lunisolar-删除重复字符
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功