【数据结构】如何给哈希集设计哈希算法

lichao · 发表于 2024-2-23 16:56:43

本帖最后由 lichao 于 2024-2-23 17:09 编辑

SHA1 不安全，不过关键是你说追求速度用 CRC，实际上 CRC 的速度比不过 SHA1，而 SHA 1 的速度比不过 MD5 ...

"实际上 CRC 的速度比不过 SHA1，而 SHA 1 的速度比不过 MD5，不信你可以自己测测试试。"
怎么得到这个速度结论的？我立马写了个脚本测了下，没复现。crc就是因为计算简单所以应用最广
https://stackoverflow.com/questions/996843/when-is-crc-more-appropriate-to-use-than-md5-sha1

import time, zlib, hashlib

def test_crc(s):
    ts1 = time.time()
    for i in range(1000): 
        zlib.crc32(s)
    ts2 = time.time()
    return ts2 - ts1

def test_sha1(s):
    ts1 = time.time()
    for i in range(1000): 
        hashlib.sha1(s).digest()
    ts2 = time.time()
    return ts2 - ts1

def test_md5(s):
    ts1 = time.time()
    for i in range(1000): 
        hashlib.md5(s).digest()
    ts2 = time.time()
    return ts2 - ts1

for i in range(3, 20):
    n = 2 ** i
    s = b"n" * n
    print(n, test_crc(s), test_sha1(s), test_md5(s))

8 0.0001647472381591797 0.001130819320678711 0.0018301010131835938
16 0.0001919269561767578 0.0010569095611572266 0.0010020732879638672
32 0.0002219676971435547 0.0010089874267578125 0.0010020732879638672
64 0.00029015541076660156 0.0010938644409179688 0.0010941028594970703
128 0.0002739429473876953 0.0011377334594726562 0.0011801719665527344
256 0.00033593177795410156 0.0012929439544677734 0.0014221668243408203
512 0.0004589557647705078 0.001560211181640625 0.0017600059509277344
1024 0.0006051063537597656 0.0020990371704101562 0.0025529861450195312
2048 0.0009191036224365234 0.003882884979248047 0.004523038864135742
4096 0.0015561580657958984 0.005532264709472656 0.0074920654296875
8192 0.002997159957885742 0.010485172271728516 0.014097929000854492
16384 0.005986928939819336 0.019515275955200195 0.026486873626708984
32768 0.010529756546020508 0.03759407997131348 0.05156302452087402
65536 0.020674943923950195 0.07198619842529297 0.10092425346374512
131072 0.0433049201965332 0.14149093627929688 0.19953060150146484
262144 0.08152174949645996 0.2673459053039551 0.3763251304626465
524288 0.16224002838134766 0.5112760066986084 0.784217119216919

如果你用c++玩hash的话有没有试过自带的std::hash，没看到你提这个

lichao · 发表于 2024-2-23 17:31:28

AyalaRs 发表于 2024-2-22 10:56
校验和算hash算法么，如果按分布要求可能不算，校验和，移位校验和，补位校验和，这些的分布都不算好 ...

实际App没有用CRC的，我自己会用，因为我用的场景很适合，太复杂了会有特征反而弄巧成拙。

0xAA55 · 发表于 2024-2-26 09:28:59

lichao 发表于 2024-2-23 16:56
[md]
"实际上 CRC 的速度比不过 SHA1，而 SHA 1 的速度比不过 MD5，不信你可以自己测测试试。"
怎么得到 ...

CRC 每次计算都只输入一个 byte，这是它慢的原因。估计用 Python 测不出来。

std::hash 很常用，但对于自己设计的类，有很多时候都不好用。

lichao · 发表于 2024-2-26 12:36:50

本帖最后由 lichao 于 2024-2-26 13:01 编辑

0xAA55 发表于 2024-2-26 09:28
CRC 每次计算都只输入一个 byte，这是它慢的原因。估计用 Python 测不出来。

std::hash 很常用，但对于 ...

用不用Python不是关键，python只是调用下底层c/c++/asm写的库而已，没人用python直接做这种底层计算的。
主要在于写函数的人是否高效，我脚本里用的都是用的最广泛的库了，所以基本可以排除因为个人技术水平导致算法效率低的问题。
因为上述程序已经测试了速度 crc>sha1>md5，如果你要证明crc比sha1/md5慢，你就得实现比hashlib更快的sha1/md5.
hashlib是python自带库，底层的算法代码应该是早在python没出来之前就有了，很多高手花费几十年时间去维护的，你想实现的比它快恐怕没那么容易吧。

另外其实sha1的安全性问题，App里更安全的做法会用2层sha1/md5混合，这种在银行app比较多见。对于实际攻击场景来说，哈希并没有加解密重要，哈希是加解密的增强，用来验证篡改的，但是加解密被破了那就跟皇帝的新衣一样了，直接搞成协议app完全没法限制。有的银行更喜欢用国密/3DES算法

0xAA55 · 发表于 2024-2-26 16:05:13

