字符串到整数的映射

看看 perfect hashing .

在大多数hashcode()类型的实现中,冲突被认为是不可避免的,并经过测试。

除此之外,还有一些加密散列函数,如MD5和SHA,在这些函数中发生冲突的可能性非常小(尽管可能需要付出很大的努力)。Java加密体系结构具有这些功能的实现。对于非常大的集合,这些方法可能比很好地实现您的解决方案要快。它们也将以恒定的时间执行,并为相同的字符串提供相同的代码,无论字符串添加的顺序如何。而且,它不需要存储每个字符串。加密散列结果可以被视为整数,但它们不适合java整数-您可以使用BigInteger保存它们,正如另一个答案中所建议的那样。

请注意,某些散列函数(如MD5)在理论上也存在一些缺陷,但出于您的目的,这些缺陷可能无关紧要,您可以使用最有效的此类函数-只有当有人恶意尝试提出与另一个字符串具有相同代码的字符串时,这些缺陷才相关。

这是不可能在没有任何限制的情况下实现的,因为可能的字符串比整数多,所以最终会耗尽数字。

只有在限制可用字符串的数量时,才可能找到解决方案。然后你可以使用一个简单的计数器。这里是一个简单的实现,其中可以使用所有(2^32=4294967296个不同的字符串)。不要介意它会占用大量内存。

import java.util.HashMap;
import java.util.Map;

public class StringToInt {

    private Map<String, Integer> map;

    private int counter = Integer.MIN_VALUE;

    public StringToInt() {
        map = new HashMap<String, Integer>();
    }

    public int toInt(String s) {
        Integer i = map.get(s);
        if (i == null) {
            map.put(s, counter);
            i = counter;
            ++counter;
        }
        return i;
    }
}

我会尝试通过引入一个对象来保存Map和Map。将字符串添加到该对象(或者从所述对象创建字符串)将为其分配一个整数值。请求已注册字符串的整数值将返回相同的值。

对于更一般的情况,您可以创建Object的一个高级子类,在那里引入一个“integerize”方法,并从中扩展每个类。然而,我认为,这条路通向眼泪。

由于java中的字符串长度没有限制,每个字符有16位,整数有32位,因此只有在字符串最多两个字符的情况下,才能生成字符串到整数的唯一映射。但您可以使用BigInteger生成一个唯一的映射,如下所示:

String s = "my string";
BigInteger bi = new BigInteger(s.getBytes());

反向映射:

String str = new String(bi.toByteArray());

您可以使用映射来指示您已经为哪些字符串分配了整数吗?这是一种“database-y”解决方案,当字符串出现时,从序列中为每个字符串分配一个“主键”。然后将字符串和整数对放入映射中,以便再次查找。如果需要给定整数的字符串,也可以将同一对放入映射中。

正如您所概述的,解决冲突的哈希表是标准解决方案。您还可以使用Bentley/Sedgewick风格的搜索trie,这在许多应用程序中比散列更快。

如果将“唯一指针”替换为“唯一整数”,您可以看到 Dave Hanson's solution to this problem in C . 这是一个很好的抽象,因为

• 指针仍然可以用作C字符串。

• 相等字符串散列到相等指针,所以 strcmp 可以省略,以支持指针相等,并且指针可以用作其他哈希表中的键。

在…上 String 然后你可以在那里玩同样的游戏。

如果整数是指数据类型,那么正如其他海报所解释的,这是不可能的,因为整数数据类型的大小是固定的,字符串是未绑定的。

但是,如果您只是指一个正数,那么理论上,您应该能够将字符串理解为一个“整数”,只要将其视为一个字节数组(采用一致编码)。也可以将其视为任意长度的整数数组,但如果可以,为什么不使用字符串呢?:)

就实现而言,这通常是通过使用散列码和简单地重复检查任何冲突来“解决”的,因为无论如何都可能没有冲突,并且万一发生冲突,它仍然是常数时间。然而,如果这不适用,我不确定最好的解决方案是什么。

有趣的问题。

我不知道这是否可行,但如果我们只使用小写字母,那么在26个基本位置系统中,每个单词都可以被视为一个数字。例如,如果a为0,z为25,则动臂为1*26^3+14*26^2+14*26^1+12*26^0=27416