这是一个创建于 998 天前的主题，其中的信息可能已经有所发展或是发生改变。
用 bitmap 存储数据，需要对数据做 offset 映射，有什么好的算法嘛。
 |
1
kilasuelika 2022-03-09 00:15:01 +08:00 via Android  1
啥叫 offset 映射
|
 |
2
liprais 2022-03-09 00:19:51 +08:00
murmurhash3
|
 |
3
CEBBCAT 2022-03-09 03:04:30 +08:00 via iPhone
你……是要做布隆过滤器吗？
|
 |
4
murmur 2022-03-09 08:34:31 +08:00
offset 映射是啥意思，记住用户看书看到的地方？
|
 |
5
dangyuluo 2022-03-09 08:55:03 +08:00
|
 |
6
leebs OP @kilasuelika offset 是偏移量，bitmap 里面的概念，相当于数组下标。
|
|
8
dangyuluo 2022-03-09 09:15:04 +08:00
那就 md5 然后取前 64bit 做 uint64_t?
|
 |
9
gwbw 2022-03-09 09:46:01 +08:00
参考 base64 的算法，映射成 base10 ，用 0~9 表示，这种么；要求纯数字的话可能要 base9 ，留一个数字专门补位
|
 |
10
Yi23 2022-03-09 09:49:48 +08:00
如果单纯的字符串转数字的话，是否可以考虑 36 进制（ 26 个英文+10 个数字）转换？但这样子可能会导致转出来的数字会非常大
|
 |
11
hu8245 2022-03-09 09:51:10 +08:00 via Android
面腾讯就问的这个，蹲一个方案💬
|
 |
12
X0ray 2022-03-09 09:53:51 +08:00
这？直接 hash 不行吗
|
 |
13
also24 2022-03-09 09:56:45 +08:00 1
直觉上是一个 X-Y Problem
如果是构建布隆过滤器的话，那二进制数据无需转换，直接就能塞进 bitmap ，不需要特殊处理。 如果是想用 bitmap 的下标来表示一个数据的话，那除非特定场景，效率是极低的，基本不存在实际的可行性，用下来还不如直接 hashmap 好用。 |
 |
14
labulaka521 2022-03-09 10:06:09 +08:00 via iPhone 1
|
 |
15
zhongchaowade 2022-03-09 11:45:34 +08:00
所以需要同时支持正负数，8 ，10 ，16 进制吗？
|
 |
16
lniwn 2022-03-09 13:14:04 +08:00 via iPhone
难道在说 ascii 码？
|
 |
17
EminemW 2022-03-09 14:15:42 +08:00
hash 然后 mod ？
|
 |
18
WhereverYouGo 2022-03-09 14:22:06 +08:00
md5? sha256?
|
 |
19
3dwelcome 2022-03-09 14:33:32 +08:00
有个叫 perfect hash 的算法，可以满足楼主的需求。
举个例子，有 10 万个字符串需要查重，那么在 redis 里创建一个大小为 10 万的 bitmap 数据结构，用 0 和 1 来表示，当前字符串是否已被占用。 先对 10 万个字符串做预处理，便可以得到一个不冲突，又刚好完美 1:1 匹配进 bitmap ，自定义 hash 映射表。 |
 |
20
littlewing 2022-03-09 14:37:27 +08:00
楼上说 hash 的，冲突怎么解决？
|
|
21
3dwelcome 2022-03-09 15:30:54 +08:00
|
Select Language