为字符串分配唯一整数id的最有效方法是什么？

Question

我编写的程序处理大量的对象,每个对象都有自己唯一的id,它本身就是一串复杂的结构(由一些分隔符连接的对象的十几个独特字段)和大的长度.

因为我必须快速处理很多这些对象,并且我需要在处理时通过id对它们进行处理,我没有权力改变它们的格式(我通过网络从外部检索它们),我想将它们复杂的字符串id映射到我自己的内部整数id,并进一步用于比较,将它们进一步转移到其他进程等.

我要做的是使用一个简单的dict,键作为对象的字符串id,整数值作为我的内部整数id.

我的问题是:在Python中有更好的方法吗？可能有一种方法可以手动计算一些哈希值,无论如何？可能是dict不是最好的解决方案？

至于数字:系统中一次有大约100K这样的独特对象,所以整数容量绰绰有余.

Answer 1

为了进行比较,您可以intern对字符串进行比较,is而不是将它们进行比较==,它可以进行简单的指针比较,并且应该与比较两个整数一样快(或者比它快):

>>> 'foo' * 100 is 'foo' * 100
False
>>> intern('foo' * 100) is intern('foo' * 100)
True

intern保证id(intern(A)) == id(intern(B))iff A == B.输入后请务必留下intern任何字符串.请注意,在Python 3.x中intern调用sys.intern.

但是当你必须将这些字符串传递给其他进程时,你的dict解决方案似乎是最好的.在这种情况下我通常做的是

str_to_id = {}
for s in strings:
    str_to_id.setdefault(s, len(str_to_id))

所以整数容量绰绰有余

Python整数是bigint,因此永远不应该是一个问题.

Answer 2

这个hash功能怎么样？

In [130]: hash
Out[130]: <function hash>

In [131]: hash('foo')
Out[131]: -740391237

没有必要存储哈希值(除非你想):关键是它们对于值相等的对象是相等的(虽然反过来可能不是这样的 - 毫无疑问,不相等的字符串或其他对象会散列到相同的值;这是散列的本质).

如果你知道你的键的范围(你可能也知道),你也可以使用一个完美的哈希函数生成器.这显然是python的一个:http://ilan.schnell-web.net/prog/perfect-hash/

完美哈希保证指定范围内的键与其哈希值具有双射关系.