V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
guagual
V2EX  ›  程序员

闲来无事 想到的哈希冲突 解决方案 思路

  •  1
     
  •   guagual · 2020-06-11 12:15:20 +08:00 · 3001 次点击
    这是一个创建于 709 天前的主题,其中的信息可能已经有所发展或是发生改变。

    其实很简单:

    1 、大前提是选择哈希结果平均分布的哈希函数,这个有很多种方案,不是关键;

    2 、在存储哈希结果的时候,

    2.1 、如果当前地址没有被占用,则直接存放值;

    2.2 、如果当前地址已经被占用了:

    2.2.1 、如果当前地址存放的是一个值:则在该地址存放指针,该指针指向一个链表,同时需要将原来这个位置的值放入链表,新的值也加入链表;

    2.2.2 、如果当前地址存放的是一个指针:直接在这个指针所指的链表里面加入新的值节点即可;

    ps:上面所说的值 是一个 结构体对象,这个结构体对象里面即有 key 又有 hash(key)和 value,以下简称值;

    3 、这样的话:当查找的时候通过将 key 传入 hash 函数的时候,得到哈希之后的 hashkey:

    3.1 、如果 hashkey 这个地址里面存储的是一个值,那么说明这个位置没有哈希冲突,直接取出值返回即可;

    3.2 、如果 hashkey 这个地址里面存储的是一个指针,那么说明这个 key 有哈希冲突,所以就按照有哈希冲突的方法来处理:

    3.2.1 、先找到这个指针对应的链表,然后挨个遍历链表,查看每一个元素,查看该元素的 key 是否和我所传入的 key 相同:

    3.2.1.1 、如果相同则说明是我要找的那个值,查找成功;

    3.2.1.2 、如果不同则继续往后找,直到找到链表最后都没有我当前的 key 的话,则整个查找失败。

    总结:

    1 、哈希冲突不可避免;

    2 、怎么在冲突的时候还能知道是不是我要找的元素;

    29 条回复    2020-06-12 12:12:16 +08:00
    optional
        1
    optional  
       2020-06-11 12:18:34 +08:00   ❤️ 3
    这是成熟的方案啊,就是拉链法,还有一种开放地址法
    guagual
        2
    guagual  
    OP
       2020-06-11 12:38:28 +08:00
    谢谢大佬提醒,刚才查了一下,开放地址法应该就是将拉链法中的链表形式改为在自己的数组中往后面找个没有占用的位置来存储吧?
    其实怎么判断当前元素是否是自己要找的元素的逻辑还是一样的是吧?
    我原来就是不知道冲突的时候怎么判断当前元素是不是自己😂😂😂,所以感觉很多不好办的问题就是改数据结构就好了。。。
    guagual
        3
    guagual  
    OP
       2020-06-11 12:42:12 +08:00
    @optional 开放地址法如果存储的数组空间不够大的话,遇到全部位置都被占满了,那就只能给数组扩容了,
    还有一种再散列法,其实也是一样的。只是不是往后找而已,而是再执行一次哈希。
    lance6716
        4
    lance6716  
       2020-06-11 12:59:42 +08:00 via Android   ❤️ 4
    思而不学则殆
    pakro888
        5
    pakro888  
       2020-06-11 13:00:00 +08:00
    建议学一下数据结构
    wzzzx
        6
    wzzzx  
       2020-06-11 13:06:01 +08:00
    有这想法挺不错的丫,但还可以多看看书
    wzzzx
        7
    wzzzx  
       2020-06-11 13:08:12 +08:00
    其次,可以了解一下哈希洪水攻击,用来收拾你这个思路的 2333
    oneisall8955
        8
    oneisall8955  
       2020-06-11 13:10:49 +08:00 via Android
    JAVA 面试中必考 HashMap 的知识点?
    guagual
        9
    guagual  
    OP
       2020-06-11 13:20:27 +08:00
    @wzzzx 查了一下哈希洪水攻击,主要是如果某一个链太长,那么找起来就很慢。
    这样的话,极端点,攻击者需要找到很多某一个冲突点的 key-value 对,或者说构造这些 key,
    这样的话就需要在哈希函数上面做手脚了,就是说要是一个顺推很容易,反推很难的哈希函数(不可逆),而常见的哈希函数应该都不可逆。

    如果是开放地址法和再散列法也应该有这个问题吧。
    ruanimal
        10
    ruanimal  
       2020-06-11 14:21:10 +08:00
    哈哈,重新发现万有引力
    redford42
        11
    redford42  
       2020-06-11 14:43:37 +08:00
    java 的实现方法就是如果一条链很长会转为红黑树
    wysnylc
        12
    wysnylc  
       2020-06-11 15:05:57 +08:00
    建议看看 Java 的 HashMap,可以完善你的想法
    xsqfjys
        13
    xsqfjys  
       2020-06-11 15:08:34 +08:00
    建议阅读《数据结构与算法分析》
    nightwitch
        14
    nightwitch  
       2020-06-11 15:16:14 +08:00
    拉链法,常规操作。

    "如果当前地址存放的是一个值:则在该地址存放指针,该指针指向一个链表,同时需要将原来这个位置的值放入链表,新的值也加入链表;"

    这里可以被攻击的,如果故意构造碰撞,很快这个链表就会变得很长,复杂度就从 O(1)退化成 O(n)了。Java 的方法是当链表足够长的时候在这里转成红黑树。
    rcp
        15
    rcp  
       2020-06-11 15:17:33 +08:00
    这确定不是 HashMap ?
    no1xsyzy
        16
    no1xsyzy  
       2020-06-11 15:32:55 +08:00
    War3 的实现是三层不同方法的哈希,也不存储原值,实在碰撞就碰撞吧,因为是游戏,碰撞也没太大关系,实在常见的碰撞稍微改改哈希算法就行
    tiedan
        17
    tiedan  
       2020-06-11 15:40:51 +08:00
    拉链法。。
    yuudachiPoi
        18
    yuudachiPoi  
       2020-06-11 15:58:03 +08:00
    我找了很久与拉链法的核心区别 然后失败了。。
    goodboy95
        19
    goodboy95  
       2020-06-11 20:52:09 +08:00
    有一说一,自己这么想想还是蛮不错的,之后看拉链法的时候印象会更深刻一点(虽然这玩意好像也没啥难度)
    之前啥算法都没学的时候,我就盯着一道 ACM 新手题想了老久,最后自己把 BFS 想出来了,结果过了半年之后在课堂上接触到了 hhh
    guagual
        20
    guagual  
    OP
       2020-06-11 23:40:20 +08:00
    @ruanimal 😂😂😂在各位大佬面前献丑了。
    guagual
        21
    guagual  
    OP
       2020-06-11 23:40:33 +08:00
    @pakro888 谢谢建议
    guagual
        22
    guagual  
    OP
       2020-06-11 23:41:03 +08:00
    @lance6716 看来我很危险了,一定要多看书
    guagual
        23
    guagual  
    OP
       2020-06-11 23:42:01 +08:00
    @redford42 👍,厉害厉害。红黑树可以降低复杂度,据说是链表超过 8 个 node 再转换成红黑树。
    guagual
        24
    guagual  
    OP
       2020-06-11 23:42:16 +08:00
    @xsqfjys 谢谢宝贵的建议
    guagual
        25
    guagual  
    OP
       2020-06-11 23:42:36 +08:00
    @nightwitch 在大佬面前献丑了。
    guagual
        26
    guagual  
    OP
       2020-06-11 23:43:24 +08:00
    @yuudachiPoi 区别只是冲突之后的存储方式不一样吧?
    Jacky23333
        27
    Jacky23333  
       2020-06-12 00:49:02 +08:00 via Android
    这不就是老师课堂上讲的拉链法吗....不过楼主如果是自己独立思考出来的那还是挺厉害的,点赞!
    larisboy
        28
    larisboy  
       2020-06-12 12:08:07 +08:00
    这种算法在极端情况下复杂度会变成 O ( n )把,感觉并不完美
    guagual
        29
    guagual  
    OP
       2020-06-12 12:12:16 +08:00
    @larisboy 所以有大佬进行了改进,如果链表长度大于 8,则将链表存储改为红黑树存储。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2448 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 12:14 · PVG 20:14 · LAX 05:14 · JFK 08:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.