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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

❮

❯

2022-04-20 22:51:33 +08:00

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

@panelatta "口嗨谁不会啊？"

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

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

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

2022-04-20 22:45:33 +08:00

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

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

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

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

2022-04-20 22:34:33 +08:00

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

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

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

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

2022-04-20 22:23:46 +08:00

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

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

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

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

2022-04-20 22:19:18 +08:00

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

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

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

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

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

2022-04-20 22:08:16 +08:00

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

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

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

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

晚期强迫症患者的救星。

2022-04-20 22:04:19 +08:00

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

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

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

2022-04-20 21:51:40 +08:00

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

@muzuiget

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

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

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

2022-04-20 21:26:34 +08:00

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

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

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

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

2022-04-20 21:04:06 +08:00

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

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

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

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

2022-04-20 20:48:11 +08:00

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

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

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

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

2022-04-20 20:38:30 +08:00

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

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

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

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

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

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

2022-04-20 20:10:42 +08:00

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

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

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

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

2022-04-20 18:38:38 +08:00

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

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

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

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

2022-04-20 18:24:41 +08:00

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

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

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

2022-04-20 18:22:07 +08:00

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

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

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

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

2022-04-20 18:08:53 +08:00

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

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

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

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

2022-04-20 09:28:47 +08:00

回复了 LeeReamond 创建的主题 › 问与答 › 命令行程序是怎么让自己输出的最后一行文字变化的。。

@mingl0280 然而\r 并不会把旧数据给清掉。还要加上清除控制符。

2022-04-19 15:55:04 +08:00

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

@binux "描述分析这个算法，你没能拿出 code ，也无法分析时空复杂度。"

我自己写代码分析了，每个 key 平均占用 5bit 就是分析结果。

代码也懒得贴，除了你们一小部分人相信外。大部分人都以为我是在吹牛。

2022-04-19 15:52:33 +08:00

回复了 3dwelcome 创建的主题 › 算法 › 构建一个完美无冲突的 hashmap。

@learningman 知道 GCC 这个编译软件吗？他就在用，github 镜像里你能搜到相关的完美哈希代码。

最常见场景，就是把已知一组字符串，映射成不重复的整型 ID 。类似 constexp ，编译器静态预处理字符串哈希，要比运行时动态处理哈希冲突，执行效率要高太多。

说工程上没有用，只不过你们平时写业务太多，没遇到罢了。

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

❮

❯