lichao 发表于 2024-2-26 12:36
用不用Python不是关键，python只是调用下底层c/c++/asm写的库而已，没人用python直接做这种底层计算的。
...

排除不了 CPU 本身架构对哈希算法效率的影响，我得出 CRC 比 SHA1 慢的这个结论的时候还很早。现在的 CPU 架构已经是今非昔比了，所以还是以现在测出来的效果为准。

另外，应用广泛的东西未必就可靠，比如：
1. gcc 4.8 应用广泛，因为 CentOS 7、8 在国内应用广泛，而 CentOS 7、8 自带的 gcc 就是 4.8 这个版本。gcc 4.8 缺个头文件 stdatomic.h。
2. gcc 9 的某个版本不能正确处理 C 语言同一个 static 函数/变量在多个编译单元的符号冲突问题（因为那个版本的 gcc 9 使用了无脑的方式实现了 -flto 优化）（注：具体版本是我在尝试给 F1C100s 编译系统库的时候，被荔枝派官方教程要求使用的 gcc 版本）
以下为帖子内容屏幕截图

有图为证

以下略。

3. musl 库：STM32CubeIDE 的 gcc 使用的 musl 库自带的 memcpy() 是一个使用 for 循环按字节拷贝数据的函数（会导致 STM32 机器在拷贝内存的时候需要大量的位运算导致效率奇低）。当你想要为了优化这个东西，自己写一个使用 for 循环按 int 拷贝内存的代码的时候（理论上做好内存对齐拷贝就可以三条指令拷贝一个 int 而无需位运算），gcc 的 -fno-tree-loop-distribute-patterns 优化机制会检测到你的代码的 for 循环内存拷贝行为然后将你的代码替换为它的 musl 库的 memcpy() 实现从而还是走了按字节拷贝内存的老路。
4. zlib 库的 crc32 表的初始化函数使用一个 volatile 变量而非 atomic 变量来避免多线程重复初始化 crc32 表（会因为编译器的指令排序优化过程导致这个 volatile 变量的读写判定内存顺序错误从而导致 CRC32 表有一定概率被重复初始化），虽然作者在注释里说了“我不懂多线程那一套”（我不知道现在这个问题修复了没有）
5. zstd 库，号称比 zlib 库快很多倍，由 facebook 开发，实际使用时在多线程环境里不管你怎么上锁/使用TLS/避开多个线程同时使用这个库等，一定会在运行一段时间后崩溃。

我就不提多年前我修了个 Python 的 http 库的 bug 了（可惜合并失败了）

很多高手花费几十年时间去维护的，你想实现的比它快恐怕没那么容易吧。

你这句话可以翻译为「人家美少女拉的屎，怎么说也比你的屎好闻吧！」

misakarinkon · 发表于 2024-2-26 16:44:51

lichao 发表于 2024-2-26 12:36
用不用Python不是关键，python只是调用下底层c/c++/asm写的库而已，没人用python直接做这种底层计算的。
...

用的广和写的早，生命周期长，跟它快不快没什么关系吧

0xAA55 · 发表于 2024-2-26 16:48:25

misakarinkon 发表于 2024-2-26 16:44
用的广和写的早，生命周期长，跟它快不快没什么关系吧

不同用途和不同思路写出来的同一个算法实现，由于考虑的因素不同，不能单纯因为它经过了多年的维护而认定它“性能一定是最佳的”。

lichao · 发表于 2024-2-26 16:58:03

本帖最后由 lichao 于 2024-2-26 17:38 编辑

0xAA55 发表于 2024-2-26 16:05
排除不了 CPU 本身架构对哈希算法效率的影响，我得出 CRC 比 SHA1 慢的这个结论的时候还很早。现在的 CPU ...

的确世上不存在100%的概率，用的多库的确实也不可能100%可靠，不过从概率上还是比用的少的库好点，这些都是动态的，主要看多少人用了多少时间检验。一堆密码学专业人士花那么多年时间维护的算法，我想总比普通人随手写的要好吧？至于架构方面，因为我环境有限无法给出所有架构的测试，不过你是可以测的啊，如果有不同的结论我也都接受，一切以事实为基础，有结论了别忘告诉我。

还有你举的例子过于偏颇，python和gcc都是很复杂的项目，其中某些小功能可能未必经过很多人测试，其实有bug是可以理解的，他们每版不知道得改多少bug呢。一个算法显然不能和这么大的项目相提并论，显而易见对吗？

zlib/zstd，至于这两个库的bug，有没有按照规范去开发呢，第三方已经在用这俩库的软件是如何保证正确性和多线程没问题的，别人是怎么解决的？你不会告诉我因为有bug导致没人用的吧？

lichao · 发表于 2024-2-26 17:03:23

本帖最后由 lichao 于 2024-2-26 17:10 编辑

misakarinkon 发表于 2024-2-26 16:44
用的广和写的早，生命周期长，跟它快不快没什么关系吧

对普通人来讲，还是有关吧。事实上你可以用另一个权威的库来证明CRC确实比SHA1慢，但是转移问题就纯粹是小孩子嘴仗了。

