字符串映射成数字，有什么好的算法嘛

[leebs]

用 bitmap 存储数据，需要对数据做 offset 映射，有什么好的算法嘛。

[kilasuelika]

啥叫 offset 映射

[liprais]

murmurhash3

[CEBBCAT]

你……是要做布隆过滤器吗？

[murmur]

offset 映射是啥意思，记住用户看书看到的地方？

[dangyuluo]

atoi 还需要算法么？

https://leetcode.com/problems/string-to-integer-atoi/

[leebs]

@kilasuelika offset 是偏移量，bitmap 里面的概念，相当于数组下标。

[leebs]

@dangyuluo 任意字符串，不是数字字符串，需要编码成数字。

[dangyuluo]

那就 md5 然后取前 64bit 做 uint64_t?

[gwbw]

参考 base64 的算法，映射成 base10 ，用 0~9 表示，这种么；要求纯数字的话可能要 base9 ，留一个数字专门补位

[Yi23]

如果单纯的字符串转数字的话，是否可以考虑 36 进制（ 26 个英文+10 个数字）转换？但这样子可能会导致转出来的数字会非常大

[hu8245]

面腾讯就问的这个，蹲一个方案💬

[X0ray]

这？直接 hash 不行吗

[also24]

直觉上是一个 X-Y Problem

如果是构建布隆过滤器的话，那二进制数据无需转换，直接就能塞进 bitmap ，不需要特殊处理。


如果是想用 bitmap 的下标来表示一个数据的话，那除非特定场景，效率是极低的，基本不存在实际的可行性，用下来还不如直接 hashmap 好用。

[labulaka521]

@also24 我也觉得是
前提： https://v2ex.com/t/838798#reply14

[zhongchaowade]

所以需要同时支持正负数，8 ，10 ，16 进制吗？

[lniwn]

难道在说 ascii 码？

[EminemW]

hash 然后 mod ？

[WhereverYouGo]

md5? sha256?

[3dwelcome]

有个叫 perfect hash 的算法，可以满足楼主的需求。

举个例子，有 10 万个字符串需要查重，那么在 redis 里创建一个大小为 10 万的 bitmap 数据结构，用 0 和 1 来表示，当前字符串是否已被占用。

先对 10 万个字符串做预处理，便可以得到一个不冲突，又刚好完美 1:1 匹配进 bitmap ，自定义 hash 映射表。

[littlewing]

楼上说 hash 的，冲突怎么解决？

[3dwelcome]

@littlewing “楼上说 hash 的，冲突怎么解决？”

完美 hash 没冲突。否则就不叫完美了。