一个双向字符串哈希函数

Question

我想得到一个字符串的唯一数字表示。我知道有很多方法可以做到这一点，我的问题是你认为哪种方法最好？我不想得到负数 - 所以Java中的hashcode()函数并不是很好，尽管我可以覆盖它...但我宁愿不这样做，因为我没有那么自信，不想无意中破坏某些东西。

我的所有字符串都是语义Web URIS。数字表示的原因是当我在页面上显示一个URI的数据时，我需要传递一些内容到查询字符串或将其放入我的JavaScript中的各个字段中。URI本身太笨重了，当您将URI作为URI值显示时会看起来很糟糕。

基本上，我想要一个称为Resource的类，它将像这样：

Resource{
  int id;
  String uri;
  String value; // this is the label or human readable name

  // .... other code/getters/setters here

  public int getId(){
    return id = stringToIntFunction();
  }

  private int stringToIntFunction(String uri){
  // do magic here
  }
}

如果要求：

1. 必须是双向的，也就是说，你可以从数字值中恢复原始字符串
2. 不需要是双向的

此外，还有其他重要的问题我没有考虑吗？

- Ankur

---

“双向哈希函数”是加密吗？ - Martijn Courteaux

Answer 1

如果你想让哈希可逆，那就有麻烦了。哈希函数被设计成单向的。特别地，考虑到一个整数具有32位信息量，而一个字符只有16位信息量，要求可逆性意味着你只能拥有零个、一个或两个字符的字符串（即使这还假设你愿意将""编码为"\0\0"或类似的形式）。当然，这是在不使用任何存储空间的情况下。如果你可以使用存储空间，那么只需要按顺序存储数字...类似于：

private int stringToIntFunction(String uri) {
    Integer existingId = storage.get(uri);
    if (existingId != null) {
        return existingId.intValue();
    }
    return storage.put(uri);
}

在这里，storage.put() 会在内部增加一个计数器，将URI与该计数器值关联起来并返回它。不过我猜想这可能不是你的需求。

基本上，要执行可逆加密，我会先将字符串转换为二进制格式（例如使用UTF-8），然后使用标准加密库进行加密。我期望结果是一个 byte[]。

如果不需要可逆性，我会考虑直接取常规 hashCode() 结果的绝对值（但将 Integer.MIN_VALUE 映射到特定的值，因为它的绝对值不能表示为一个 int）。

- Jon Skeet

---

谢谢Jon，我可能得选择你的第二个建议。不过我不确定你所说的“将Integer.MIN_VALUE映射到特定内容，因为它的绝对值无法表示为int”的意思是什么。 - Ankur

不用担心回答这个问题，对于单向情况，有很多相关资料（在SO上也有）。 - Ankur

@Ankur：Integer.MIN_VALUE的绝对值是2,147,483,648。然而，一个整数能表示的最大正数是2,147,483,647。因此，你必须确保不要在Integer.MIN_VALUE上调用Math.abs，而是以不同的方式处理它。 - Michael Stum

是的，理想情况下我不想查找全局ID存储。使用加密算法似乎是有意义的。 - Ankur

@Ankur：但你最初的问题是URI太长了，对吧？加密对此没有帮助。 - Jon Skeet

而且URI可能太小了，无法进行压缩...我会继续思考。 - Ankur

Answer 2

哈希是单向的（这就是它们具有固定长度的部分原因，无论输入的大小如何）。如果你需要双向的，你可以考虑使用类似于Base64编码的东西。

为什么不能有负数？URI从哪里来？它们在数据库中吗？为什么不使用数据库键ID？如果它们不在数据库中，是否可以根据一组变量/参数为用户生成它们？（因此查询字符串仅包含诸如foo = 1＆amp;bar = two之类的内容，并且您在服务器或JavaScript端生成URL）

- Michael Stum

---

为了避免在一个很小的框中进行非常长的解释，我想说我一直在使用数据库键ID，但这会降低我的应用程序中不同部分的性能。 - Ankur

@Ankur 有没有通过缓存解决这个问题的机会？基本上就是Jon建议的，使用全局哈希表。 - Michael Stum

是的，有点像。我的想法是：1）计算某个哈希值，2）按数字顺序存储，3）定期浏览此表，然后将A、B、C等添加到第二、第三、第四个...哈希实例中。我应该提到它不一定非得是int（尽管那样会很好）。只需要紧凑一些的东西。 - Ankur

但是我的解决方案会遇到一些问题，所以并不完美。 - Ankur

Answer 3

考虑到哈希函数是单向的，我建议两种解决方案：

• 使用加密函数来获取表示URL的长字符串（类似于这样-> param=456ab894ce897b98f，具体长度取决于URL）。例如可以使用DES加密或base64url。
• 在数据库中跟踪URL（也可以使用简单的基于文件的数据库，如SQLite）。然后你将有效地拥有一个uint <=> URL的等价关系。

- Vincent Mimoun-Prat

Answer 4

“唯一表示”意味着Java提供的string.hashcode是无用的——很快你就会遇到两个共享相同hashcode的URI。

任何双向方案都会导致一个难以处理的字符串，除非你将URI存储在数据库中并使用记录ID作为唯一标识符。

至于单向方法——MD5哈希比简单的hashcode更加独特（但并非绝对独特），但根据您的定义可能会变得难以处理！

- Will A

Answer 5

问题1：如果您想从数字中恢复字符串，则可以使用以下方法：

1a：对字符串进行加密，这将产生一个随机的字节数组，可以显示为Base-64，大小与原字符串相同或更大，除非您首先压缩字符串。

1b：使用数据库或映射，数字是映射/数据库中字符串的索引。

问题2：字符串不必可恢复。

这里有各种各样的想法。您可以以十六进制或Base-64显示哈希值，以避免负号。在Base-64中，唯一的非字母数字字符是“+”，“/”和“=”。对于几乎唯一的哈希值，您需要使用密码学大小的MD5（128位）、SHA-1（160位）或SHA-2（256或512位）。

MD5哈希看起来像“d131dd02c5e6eec4693d9a0698aff95c”，哈希越大，发生冲突的可能性就越小。

rossum

- rossum