CRC-32 算不算一种哈希算法？

V2EX = way to explore

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

现在注册

已注册用户请登录

这是一个创建于 3841 天前的主题，其中的信息可能已经有所发展或是发生改变。

是不是任意大小的数据都可以通过CRC-32计算出一个32位的数据？

如果是这样的话那不就是弱版的MD5
为什么刚刚听老师说CRC-32不算一种哈希算法？

算法

哈希

27 条回复 • 1970-01-01 08:00:00 +08:00

timonwong

2014-04-24 16:24:12 +08:00

是

timothyqiu

2014-04-24 16:26:14 +08:00

哈希是把任意长度数据往固定长度数据上的一种映射。

所以 CRC-32 算哈希算法。

不过，理论上 return 0 也是一种哈希算法，只不过永远碰撞而已。

lococo

2014-04-24 16:30:21 +08:00

刚刚论文导师说我的论文太水，没看懂我的算法，把我骂一顿
第一句话就是说：
P14 crc-32 不是哈希函数！！

我还以为真是我错了 ``

nicai000

2014-04-24 16:33:03 +08:00

算, 你老师略弱. "弱版的MD5"这句话说得也略弱.

Keyes

2014-04-24 16:33:54 +08:00

CRC32是一个妥妥的标准哈希算法，整个CRC系列都是为这目的而诞生的，你导师如此卖萌……

Keyes

2014-04-24 16:35:06 +08:00

你可以去维基摘一些CRC的公式给他……

lococo

2014-04-24 16:50:22 +08:00

我刚刚把这个帖子的链接贴给导师了 ``
导师说我如果在论文里写CRC-32是一种哈希算法的话这点就通不过检查的

raptium

2014-04-24 16:51:14 +08:00

http://en.wikipedia.org/wiki/Cryptographic_hash_function
http://en.wikipedia.org/wiki/Hash_function

你导师把这两个搞混了
CRC32 是 Hash Function，不过对碰撞就没啥抵抗了

lococo

2014-04-24 16:51:20 +08:00

好伤心
那我还是把我论文里的所有这样写的语句改成
恩`` 循环冗余校验算法！！

raptium

2014-04-24 16:52:23 +08:00

事实上简单的 Hash Function 可以是 f(x) = x mod n
在写 hash map 的时候这样就够用了

xdeng

2014-04-24 16:57:04 +08:00

碰撞率比 MD5高吧？

lococo

2014-04-24 17:00:04 +08:00

@xdeng
对呀。。
所以我一直觉得CRC32就好像弱版的MD5

xdeng

2014-04-24 17:30:29 +08:00

@lococo CRC32 好像是追求的是速度

Keyes

2014-04-24 17:32:01 +08:00

@xdeng 这也是TCP用它做校验的原因

lococo

2014-04-24 17:34:24 +08:00

@xdeng
我的论文是研究大数据完整性验证的，需求就是想要提高验证的效率
最开始我想用bloom filter + MD5 实现，最后比较了一番
我才用的 hash set + crc-32 去实现

min

2014-04-24 17:43:21 +08:00

@lococo
你把这link发给你导师了？
还是不要费力搞什么论文了，研究一下换导师实在点儿 :)

Keyes

2014-04-24 17:43:26 +08:00

其实用于少量数据的完整性校验，并不需要MD5等算法上场

另外“碰撞”也只是f(data1) == f(data2)而已；

但如果是我有数据篡改的目的，那我的目的一定是：
要根据a1的数据进行篡改得到a2，且hash(a1)==hash(a2)，且a2要具有实际意义，要保持原有数据结构的长度限制；

反正我是做不到……要得出长度一样、哈希结果一样，但内容不一样的两组数据，我相信即使CRC32也没有那么容易就做出来的

半吊子一个……不知道各位能看懂不……求做算法的大神出面详解

min

2014-04-24 17:44:09 +08:00

验证效率方面，好像有些hash算法是针对性能优化的，可以找来参考参考

Keyes

2014-04-24 17:46:39 +08:00

@min 默默+1

nicai000

2014-04-24 17:46:47 +08:00

你竟然把这帖子发给导师, 也真够直的...

lococo

2014-04-24 17:50:21 +08:00

导师现在已经懒得理我了··

twor2

2014-04-24 18:11:50 +08:00

@lococo “导师现在已经懒得理我了·· ”

戳中笑点 233333

zinking

2014-04-24 18:18:20 +08:00

我觉得要看你讨论的上下文，如果上下文里哈希算法指的是用在Map之类数据结构上的话，我不觉得CRC是哈希算法。 CRC就是通常意义的校验算法而已。没必要把什么东西都往抽象高层发散。就像前面同学说的return 0还是哈希算法呢

quake0day

2014-04-24 22:50:20 +08:00

如果检查的人有机会听你辩驳的话你就这么写。如果你没机会申辩的话，那最好还是改成他们容易懂的表述。

lococo

2014-04-24 23:35:50 +08:00

@quake0day
嗯。。我觉得导师还是为我好。。
今天有点激动了。。

undeadking

2014-04-25 13:41:01 +08:00

hash算法和可用于加密学的安全hash算法是两回事,一般信息安全的课本都会有详细的定义说明啊

lococo

2014-04-25 15:05:05 +08:00 via iPhone

@undeadking
最开始导师给我问题背景假设的时候就在说用hash去确保原始数据完整性…