0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看技术视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

hash算法在FPGA中的实现(3)

CHANBAEK 来源:FPGA的现今未 作者:FPGA的现今未 2023-09-07 17:02 次阅读

在前面的文章中主要介绍了hash表及其链表的结构,同时说明了如何读取表项。那表项是如何写入的了?前期的文章中有少量的提及,这里单独写一篇,介绍两种常见的方案。

CPU写入表项

当表项由CPU写入的时候,FPGA只进行读取(查表)的时候,那么表项的插入就和FPGA没有什么关系了。唯一要注意的就是表项要有一个CPU的写接口。以hash表为例,如果hash表在内部ram中,那么该ram就是CPU写,逻辑读;如果hash表在DDR中,那只需要给DDR留一个CPU的读写接口即可。

FPGA写入表项

FPGA写入表项的情况相对就要复杂一些,总体来说,不管什么场景,它都是用key计算hash值,然后查表,命中就返回命中结果,不命中就把key写入表中的过程,用一个流程图表示,如下图所示:

图片

hash表的写入

根据前面hash表的构建,我们讨论一种情况,hash桶中存放多个key的场景,其他情况都是相似的处理方式。如下表所示:

图片

当key6来查表时,如果计算出hash值为3,如果读取addr3,发现里面已经有key6,所以查表得到的结果是key6命中的;

当key10来查表时,如果计算出的hash值也是3,读取addr3,发现里面没有key10,返回的结果是不命中,同时还需要把key10和已经存在的其他的key一起写入addr3中,变成如下表:

图片

hash链表的写入

hash链表的写入比hash表的写入要复杂,因为除了key的写入,还涉及到链表地址的回写。以一个具体的例子说明插入链表的过程。

假定hash桶的内容如下图所示,此时假定hash桶已经满了,但是还没有链表,hash桶中具体存放什么key,如何存放key不影响hash链表的写入,所以不在这里说明。

图片

现在来了一个keyA,其hash值对应到上述hash桶,且没有命中,由于hash桶已经满了,无法继续写入hash桶中,必须写入链表了。因为将该keyA给到链表处理模块,链表处理模块会返回一个地址,addr1,表示当前的keyA,已经写入链表,位置在addr1,这时需要把addr1这个地址写回到hash桶中,这样链表才能建立,如下图所示,这样在查表的时候,就可以根据hash桶中的addr1,得到keyA。

图片

同理,如果继续来一个keyB,hash值和keyA相同,在进行key比较的时候,发现hash桶中没有命中,同时链表addr1中也没有命中,即keyB没有命中,需要写入hash桶或者hash链表中。我们在查表的时候得知addr1是最后一链(NULL),因此将keyB送给链表处理模块,链表处理模块返回一个地址,假定为addr2,表示keyB已经写入addr2中,这次也需要把地址addr2写入地址addr1中,实现链表在尾部的插入。如下图所示:

图片

当有key需要继续插入时,以此类推。

对于链表插入的位置,可以在尾部插入外,也可以在头部插入。当链表处理模块返回keyB写入的地址addr2后,将该地址写入hash桶中,同时将hash桶中的地址addr1和keyB写入到addr2中。如下图所示:

图片

无论是从链表头插入还是链表尾插入,都不影响最终结果,可以根据自己设计,选择相对简单的实现方案。

总结

hash链表的插入,一般就是CPU写入和逻辑自己写入。逻辑写入的时候,无论hash桶或者链表每一链的结构如何,都可以采用上述的方式插入链表。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • FPGA
    +关注

    关注

    1629

    文章

    21736

    浏览量

    603333
  • cpu
    cpu
    +关注

    关注

    68

    文章

    10863

    浏览量

    211753
  • Hash算法
    +关注

    关注

    0

    文章

    43

    浏览量

    7382
  • 链表
    +关注

    关注

    0

    文章

    80

    浏览量

    10559