0xAA55 · 发表于 2024-2-27 14:27:57

lichao 发表于 2024-2-26 16:58
的确世上不存在100%的概率，用的多库的确实也不可能100%可靠，不过从概率上还是比用的少的库好点，这些都 ...

结论不就是 CRC32 在我们这的服务器上比 SHA1 慢，SHA1 比 MD5 慢么？运行环境曙光X640 服务器，Ubuntu 最新版系统，使用语言 JDK8（项目要求），以 Docker 容器方式部署，我们公司的架构师在测试数据库性能的时候发现的。

我举得例子里 gcc 那几个 bug 你不觉得严重么？你到底用过几次 gcc 哦？这么出名的大项目能有这么严重的 bug，那么一个算法也可能隐藏着重大 bug 也是有可能的吧？

zlib/zstd 你真的就确定第三方在使用这俩库的时候就已经保证了正确性和多线程没问题的呢？另外你有没有想过有一种可能：facebook 的服务器是 *nix 服务器，而 *nix 的传统，就是喜欢使用 *进程池* （*nix 是不区分进程和线程的，此处的“进程”指的是内存空间不共享的进程），而使用 *进程池* 就会避开它的多线程问题，再加上很少有人在 Windows 上使用 zstd，所以它被“你的第三方”认定是没有 bug 的了。

的确世上不存在100%的概率，用的多库的确实也不可能100%可靠

开源社区讲究的就是谁发现 bug，谁修复 bug，开源算法也一样。有的人喜欢参与推进开源项目，贡献代码修补错误或者增加新的功能，有的人则是拿来主义，而且基本上商业开发者在使用开源项目的产品的时候都是拿来主义，因为你在混工作的时候，其实你只会想给你的老板交差，除非在此之上你还有余力去参与开源项目的推进，否则只要能编译通过、通过代码审计、要不就再来个 code linting 审查。只要你的老板发现不了 bug，只要你的服务能顺利上线，甚至某些公司的服务以不合规的方式上线，只要你的老板满意，你就不会再做其它的多余的事情。否则要是被老板发现你工作强度不饱和，你会遇到职场问题。

而参与开源项目/开源算法的人的能力水平参差不齐，有工作了很多年的程序员，有业余爱好者，有还没毕业的大学生，甚至还有众多初中生、高中生甚至小学生，有的甚至连基本的计算机编程能力都没有，但是却喜欢~~瞎几把~~微调各种参数配置。越是用得广泛的开源项目，想要往里面拉屎的人就越多。不能迷信开源大法，也不能迷信“维护得久的算法”，因为对于一个算法/软件库的开发者而言，鬼知道你家公司生产环境会使用哪个版本的算法实现，以及你的生产环境机器是什么样的架构。

usr · 发表于 2024-2-27 15:54:03

想要往里面拉屎的人就越多。

Linux呢?你的屎也得能拉進去吧？

0xAA55 · 发表于 2024-2-27 16:05:54

usr 发表于 2024-2-27 15:54
Linux呢?你的屎也得能拉進去吧？

直接往里面拉屎确实不太容易拉得进去，但往它的衍生物里拉屎则是开源嵌入式开发社区现状。很多嵌入式板子的 bootloader 是通过精简 Linux 内核源码，或者模仿 Linux 内核的组织结构，或者参照古早时期 Linux 还很简单的时候的代码进行研发的。尤其是很多国产嵌入式板子（比如荔枝派）的开发需要你自己编译其 Linux 系统，然后你会发现这些嵌入式板子的 Linux 系统的外设驱动就是专门针对这个板子（以及开发人员在当时使用的最新的 gcc 版本）开发的。参照它的外设驱动源码，你可以看到这些驱动大致是如何驱动嵌入式芯片外设的，于是便可以脱离它的 Linux 系统，自己进行裸金属开发（只要你有相当充裕的闲暇时间）。

有的古早时期火极一时的嵌入式板子到现在还在淘宝有人售卖，但是你要编译它的 Linux 系统，你可能需要一台 2015 年的二手笔记本电脑，装个 2015 年的 Ubuntu，以及对应的 2015 年的 Ubuntu 的针对这个 2015 年笔记本电脑的 2015 年版 USB 驱动，然后确保你配置好了 2015 年的 gcc 工具链，再通过 2015 年的 ed2k 链接来下载源码，然后编译源码，你才能把它玩起来。否则你只能找客服要一些 Demo Image，使用 2015 年的 USB 下载器来观赏一个 2015 年的跑马灯程序。

usr · 发表于 2024-2-27 16:38:30

跑題le跑題le 本文討論的是散列算法

CRC不是專門的散列算法吧?

0xAA55 · 发表于 2024-2-27 16:46:28

usr 发表于 2024-2-27 16:38
跑題le跑題le 本文討論的是散列算法
CRC不是專門的散列算法吧?

确实。

但是因为它可以被当作 hash function 来用，我就把它归类为“哈希算法”了哈哈哈哈哈哈

账号		自动登录	找回密码
密码			立即注册→加入我们