今天技术群里有同学提出想讲非数字的用户 ID 映射到位图中,计划采用 murmur 3 哈希算法,询问冲撞率是多少。 借着这个机会简单聊下非数字用户ID 如何更好地避免冲突,是否有更好的思路。
可以参考 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;
}
}
俗话说:“计算机科学领域的任何问题,都是可以通过新增一个间接的中间层来解决的”。
我们可以为用户表新增一个数字的 ID,可以采用分布式 ID 生成器(分布式系统),将老数据生成一遍,新增用户表行时也调用该生成器写入数字的 ID,这样就不需要转换。 如用户表包含: userId (字符串类型)、userName、 email 等信息,我们可以新增一列叫 newUserId (长整形)。
只要分布式ID生成器本身是科学的,就可以避免用户 ID 都偏大或偏小,同时能够保证唯一性。 缺点是需要新增一列,需要刷老数据,新的数据需要写入该字段,但整体来说这并不是很大的问题。 我个人倾向于这种方案。
采用任何 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 有以下几个优点:
Murmur3 是一种非加密型哈希函数,适用于一般的哈希检索操作。它也有一些缺点,比如:
既然采用哈希算法,哈希冲突不可避免,那么我们可以采用其他办法解决哈希冲突。
哈希冲突是指两个或多个不同的输入值经过哈希函数后得到相同的输出值。哈希冲突是不可避免的,因为哈希函数的输出空间通常比输入空间小。因此,哈希表需要有一些处理冲突的机制,称为冲突解决方案。 常见的哈希冲突解决方案有以下几种:
我们可以考虑参考上述的方案,对哈希的方案进行改造,解决哈希冲突带来的问题。 我们也可以将没有哈希冲突的情况下采用位图的方式,对于有哈希冲突的方式单独建表进行存储,由于冲突的概率极低,所以这些额外的存储量很少。
只要思想不滑坡,办法总比困难多。在做技术方案遇到困难时,建议多发散思维寻找新的思路。
很多时候,并不存在完美的方案,通常各种方案各有利弊,需要我们在不同方案中去取舍。 在解决问题时,通常需要我们分情况进行讨论,需要将多种解决方案结合在一起使用。 如果你有更好的方案,也欢迎留言补充讨论。