收藏 人收藏

    评论

    相关推荐

    FPGA实现PID算法

    本帖最后由 发烧友LV 于 2014-12-29 20:13 编辑 FPGA实现PID算法,面临着小数的计算,请问大家一般是怎么处
    发表于 12-03 21:59

    怎么spartan 3AN fpga实现遗传算法

    我正在做我的遗传算法项目,有没有办法斯巴达3AN fpga实现遗传
    发表于 04-03 13:16

    1HASH函数软件自保护的应用

    本文介绍了HASH 函数的原理,并重点讨论了其中的SHA-1 算法及其软件自保护的应用和实现技术。关键词:
    发表于 08-07 09:28 17次下载

    MACFPGA的高效实现

    乘累加器DSP算法中有着举足轻重的地位。现在,很多前端DSP算法都通过FPGA实现。结合FPGA
    发表于 08-06 14:41 29次下载

    AESSubBytes算法FPGA实现

    介绍了AES,SubBytes算法FPGA的具体实现.构造SubBytes的S-Box转换表可以直接查找ROM表来
    发表于 11-09 16:42 25次下载

    FPGA实现的FIR算法汽车动态称重仪表的应用

    摘 要: 本文介绍了用FPGA实现的FIR算法,并对这种算法应用于汽车动态称重仪表的结果做了分析。实践证明此
    发表于 03-11 13:46 881次阅读
    <b class='flag-5'>FPGA</b><b class='flag-5'>实现</b>的FIR<b class='flag-5'>算法</b><b class='flag-5'>在</b>汽车动态称重仪表<b class='flag-5'>中</b>的应用

    3DES算法FPGA高速实现

    摘要:介绍3-DES算法的概要;以Xilinx公司SPARTANII结构的XC2S100为例,阐述用FPGA高速实现3-DES
    发表于 06-20 14:22 1457次阅读
    <b class='flag-5'>3</b>DES<b class='flag-5'>算法</b>的<b class='flag-5'>FPGA</b>高速<b class='flag-5'>实现</b>

    基于FPGA的SM3算法优化设计与实现

    基于FPGA的SM3算法优化设计与实现的论文
    发表于 10-29 17:16 5次下载

    FPGA实现CRC算法的程序

    Xilinx FPGA工程例子源码:FPGA实现CRC算法的程序
    发表于 06-07 15:07 28次下载

    基于SHA-1算法的硬件设计及实现FPGA实现

    算法进行深入研究,面向Xilinx K7 410T FPGA 芯片设计SHA-1算法实现结构,完成SHA-1算法编程,进行测试和后续应用。该
    发表于 10-30 16:25 4次下载
    基于SHA-1<b class='flag-5'>算法</b>的硬件设计及<b class='flag-5'>实现</b>(<b class='flag-5'>FPGA</b><b class='flag-5'>实现</b>)

    Hash算法简介

    区块Hash值时(即挖矿的过程),都使用了Hash算法,特别是SHA256算法。比特币系统本身也就是加密算法的衍生物。
    的头像 发表于 06-08 14:01 5041次阅读

    hash算法的原理和实际应用等几个角度,对hash算法进行一个讲解

    由于hash的原理是将输入空间的值映射成hash空间内,而hash值的空间远小于输入的空间。根据抽屉原理,一定会存在不同的输入被映射成相同输出的情况。那么作为一个好的hash
    的头像 发表于 06-03 17:34 3277次阅读
    从<b class='flag-5'>hash</b><b class='flag-5'>算法</b>的原理和实际应用等几个角度,对<b class='flag-5'>hash</b><b class='flag-5'>算法</b>进行一个讲解

    hash算法FPGA实现(1)

    FPGA的设计,尤其是通信领域,经常会遇到hash算法
    的头像 发表于 09-07 17:01 1213次阅读
    <b class='flag-5'>hash</b><b class='flag-5'>算法</b><b class='flag-5'>在</b><b class='flag-5'>FPGA</b><b class='flag-5'>中</b>的<b class='flag-5'>实现</b>(1)

    hash算法FPGA实现(2)

    在前面的文章hash算法FPGA实现(一)
    的头像 发表于 09-07 17:02 808次阅读
    <b class='flag-5'>hash</b><b class='flag-5'>算法</b><b class='flag-5'>在</b><b class='flag-5'>FPGA</b><b class='flag-5'>中</b>的<b class='flag-5'>实现</b>(2)

    hash算法FPGA实现(4)

    在前面的文章主要介绍了hash表及其链表的结构,以及key值的插入方法,既然有key值的插入,那就有key值的删除,一种删除是CPU通过重新刷新链表来删除,另外一种就是FPGA删除了,这里主要讨论
    的头像 发表于 09-07 17:03 735次阅读
    <b class='flag-5'>hash</b><b class='flag-5'>算法</b><b class='flag-5'>在</b><b class='flag-5'>FPGA</b><b class='flag-5'>中</b>的<b class='flag-5'>实现</b>(4)