用于任意对象的 python 哈希函数的替代方案

在python2.7中，我成功使用hash()将对象放入持久存储在磁盘上的存储桶中。样机代码如下所示：

class PersistentDict(object):
  def __setitem__(self, key, value):
    bucket_index = (hash(key)&0xffffffff) % self.bucket_count
    self._store_to_bucket(bucket_index, key, value)

  def __getitem__(self, key):
    bucket_index = (hash(key)&0xffffffff) % self.bucket_count
    return self._fetch_from_bucket(bucket_index)[key]

在Python3中，hash()使用随机或固定盐，这使得它对此无法使用/不是最佳的[1]。显然，不可能使用用于特定调用的固定盐。所以，我需要一个替代方案：

• 跨解释器调用必须稳定
• 可能需要在执行时提供参数，例如在通话中设置盐
• 必须支持任意对象（任何支持的对象dict/set)

我已经尝试过使用哈希函数hashlib（慢！）和校验和zlib（显然对于散列来说不是理想的，但是嗯）它可以很好地处理字符串/字节。然而，他们工作only在类似字节的对象上，而hash()几乎适用于所有东西。

[1] 使用hash()识别存储桶的方法是：

• 如果盐是随机的，则跨解释器调用不可靠
• 防止应用程序使用随机加盐功能，盐是固定的
• 如果有两个则无法使用PersistentDicts 是用不同的盐创建的

我已经成功地使用了以下组合hash and zlib.adler32。最直接的实现是这样的：

def hashkey(obj, salt=0):
  """
  Create a key suitable for use in hashmaps

  :param obj: object for which to create a key
  :type: str, bytes, :py:class:`datetime.datetime`, object
  :param salt: an optional salt to add to the key value
  :type salt: int
  :return: numeric key to `obj`
  :rtype: int
  """
  if obj is None:
    return 0
  if isinstance(obj, str):
    return zlib.adler32(obj.encode(), salt) & 0xffffffff
  elif isinstance(obj, bytes):
    return zlib.adler32(obj, salt) & 0xffffffff
  elif isinstance(obj, datetime_type):
    return zlib.adler32(str(obj).encode(), salt) & 0xffffffff
  return hash(obj) & 0xffffffff

使用 Python 3.4.3，这比调用普通函数慢很多hash，大约需要 0.07 us。对于一个规则的物体来说，hashkey需要 ~1.0 usc。 0.8 微秒bytes0.7 为str.

开销大致如下：

• 函数调用需要 0.1 usec (hash(obj) vs def pyhash(obj): return hash(obj))
• 0.2 usec 到 0.5 usec 用于选择哈希函数isinstance
• 0.75 用于zlib.adler32 or zlib.crc32 vs hash：~0.160 usec vs ~ 0.75 usec（adler 和 crc 为 +/- 4 usec）
• 0.15 微秒obj.encode() of str对象（"foobar")
• 1.5 微秒str(obj).encode() of datetime.datetime objects

最优化来自于排序if声明。如果人们主要期望普通对象，那么以下是我能想到的最快的：

def hashkey_c(obj, salt=0):
  if obj.__class__ in hashkey_c.types:
    if obj is None:
      return 0
    if obj.__class__ is str:
      return zlib.adler32(obj.encode(), salt) & 0xffffffff
    elif obj.__class__ is bytes:
      return zlib.adler32(obj, salt) & 0xffffffff
    elif obj.__class__ is datetime_type:
      return zlib.adler32(str(obj).encode(), salt) & 0xffffffff
  return hash(obj) & 0xffffffff
hashkey_c.types = {str, bytes, datetime_type, type(None)}

总时间：~0.7 usstr and bytes, 糟糕透顶datetime, 0.35 usec 用于对象、整数等。dict将类型映射到可比较的散列，如果对dict键（又名类型）分别（即不obj.__class__ in hashkey.dict_types but obj.__class__ in hashkey.explicit_dict_types).

一些附加说明：

• hash对于使用默认值的任何对象，跨解释器启动都不稳定__hash__实施，包括None
• 它对于不可变容器（定义了__hash__) 含有盐分类型，例如(1, 2, 'three')