有没有什么广泛使用的算法将 16 进制数据缩短（用于压缩哈希值）？

V2EX = way to explore

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

现在注册

已注册用户请登录

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

需求是这样的，有个数据表，存放大量哈希值。

无论是 md5 还是 sha1 的长度都比较长，而且他们的取值范围都是 16 进制数（ 0-9，a-f ）

有没有什么广泛使用的算法，用（ 0-9，a-z，A-Z ）来表示他们，从而缩短他们的长度。

注：

之所以要这样缩短的主要原因是为了减少数据库空间占用；
这个算法最好是使用的比较广泛的，因为这个需求自己写一个程序映射应该也可以，但还是希望能找到一个更加广泛通用的解决方案；
这个算法要能互逆

算法

哈希值

a-z

缩短

28 条回复 • 2019-11-24 22:59:59 +08:00

also24

2019-11-23 14:44:37 +08:00 via Android

这个不需要算法，进制换算就够了

also24

2019-11-23 14:47:46 +08:00 via Android

或者这样说，你对 md5 的输出有误解

md5 输出的是 128bit，只是为了方便你看，才展示为 32 位 HEX String

你完全可以直接存储这 128bit 以达到最小化空间占用

NeinChn

2019-11-23 15:02:59 +08:00

MD5/SHA1 能互逆？

ipwx

2019-11-23 15:03:59 +08:00 via Android

你可以用 binary type 存。但如果这你还不满足，那没有办法了

ipwx

2019-11-23 15:05:01 +08:00 via Android

事实上每两位 hex 等于一位二进制八位

nyse

2019-11-23 15:05:15 +08:00

@NeinChn #3 不是 MD5/SHA1 互逆

nyse

2019-11-23 15:08:45 +08:00

@also24 #2
@ipwx #5

由于可能用来查询，所以不太适合直接存二进制，我就在想有没有办法转成另外一种字符串

0TSH60F7J2rVkg8t

2019-11-23 15:12:35 +08:00 via iPhone

把二进制 binary 用 base64 encode 一下就行了

ipwx

2019-11-23 15:14:14 +08:00 via Android

@nyse 二进制为啥不能查

hdbzsgm

2019-11-23 15:16:27 +08:00

@ahhui #8 你确定 base64 是压缩吗

also24

2019-11-23 15:18:48 +08:00

@nyse #7
我不清楚你的查询指的是在什么体系内进行查询，至少 mysql 是支持 binary 查询的。

如果你一定要把它变成『可见字符』，那就如 8 楼所说，base64 吧

woodensail

2019-11-23 15:19:05 +08:00

base64 了解一下，一个字节能存 6bit，24 个字符搞定
或者不要求可读性，直接存字节数组，16 个字节搞定

unixeno

2019-11-23 15:19:18 +08:00 via Android

@hdbzsgm 对比 base16 来说确实是压缩

ipwx

2019-11-23 15:19:47 +08:00 via Android

@also24 可见字符前端就行了吧，后台查询要什么可见

passerbytiny

2019-11-23 15:19:55 +08:00

你经常看到的 Md5/SHA1/UUID 等，并不是 16 进制数据，他的标准叫法是十六进制转储 /Hex dump （ https://zh.wikipedia.org/wiki/%E5%8D%81%E5%85%AD%E8%BF%9B%E5%88%B6%E8%BD%AC%E5%82%A8 ）。本质上，是处于可视化的目的，将二进制数据以十六进制数据（字符串形式）打印出来。

虽然你看到的是十六进制，但存储的不一定是。如果存储原始数据，那么是二进制数据；如果存储你看到的十六进制字符串，那么仍然是二进制数据，只不过是经过转码后的二进制数据，长度是原始二进制数据的两倍。所以，你只需要把存储格式，从字符串格式，改成原始二进制格式，就会压缩一半的存储空间。

geelaw

2019-11-23 15:22:02 +08:00 via iPhone

int128 咯

passerbytiny

2019-11-23 15:24:57 +08:00

@nyse #7 通用方法，也就 hex dump （ 16 → 32 ）和 base64 encode （ 16 →24 ）了，再短就要自创方法了。

also24

2019-11-23 15:25:03 +08:00

@hdbzsgm #10
对于楼主的语境来说是

原始数据是 128bit
楼主当前使用的方式（ HEX string ）是 32byte -> 256bit

而 128bit 数据在 base64 之后得到的字符串是 129/3*4 = 172 bit

172bit < 256bit，所以对于楼主来说，数据确实被『压缩』了

also24

2019-11-23 15:25:53 +08:00

@ipwx #14
emmm…… 你是不是回复错人了？

also24

2019-11-23 16:00:02 +08:00

@hdbzsgm #10
修正一下计算方式，应该是
128 / 8 = 16byte
( 16 + 2 ) / 3 * 4 = 24byte
补两个 == 之后 24 + 2 = 26byte
26 * 8 = 208 bit

208bit < 256bit

wlh233

2019-11-23 17:53:11 +08:00

@also24 虽然结论是对的，你这两次都没算对啊，不用 +2 了，已经补过了，就是 24

xmadi

2019-11-23 18:01:36 +08:00 via iPhone

使用 36 进制(0-9，a-z，不区分大小写）或者 base64 如果觉得 base64 的两个符号太麻烦可以使用 base62 （ 0-9，a-z，A-Z ）就是楼主想要的东西

imn1

2019-11-23 18:08:53 +08:00

难道是彩虹表？

keepeye

2019-11-23 18:13:44 +08:00

import string
digs = string.digits + string.ascii_letters + '!@#$%^&*()_+:;<>,.?/[]{}'
def int2base(x, base):
if x < 0:
sign = -1
elif x == 0:
return digs[0]
else:
sign = 1

x *= sign
digits = []

while x:
digits.append(digs[int(x % base)])
x = int(x / base)

if sign < 0:
digits.append('-')

digits.reverse()

return ''.join(digits)

def main():
src = b'test'
e = hashlib.md5(src).digest()
a1 = struct.unpack('q', a[0:8])
a2 = struct.unpack('q', a[8:])
print(int2base(a1[0], 86) + int2base(a2[0], 86)) # 最终输出 20 个字符

lululau

2019-11-23 18:47:58 +08:00 via iPhone

@hdbzsgm 你确定明白楼主说的问题？

also24

2019-11-23 23:01:52 +08:00

@wlh233 #21
前面补的两个 0 字节是为了凑够 3 的倍数
后面补的两个等号是代表前面补了两个字节

wlh233

2019-11-24 12:58:07 +08:00

@also24 https://tools.ietf.org/html/rfc3548#section-7 所以多算了啊，补齐之后没用上的零比特最后变成等号了，总字节数就是这么多了，不用再加了

also24

2019-11-24 22:59:59 +08:00

@wlh233 #27
确实我的错，我把两种思路混合理解了。

思路一：
先补 4 bit 『 0000 』，再补 2 byte 『==』，这种情况下是
(128+4) / 3 * 4 = 176bit
176 + 2*8 =192bit

思路二：
先补 16 bit 『 0000 000000 000000 』，转换出来末尾多了『 AA 』，替换为『==』，这种情况下是
(128+16) /3 * 4 = 192bit
192 - 2*8 + 2*8 = 192bit

我忽略了『==』是由『 AA 』替换而来，而不是直接补上。

感谢指正