V2EX › 3dwelcome 的所有回复 › 第 11 页 / 共 155 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

1 ... 7 8 9 10 11 12 13 14 15 16 ... 155

❮

❯

2022 年 4 月 21 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@vacua "有依据就拿出来啊“

主楼的代码就是依据，你可以试试，用 seed 递增，看看 crc32 后的结果，会不会产生相互冲突。

一个随机数生成器，产生结果不可预测，值有可能会重复。

但 hash 不一样，只要输入值不超出表达范围，是可以进行逆向 hash 的还原操作。

2022 年 4 月 21 日

回复了 zilan 创建的主题 › 程序员 › 片面感觉前端（有一部分）是在提高入行门槛

@prenwang "我感觉已经厌倦软件开发了, 厌倦了一些人喋喋不休的提前端要求, 我是个全栈, 但是前端只能算过得去."

前端一半是设计，是个随时都在变动的业务。然而现代的前端工程化，让逻辑和变化绑在一起，每次修改修改代码都变得费心力。

有些人希望用低代码化，来替代 80%的前端变化，也不是没道理。

之所以我大力推崇 wasm ，也是因为这技术，能剥离出代码里一部分变化和不变化的部分，这点需要语言具有较强的抽象能力。光靠 JS ，是很难完美实现的。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@leimao "发现用某个种子能够超越被外界认可的 SOTA 算法，然后出来吹了一番。"

我也没想着吹，这个帖子的算法和上个帖子的，都是一拍脑袋，就能想出来的超简单方法。

只是上个帖子里，大家都觉得我在吹牛，这才不得已发一点代码，作为对比测试。

要不然光吃瓜群众的口水，都能把给我淹没了。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@panelatta "口嗨谁不会啊？"

你这算法性能不够的，查询性能也是一个很重要的指标。

上个贴所以弃贴，又重新开了一个，就是因为 5bit 的算法查询性能拉跨。

要超越 stl 的 hashmap ，是一件很困难并值得骄傲的事情。所以我才又发帖。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@binux "你都有 lookup table 了，还要你这个 hashmap 干嘛？"

市面上有很多的 perfect hash 算法，各种各样，所有无一例外，都是需要附加额外 lookup table 作为算法数据支撑。

这就是所谓的预处理，如果预处理不产生辅助数据，那就变成 hashmap 这种实时算法了。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@leimao "而且这么跟你说吧，你无法通过换种子或者换 Hash 函数来保证新的 Hashed value 和之前的没有冲突，数学上不支持的话咱还是低调一点。"

我发现你们对 hash 函数的运行机制都是一知半解。实在不行我就再发一贴，这样下去，都快变成连续剧了。

你可以看一下这篇文章： https://www.jandrewrogers.com/2019/02/12/fast-perfect-hashing/

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@binux "比如说一个字典，文章还不能直接写英文单词了？"

不 mix 也可以，那就和普通的完美哈希算法一样，做成 lookup table 保存在内部呗。

我是觉得 seed 和 key 绑定在一起，用起来更方便顺手。比如编译进程序内部字符串资源查找，肯定不需要用户输入。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@vacua "0 要拿理论推导啊，加个盐就成 0 了，没有概率学公式的完美一律是伪科学"

可能你不信，但是"完美"这点，我确实是有依据的。

很多人觉得 hash 只是散列作用，不确定散列后数据是否发生碰撞，也不清楚内部原理。但是我发现，一些特定 hash 函数，只要处理的数据在表达范围内，仅仅只是 reorder ，重排序了数据顺序，并不会对数据范围造成损伤。

换言之，也就是主楼代码里那个 seed 或者说盐，是 100%存在完美解的。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@LeeReamond "毕竟 hashmap 实现的上细节也很丰富"

我查了一下，好象 stl 是用链表加红黑树结构来处理碰撞的情况，速度肯定不慢。

发这个帖子，也就是觉得无碰撞的字符串哈希很有意思，"完美哈希"这个词在我看来，很雅致。

晚期强迫症患者的救星。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

这样说吧，任意两个文件在 MD5 计算后，碰撞的概率是 1.47*10-29 次方。

由于完美哈希导入了盐这个属性，那么新的碰撞概率就是绝对的 0 ，这就是“完美”的含义。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@muzuiget

我知道你指的是范围，可是预处理就意味着我的 hash 值表示范围，永远可以比你数据提供的最大范围还要大。

