将非数字的用户ID映射到位图的方案探讨
一、背景
今天技术群里有同学提出想讲非数字的用户 ID 映射到位图中，计划采用 murmur 3 哈希算法，询问冲撞率是多少。 借着这个机会简单聊下非数字用户ID 如何更好地避免冲突，是否有更好的思路。
二、方案
2.1 将非数字的用户ID 映射成唯一的数字
2.1.1 直接转换：参考 Base 64 算法自定义转换函数
可以参考 base 64 算法 ，根据自己用户 ID 的的字符构成，改造 Base64 算法实现非数字的用户ID 到十进制数字的转换。
这样做可以避免引入哈希算法带来的哈希冲突问题，缺点是转换后的 用户 ID 普遍普遍偏大或偏小。
参考代码如下：
public class CustomBase64ToDecimal {
// 字符集
private static final String BASE_64_CHARS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_-"; // 自定义的64进制字符集
// 64进制的基数
private static final int BASE_64 = BASE_64_CHARS.length();
public static void main(String[] args) {
String base64String = "2Qhq"; // 自定义的64进制字符串
int decimal = customBase64ToDecimal(base64String); // 转换为十进制
System.out.println(decimal); // 输出十进制结果
}
// 自定义的 base 64 转十进制的算法
private static int customBase64ToDecimal(String base64String) {
int decimal = 0;
int power = 0;
for (int i = base64String.length() - 1; i >= 0; i--) {
char c = base64String.charAt(i);
int digit = BASE_64_CHARS.indexOf(c);
decimal += digit * Math.pow(BASE_64, power);
power++;
}
return decimal;
}
}2.1.2 间接“转换”：加中间层
俗话说：“计算机科学领域的任何问题，都是可以通过新增一个间接的中间层来解决的”。
我们可以为用户表新增一个数字的 ID，可以采用分布式 ID 生成器（分布式系统），将老数据生成一遍，新增用户表行时也调用该生成器写入数字的 ID，这样就不需要转换。 如用户表包含： userId （字符串类型）、userName、 email 等信息，我们可以新增一列叫 newUserId （长整形）。
只要分布式ID生成器本身是科学的，就可以避免用户 ID 都偏大或偏小，同时能够保证唯一性。 缺点是需要新增一列，需要刷老数据，新的数据需要写入该字段，但整体来说这并不是很大的问题。 我个人倾向于这种方案。
2.2 采用哈希算法
2.2.1 降低 Hash 冲突的概率：使用高位
采用任何 Hash 算法，理论上都会存在 哈希冲突，只是概率的大小的问题。 如果业务上容许，几十万，几百万分之，甚至上亿分之一的冲突概率，可以考虑使用 murmur 3 算法。 有文章显示，如果数据集完全随机，在特定实验中显示， Murmur3 的 64 位，哈希冲突的概率大约是 亿分之一的概率。如果不放心，可以考虑使用 Murmur3 128 位，冲突的概率更低。
Apache 的 commons-codec 类库的示例如下： maven 依赖：
<dependency>
<groupId>commons-codecgroupId>
<artifactId>commons-codecartifactId>
<version>1.15version>
dependency>参考代码：
public class Murmur3Demo {
public static void main(String[] args) {
// Create a byte array to hash
byte[] data = "Hello world".getBytes();
// Compute a 32-bit hash value
int hash32 = MurmurHash3.hash32x86(data);
System.out.println("32-bit hash: " + hash32);
// Compute a 64-bit hash value
long hash64 = MurmurHash3.hash64(data);
System.out.println("64-bit hash: " + hash64);
// Compute a 128-bit hash value as two long values
long[] hash128x64 = MurmurHash3.hash128x64(data);
System.out.println("128-bit hash: " + hash128x64[0] + ", " + hash128x64[1]);
}
}也可以使用 guava 的相关工具类。 maven 依赖：
<dependency>
<groupId>com.google.guavagroupId>
<artifactId>guavaartifactId>
<version>31.1-jreversion>
dependency>参考代码：
import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.nio.charset.StandardCharsets;
public class GuavaMurmurDemo {
public static void main(String[] args) {
// 创建一个128 位的murmur3哈希函数
HashFunction hashFunction = Hashing.murmur3_128();
// 计算字符串"Hello world"的哈希值
HashCode hashCode = hashFunction.hashString("Hello world", StandardCharsets.UTF_8);
// 打印哈希值 -769998839
System.out.println(hashCode.asInt());
}
}这里顺便聊一下 murmur3 的优缺点。 murmur3 有以下几个优点：
- 它是一种非加密型哈希函数，适用于一般的哈希检索操作。
- 它的随机分布性很好，能够有效地避免哈希碰撞。
- 它的计算速度很快，比MD5或SHA等加密型哈希函数要快得多。
- 它支持多种长度的输出，如32位、64位、128位等。
- 它的实现代码很简洁，易于移植和优化。
Murmur3 是一种非加密型哈希函数，适用于一般的哈希检索操作。它也有一些缺点，比如：
- 它不是加密安全的，也就是说它不能防止故意构造的碰撞或者逆向还原原始数据。
- 它对于哈希码的长度有限制，如果使用32位的哈希码，那么在插入大约7.2万个元素后，发生碰撞的概率就接近50%。如果使用 200 万个元素，那么几乎肯定会发生碰撞。
- 它对于规律性较强的 key 可能不太适合，因为它可能导致输出结果也具有规律性。
2.2.2 哈希冲突后解决办法
既然采用哈希算法，哈希冲突不可避免，那么我们可以采用其他办法解决哈希冲突。
哈希冲突是指两个或多个不同的输入值经过哈希函数后得到相同的输出值。哈希冲突是不可避免的，因为哈希函数的输出空间通常比输入空间小。因此，哈希表需要有一些处理冲突的机制，称为冲突解决方案。 常见的哈希冲突解决方案有以下几种:
- 开放寻址法：当发生冲突时，通过探测或搜索数组中的其他位置（探测序列），直到找到目标记录或一个未使用的数组槽为止。常用的探测序列包括线性探测、二次探测和双重散列等。
- 分离链接法：当发生冲突时，将具有相同哈希值的记录存储在一个链表中，每个数组槽指向一个链表头节点。这样可以避免移动记录，但需要额外的空间来存储链表节点。
- 概率性散列法：当发生冲突时，使用一个随机数生成器来选择一个新的哈希函数，并重复这个过程直到找到一个没有冲突的哈希函数为止。这种方法可以保证在期望意义上最小化冲突次数，但需要存储多个哈希函数，并且可能导致较长的查找时间。
- 完美散列法：当输入数据集是静态或已知的时候，可以使用一种特殊的算法来构造一个没有任何冲突的哈希函数。这种方法可以实现最优化的查找性能，但需要较高的计算和空间开销，并且对于动态变化的数据集不适用。
- 融合散列法：当发生冲突时，将具有相同哈希值的记录存储在另一个数组中，并将原始数组槽指向该数组中对应位置。这样可以减少额外空间消耗，并且保持了开放寻址法和分离链接法各自优点。
我们可以考虑参考上述的方案，对哈希的方案进行改造，解决哈希冲突带来的问题。 我们也可以将没有哈希冲突的情况下采用位图的方式，对于有哈希冲突的方式单独建表进行存储，由于冲突的概率极低，所以这些额外的存储量很少。
三、总结
只要思想不滑坡，办法总比困难多。在做技术方案遇到困难时，建议多发散思维寻找新的思路。
很多时候，并不存在完美的方案，通常各种方案各有利弊，需要我们在不同方案中去取舍。 在解决问题时，通常需要我们分情况进行讨论，需要将多种解决方案结合在一起使用。 如果你有更好的方案，也欢迎留言补充讨论。
腾讯云开发者
