首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
nyse
V2EX  ›  算法

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

  •  
  •   nyse · 59 天前 · 1880 次点击
    这是一个创建于 59 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    注:

    1. 之所以要这样缩短的主要原因是为了减少数据库空间占用;

    2. 这个算法最好是使用的比较广泛的,因为这个需求自己写一个程序映射应该也可以,但还是希望能找到一个更加广泛通用的解决方案;

    3. 这个算法要能互逆

    28 回复  |  直到 2019-11-24 22:59:59 +08:00
    also24
        1
    also24   59 天前 via Android   ♥ 1
    这个不需要算法,进制换算就够了
    also24
        2
    also24   59 天前 via Android
    或者这样说,你对 md5 的输出有误解

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

    你完全可以直接存储这 128bit 以达到最小化空间占用
    NeinChn
        3
    NeinChn   59 天前
    MD5/SHA1 能互逆?
    ipwx
        4
    ipwx   59 天前 via Android
    你可以用 binary type 存。但如果这你还不满足,那没有办法了
    ipwx
        5
    ipwx   59 天前 via Android
    事实上每两位 hex 等于一位二进制八位
    nyse
        6
    nyse   59 天前
    @NeinChn #3 不是 MD5/SHA1 互逆
    nyse
        7
    nyse   59 天前
    @also24 #2
    @ipwx #5

    由于可能用来查询,所以不太适合直接存二进制,我就在想有没有办法转成另外一种字符串
    ahhui
        8
    ahhui   59 天前 via iPhone
    把二进制 binary 用 base64 encode 一下就行了
    ipwx
        9
    ipwx   59 天前 via Android
    @nyse 二进制为啥不能查
    hdbzsgm
        10
    hdbzsgm   59 天前
    @ahhui #8 你确定 base64 是压缩吗
    also24
        11
    also24   59 天前
    @nyse #7
    我不清楚你的查询指的是在什么体系内进行查询,至少 mysql 是支持 binary 查询的。

    如果你一定要把它变成 『可见字符』,那就如 8 楼所说,base64 吧
    woodensail
        12
    woodensail   59 天前
    base64 了解一下,一个字节能存 6bit,24 个字符搞定
    或者不要求可读性,直接存字节数组,16 个字节搞定
    unixeno
        13
    unixeno   59 天前 via Android
    @hdbzsgm 对比 base16 来说确实是压缩
    ipwx
        14
    ipwx   59 天前 via Android
    @also24 可见字符前端就行了吧,后台查询要什么可见
    passerbytiny
        15
    passerbytiny   59 天前
    你经常看到的 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
        16
    geelaw   59 天前 via iPhone
    int128 咯
    passerbytiny
        17
    passerbytiny   59 天前
    @nyse #7 通用方法,也就 hex dump ( 16 → 32 )和 base64 encode ( 16 →24 )了,再短就要自创方法了。
    also24
        18
    also24   59 天前
    @hdbzsgm #10
    对于楼主的语境来说是

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

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


    172bit < 256bit,所以对于楼主来说,数据确实被 『压缩』了
    also24
        19
    also24   59 天前
    @ipwx #14
    emmm…… 你是不是回复错人了?
    also24
        20
    also24   59 天前
    @hdbzsgm #10
    修正一下计算方式,应该是
    128 / 8 = 16byte
    ( 16 + 2 ) / 3 * 4 = 24byte
    补两个 == 之后 24 + 2 = 26byte
    26 * 8 = 208 bit

    208bit < 256bit
    wlh233
        21
    wlh233   59 天前
    @also24 虽然结论是对的,你这两次都没算对啊,不用 +2 了,已经补过了,就是 24
    xmadi
        22
    xmadi   59 天前 via iPhone
    使用 36 进制(0-9,a-z,不区分大小写) 或者 base64 如果觉得 base64 的两个符号太麻烦 可以使用 base62 ( 0-9,a-z,A-Z ) 就是楼主想要的东西
    imn1
        23
    imn1   59 天前
    难道是彩虹表?
    keepeye
        24
    keepeye   59 天前
    import string
    digs = string.digits + string.ascii_letters + '[email protected]#$%^&*()_+:;<>,.?/[]{}'
    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
        25
    lululau   59 天前 via iPhone
    @hdbzsgm 你确定明白楼主说的问题?
    also24
        26
    also24   59 天前
    @wlh233 #21
    前面补的两个 0 字节是为了凑够 3 的倍数
    后面补的两个等号是代表前面补了两个字节
    wlh233
        27
    wlh233   58 天前
    @also24 https://tools.ietf.org/html/rfc3548#section-7 所以多算了啊,补齐之后没用上的零比特最后变成等号了,总字节数就是这么多了,不用再加了
    also24
        28
    also24   58 天前
    @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 』 替换而来,而不是直接补上。

    感谢指正
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2572 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 29ms · UTC 04:00 · PVG 12:00 · LAX 20:00 · JFK 23:00
    ♥ Do have faith in what you're doing.