你要问怎么可能，这就是 incrementally hash function 的属性。一个可增变哈希函数，是可以被针对性构造的，你想要表示多大的范围都可以，并不是 MD5 那种定死截断类函数。

现实中，往往数据范围都是极其有限的。盐（种子）的加入，也能人为去避免碰撞，能发生碰撞的，就不叫完美哈希了。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@muzuiget "我的原始数据可以取值 SHA256 的表示范围，再加一个 SHA512 长度的值，保证让你至少碰撞一次。"

并不是的，完美哈希是预处理，也就是一切数据，都是在可控范围内。

碰撞的概率不仅仅是和 KEY 大小有关系，和数量也有关系。你哪怕一个 KEY 是几百 G 的文件，只要文件总数量没上去，用 MD5 照样可以完美表达。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@muzuiget "表示如果 hash 的表示范围为 N ，如果原始数据有 N + 1 种情形，那必定产生一次碰撞。"

你这说法不成立，hash 的表示范围肯定比原始数据要大。hash function 是个广泛的概念，并不是指某些特定函数。

比如 MD5 装不下 500 万个文件，那么换成 SHA256 也许就可以。总有更大结果的 hash 函数，这种通用函数叫 incrementally hash function 。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@keith1126 "直接用 keyseed 来存每个元素在 dataset 中位置岂不是更直接？查找的时候直接 dataset[keyseed[i]] 不是更快？"

这里 keyseed 用数组保存，只是方便大家能看懂代码。最终是 mix 到原 key 里面的。

用的时候，直接用修改后的 key 来查，没有所谓的 ID 号。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@keith1126 "在建立哈希表之前，你已经预知了所有的 key"

这种情况很常见的，比如搜索一本牛津英文字典，动态加入英文单词是很罕见的情况，大部分都是直接查询。

"如果 key 的空间无限大。...自然就可以避免所谓的冲突。但这并不现实。"

我猜你是指如果 KEY 是文件，处理 500 万个 500G 文件，哈希后肯定会发生冲突。这种也可以避免的，有一些 HASH 函数，拥有 incrementally 特型，也就是随着处理文件长度的增加，HASHVAL 大小也会同步增加。盐也可以同步递增。

但这又是一个延伸的话题，可惜这里的空白处太小，写不下。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@mrgeneral
“呃，hash 冲突是对不同的关键字可能得到同一散列地址，加盐一样冲突，只不过概率小而已。”

昨天我也许和你一样的想法，现在我已经不那么想了。

加了盐后，就相当哈希于一个被设计修改过的 MD5 文件，想要发生碰撞或者不想发生碰撞，都是人为可控的。并不完全依赖概率。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

回帖的时候又灵光一闪，可以不用暴力循环 9 万次。

hash 函数分两类，一种安全 hash ，比如 MD5 和 SHA1 。另外一类是非安全 hash ，比如 hashmap 里用的字符串 hash 。非安全哈希，可以根据 hash 的结果，去人为构建 hash 前的结果。所谓的 hash 碰撞攻击法。

于是，我确信我发现一种美妙的证法，免去暴力循环查找，可惜这里的空白处太小，写不下。

2022 年 4 月 20 日

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap（上图附代码)

@NeroKamin “看起来不就是开放地址法吗”

是递归暴力查找法，比如要给一万个字符串都分配一个 0 ～ 10000 的不重复整数 ID 。基本上需要循环 9 万次，才能找到完美哈希结果。

2022 年 4 月 20 日

回复了 SSang 创建的主题 › 程序员 › 长期的用户令牌是如何存储的呢？存储结构是什么样的？

"像 gitlab 、github 的 token 往往有 90 天，180 天，甚至是永久有效期。"

你是怕 token 时间太长泄露吗？我个人觉得问题不大，后台都是可以控制的。

类似 B 站的 cookie, 接近一年前的我都还在用，也没啥问题。

2022 年 4 月 20 日

回复了 SSang 创建的主题 › 程序员 › 长期的用户令牌是如何存储的呢？存储结构是什么样的？

我用第二种方式，用户在登录时 token 和密码兼容，二选一。

后台我管这玩意叫 userpin ，然后往里面塞一大堆东西，比如分配用户的数据库 ID ，登录时的 APP ID 号，hash 后的部分密码，预计失效过期时间，客户端识别 ID 之类，防修改签名码。当然全部数据，都加密过再传到前端。

由于塞进了好多东西，最终的 token 很大，反正用户也看不见。（手动狗头）

1 ... 7 8 9 10 11 12 13 14 15 16 ... 155

❮

❯