0

我想实现一种散列技术，C其中字符串的所有排列都具有相同的散列键。
例如abc&cab两者都应该有相同的键。

我曾考虑添加ascii值然后检查frequency of characters[重要否则两者abc&aad将具有我们不想要的相同键]。
但是，它似乎效率不高。

有没有更好的散列函数可以很好地解决冲突并且也不会导致稀疏散列表？

Java [ ] 内部使用了哪种散列技术for strings，不仅可以最大限度地减少冲突，而且操作 [ insertion ,deletion, search] 足够快？

4

4 回答 4

12

为什么不在散列之前对字符串的字符进行排序？

于 2012-06-24T14:35:38.070 回答
4

显而易见的技术是简单地对字符串进行排序。您可以简单地将排序后的字符串用作查找键，也可以使用任何认为合适的算法对其进行散列。或者，您可以使用字符串的游程编码 (RLE) 表示形式（因此 RLE 为banana）a3bn2，并可选择对其进行散列。

很大程度上取决于您要对散列做什么，以及它们对冲突的抵抗力。一个简单的 CRC（循环冗余校验和）可能就足够了，或者可能是 MD5 或 SHA1 等加密校验和对您来说不够安全。

于 2012-06-24T14:41:48.427 回答
2

Java [用于字符串] 内部使用了哪种散列技术，它不仅可以最大限度地减少冲突，而且操作 [插入、删除、搜索] 是否足够快？

Java 中用于提高速度的基本“技巧”是缓存哈希值，使其成为 a 的成员变量，String因此您只需计算一次。但是这只能在 Java 中工作，因为字符串是不可变的。

于 2012-06-24T14:40:18.097 回答
1

关于散列的主要规则是“不要发明自己的散列算法。永远。”。您可以只对字符串中的字符进行排序并应用标准散列策略。

如果您对散列感兴趣，还请阅读。

于 2012-06-24T14:49:00.137 回答