V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2152 days ago, the information mentioned may be changed or developed.
其实很简单：
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 、怎么在冲突的时候还能知道是不是我要找的元素；
 |
1
optional Jun 11, 2020  3
这是成熟的方案啊，就是拉链法，还有一种开放地址法
|
 |
2
guagual OP 谢谢大佬提醒，刚才查了一下，开放地址法应该就是将拉链法中的链表形式改为在自己的数组中往后面找个没有占用的位置来存储吧？
其实怎么判断当前元素是否是自己要找的元素的逻辑还是一样的是吧？ 我原来就是不知道冲突的时候怎么判断当前元素是不是自己😂😂😂，所以感觉很多不好办的问题就是改数据结构就好了。。。 |
|
3
guagual OP @optional 开放地址法如果存储的数组空间不够大的话，遇到全部位置都被占满了，那就只能给数组扩容了，
还有一种再散列法，其实也是一样的。只是不是往后找而已，而是再执行一次哈希。 |
 |
4
lance6716 Jun 11, 2020 via Android 4
思而不学则殆
|
 |
5
pakro888 Jun 11, 2020
建议学一下数据结构
|
 |
6
wzzzx Jun 11, 2020
有这想法挺不错的丫，但还可以多看看书
|
|
7
wzzzx Jun 11, 2020
其次，可以了解一下哈希洪水攻击，用来收拾你这个思路的 2333
|
 |
8
itechify PRO JAVA 面试中必考 HashMap 的知识点？
|
|
9
guagual OP @wzzzx 查了一下哈希洪水攻击，主要是如果某一个链太长，那么找起来就很慢。
这样的话，极端点，攻击者需要找到很多某一个冲突点的 key-value 对，或者说构造这些 key， 这样的话就需要在哈希函数上面做手脚了，就是说要是一个顺推很容易，反推很难的哈希函数(不可逆)，而常见的哈希函数应该都不可逆。 如果是开放地址法和再散列法也应该有这个问题吧。 |
 |
10
ruanimal Jun 11, 2020
哈哈，重新发现万有引力
|
 |
11
redford42 Jun 11, 2020
java 的实现方法就是如果一条链很长会转为红黑树
|
 |
12
wysnylc Jun 11, 2020
建议看看 Java 的 HashMap,可以完善你的想法
|
 |
13
xsqfjys Jun 11, 2020
建议阅读《数据结构与算法分析》
|
 |
14
nightwitch Jun 11, 2020
拉链法，常规操作。
"如果当前地址存放的是一个值：则在该地址存放指针，该指针指向一个链表，同时需要将原来这个位置的值放入链表，新的值也加入链表；" 这里可以被攻击的，如果故意构造碰撞，很快这个链表就会变得很长，复杂度就从 O(1)退化成 O(n)了。Java 的方法是当链表足够长的时候在这里转成红黑树。 |
 |
15
rcp Jun 11, 2020
这确定不是 HashMap ?
|
 |
16
no1xsyzy Jun 11, 2020
War3 的实现是三层不同方法的哈希，也不存储原值，实在碰撞就碰撞吧，因为是游戏，碰撞也没太大关系，实在常见的碰撞稍微改改哈希算法就行
|
 |
17
tiedan Jun 11, 2020
拉链法。。
|
 |
18
yuudachiPoi Jun 11, 2020
我找了很久与拉链法的核心区别 然后失败了。。
|
 |
19
goodboy95 Jun 11, 2020
有一说一，自己这么想想还是蛮不错的，之后看拉链法的时候印象会更深刻一点（虽然这玩意好像也没啥难度）
之前啥算法都没学的时候，我就盯着一道 ACM 新手题想了老久，最后自己把 BFS 想出来了，结果过了半年之后在课堂上接触到了 hhh |
|
25
guagual OP @nightwitch 在大佬面前献丑了。
|
|
26
guagual OP @yuudachiPoi 区别只是冲突之后的存储方式不一样吧？
|
 |
27
Jacky23333 Jun 12, 2020 via Android
这不就是老师课堂上讲的拉链法吗....不过楼主如果是自己独立思考出来的那还是挺厉害的，点赞！
|
 |
28
larisboy Jun 12, 2020
这种算法在极端情况下复杂度会变成 O （ n ）把，感觉并不完美
|
Select Language