Question

字典和集合使用散列表来获得O(1)的查询和插入。能得到这一效率是因为我们非常聪明地使用散列函数将一个任意的键（如一个字符串或一个对象）转变成了一个列表的索引。散列函数和列表随后可以被用来决定任意数据的位置，而无须搜索。通过将一个数据的键转化成某种可以被用作列表索引的东西，我们就得到了跟列表一样的性能。而且，由于无须使用数字作为索引（它本身暗示了数据的某种顺序），我们可以用任意的键来引用数据。

4.1.1　插入和获取

为了创建一个散列表，我们先从分配一些内存开始，这一点和数组一样。对于一个数组，如果我们想要插入数据，我们只需要找到未被使用的最小的桶并将我们的数据插入那里（如果有必要的话还要改变数组的大小）即可。对于散列表，我们必须首先弄清楚数据在这个连续内存块中的位置。

新插入数据的位置取决于数据的两个属性：键的散列值以及该值如何跟其他对象 比较。这是因为当我们插入数据时，首先需要计算键的散列值并掩码来得到一个有效的数组索引。^[2]掩码是为了保证一个可能是任意数字的散列值最终能落入分配　的桶中。所以，如果我们分配了8个块的内存，而我们的散列值是28957，那么它将落入的桶的索引是28957 & 0b111 = 7。如果我们的字典增长到了需要512块内存，那么掩码就变成0b11111111（此时，我们会使用位于28957 & 0b11111111的桶）。现在我们需要检查这个桶是否已经被使用。如果它是空桶，我们可以将键和值插入这一内存块。我们保存键是为了在获取时确保获得的是正确的值。如果桶已经被使用，且桶内的值跟我们希望插入的值相等（使用内建的cmp进行比较），说明这一键值对已经保存于散列表中，我们可以直接返回。然而，如果值不相等，那么我们需要找到一个新的位置来保存数据。

为了找到新的索引，我们用一个简单的线性函数计算出一个新的索引，这一方法称为嗅探。Python的嗅探机制使用了原始散列值的高位比特（还记得对于之前那个长度为8的散列表，由于使用的掩码mask = 0b111 = bin(8 - 1)，我们只用了最后3个bit作为初始索引）。使用这些高位比特使得每一个散列值生成的下一可用散列序列都是不同的，这样就能帮助防止未来的碰撞。生成新索引的算法有很多自由的选择，不过，需要注意的是计算方案要能访问每一个可能的索引使得数据能够尽量均匀地分布在表中。数据分布的均匀程度被称为“负载因素”，它跟散列函数的熵有关。例4-4中的伪码描述了CPython 2.7中使用的散列索引的计算。

例4-4　字典查询序列

def index_sequence(key, mask=0b111, PERTURB_SHIFT=5):
  perturb = hash(key)  #υ❶
  i = perturb & mask
  yield i
  while True:
    i = ((i << 2) + i + perturb + 1)
    perturb >>= PERTURB_SHIFT
    yield i & mask

❶ hash返回的是一个整型，而CPython中实际的C代码使用的是无符号整型。因此，这段伪码并没有100%复制CPython的行为，但它是一个不错的近似。

这一嗅探函数是基础的“线性嗅探”方法的修改版。在线性嗅探中，我们让i = (5 * i + 1) & mask，i的初始值是键的散列值，算法中用到的5这个值对于当前的讨论不重要。^[3]重要的是记住线性嗅探仅使用了散列值的最后几个字节而没有考虑其余字节（比如，对于一个8元素字典，我们只查看了最后3个比特，因为当前的掩码是0x111）。这意味着如果两个键的散列值最后3个比特相等，那么不仅产生了一个碰撞，同时其后的嗅探索引序列也都是一样的。Python使用的扰动方案会考虑散列值中更多的比特位来解决这一问题。

当我们在查询某个键时也有一个类似的过程：给出的键会被转化为一个索引进行检索。如果和该索引指向的位置中的键符合（在插入操作时我们会保存原始的键），那么我们就会返回那个值。如果不符合，我们用同一个方案继续创建新的索引，直至我们找到数据或找到一个空桶。如果我们找到一个空桶，我们就可以认为表里不存在该数据。

图4-1显示了往散列表中添加数据的过程。我们创建的散列函数只使用输入的第一个字符。我们利用了Python的ord函数将输入的第一个字符转成一个整型（散列函数必须返回整型）。我们在4.1.4节中将会看到，Python为其大多数类型都提供了一个散列函数，所以你无须自己提供一个，除非是在某些极端情况下。

插入键“Barcelona”时发生了一个碰撞，用例4-4的方案计算出一个新的索引。创建这个字典的Python代码见例4-5。

例4-5　自定义散列函数

class City(str):
  def __hash__(self):
    return ord(self[0])

# We create a dictionary where we assign arbitrary values to cities
data = {
  City("Rome"): 4,
  City("San Francisco"): 3,
  City("New York"): 5,
  City("Barcelona"): 2,
}

图4-1　插入散列表时发生碰撞的结果

在这里，“Barcelona”和“Rome”发生了散列碰撞（图4-1显示了插入时的结果）。我们看到，对于一个拥有四个元素的字典，它的掩码是0b111。“Barcelona”会尝试使用索引ord("B") & 0b111 = 66 & 0b111 = 0b1000010 & 0b111 = 0b010 = 2。同样，“Rome”会尝试使用索引ord("R") & 0b111 = 82 & 0b111 = 0b1010010 & 0b111 = 0b010 = 2。

　问题　

思考下面的问题，讨论散列碰撞：

1．查找一个元素——使用例4-5创建的字典，对“Johannesburg”键的查询是怎样的？检索的索引是什么？

2．删除一个元素——使用例4-5创建的字典，如何处理“Rome”键的删除？后续对“Rome”和“Barcelona”键的查询会被如何处理？

3．散列碰撞——考虑例4-5创建的字典，如果有500个首字母大写的城市被插入散列表，你估计会有多少次散列碰撞？1000个城市又如何？你能否想到一种方法降低碰撞次数？

对于500个城市，大约有474个字典元素会跟之前的值冲突（500—26），每个散列值会有大约500 / 26 = 19.2个城市与之关联。对于1000个城市则是974次碰撞，每个散列值有1000 / 26 = 38.4个城市与之关联。这是因为散列函数只是简单地基于首字母的数值，其取值范围为A-Z，仅有26个独立散列值。这意味着一次查询会导致最多38次子查询来找到正确的值。为了修正这一点，我们必须考虑城市的其他方面来增加可能的散列值。默认的字符串散列函数会考虑每一个字符使散列值的可能取值范围最大化。4.1.4节中有更多解释。

4.1.2　删除

当一个值从散列表中被删除时，我们不能简单地写一个NULL到内存的那个桶里。这是因为我们已经用NULL来作为嗅探散列碰撞的终止值。所以，我们必须写一个特殊的值来表示该桶虽空，但其后可能还有别的因散列碰撞而插入的值。这些空桶可以在未来被写入或在散列表改变大小时被删除。

4.1.3　改变大小

当越来越多的项目被插入散列表时，表本身必须改变大小来适应。研究显示一个不超过三分之二满的表在具有最佳空间节约的同时依然具有不错的散列碰撞避免率。因此，当一个表到达关键点时，它就会增长。为了做到这一点，需要分配一个更大的表（也就是在内存中预留更多的桶），将掩码调整为适合新的表，旧表中的所有元素被重新插入新表。这需要重新计算索引，因为改变后的掩码会改变索引计算结果。结果就是，改大散列表的代价非常昂贵！不过，因为我们只在表太小时而不是在每一次插入时进行这一操作，分摊后每一次插入的代价依然是O(1)。

字典或集合默认的最小长度是8（也就是说，即使你只保存3个值，Python仍然会分配8个元素）。每次改变大小时，桶的个数增加到原来的4倍，直至达到50000个元素，之后每次增加到原来的2倍。这导致了下面可能的大小：

8, 32, 128, 512, 2048, 8192, 32768, 131072, 262144, ...

值得注意的是当一个散列表变大或变小时都可能发生改变大小。也就是说，如果散列表中足够多的元素被删除，表可能会被改小。但是，改变大小仅发生在插入时。

4.1.4　散列函数和熵

Python对象通常以散列表实现，因为它们已经有内建的__hash__和__cmp__函数。对于数字类型（int和float），散列值就是基于它们数字的比特值。元组和字符串的散列值基于它们的内容。而另一方面，列表不能被散列，因为它们的值可以改变。一旦列表的值发生改变，其散列值也会相应改变，也就改变了键在散列表中的相对位置。^[4]

用户自定义类也有一个默认的散列和比较函数。默认的__hash__函数使用内建的id函数返回对象在内存中的位置。同样，__cmp__操作符比较的也是对象在内存中的位置的数字值。

这么做一般来说没什么问题，因为一个类的两个实例一般是不同的，不会导致散列碰撞。然而在某些情况下我们会想要使用set或dict对象来消除项目之间的歧义。见下例的类定义：

class Point(object):
  def __init__(self, x, y):
    self.x, self.y = x, y

如果我们用相同的x和y实例化多个Point对象，它们在内存中是独立的对象，各自处在内存中的不同位置，也就有各自不同的散列值。这意味着将它们放入一个set会导致它们各自都是一个独立的项目：

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x1099bfc90>, <__main__.Point at 0x1099bfbd0>])
>>> Point(1,1) in set([p1, p2])
False

我们可以提供一个基于对象内容而不是对象在内存中的位置的自定义散列函数来解决这个问题。散列函数可以是任意函数，只要它对于同一个对象始终给出同一个散列值。（散列函数对熵也有要求，我们后面会加以讨论。）下面的例子重定义了Point类，给出了我们期望的结果：

class Point(object):
  def __init__(self, x, y):
    self.x, self.y = x, y

  def __hash__(self):
    return hash((self.x, self.y))

  def __eq__(self, other):
    return self.x == other.x and self.y == other.y

这让我们在集合或字典中创建的项目能够以Point对象的内部属性而不是其在内存中的位置为索引：

>>> p1 = Point(1,1)
>>> p2 = Point(1,1)
>>> set([p1, p2])
set([<__main__.Point at 0x109b95910>])
>>> Point(1,1) in set([p1, p2])
True

之前我们讨论散列碰撞时提到，一个用户自定义的散列函数需要让散列值均匀分布以避免散列碰撞。碰撞太频繁会降低散列表的性能：如果大多数键都有碰撞，那么我们需要经常“嗅探”其他索引值，有可能需要在字典中访问很大一片区域来寻找需要的键。最坏情况下，字典中所有的键都碰撞，字典查询的性能变成O(n)，就跟搜索一个列表一样。

如果我们在创建散列函数时知道我们要在字典中存储5000个值，我们必须注意整个字典将被存储在一个大小为32768的散列表中，所以我们的散列值只有最后15个比特参与了索引的创建（对于这个大小的散列表，掩码是bin(32768-1) = 0b111111111111111``）。

衡量“我的散列函数分布均匀程度”的标准被称为散列函数的熵。熵的定义是：

p(i)是散列函数给出散列值为i的概率。当所有的散列值都具有同样的被选中概率时熵最大。一个令熵最大的散列函数被称为完美散列函数，因为它保证了最低的碰撞次数。

对于无穷大的字典，整数的散列函数就是完美散列函数。这是因为一个整数的散列值就是整数自身！一个无穷大字典的掩码也是无穷大，所以我们会使用散列值的所有比特。于是，给定任意两个数字，我们都可以保证它们的散列值不会相等。

不过，如果我们考虑有限大的字典，那么我们将不再具有这样的保证。比如，对于一个具有四个元素的字典，我们使用的掩码是0b111。那么，数字5的散列值是5 & 0b111 = 5，而501的散列值是501 & 0b111 = 5，它们的条目会碰撞。

　备忘　

为了找到大小为N的字典的掩码，我们首先找到能令该字典保持三分之二满的最低桶数（N * 5 / 3），然后找到能满足这个数字的最小字典大小（8; 32; 128; 512; 2048; 等等）并找到足以保存这一数字的bit的位数。比如，如果N=1039，那么我们至少需要1731个桶，这意味着我们的字典有2048个桶。那么掩码就是bin(2048 - 1) = 0b11111111111。

对于有限大小的字典不存在一个最佳的散列函数。不过，提前知道散列值的范围以及字典的大小可以帮助我们做出好的选择。比如，如果我们要在字典中存储总共676个双小写字母组合（aa、ab、ac等），那么例4-6就是一个好的散列函数。

例4-6　最优双字母散列函数

def twoletter_hash(key):
  offset = ord('a')
  k1, k2 = key
  return (ord(k2) - offset) + 26 * (ord(k1) - offset)

当掩码为0b1111111111时（一个具有676个元素的字典将被保存在一个长度为2048的散列表中，其掩码是bin(2048-1) = 0b1111111111），这个散列函数对于任意两个双小写字母都不会发生散列碰撞。

例4-7十分明显地展示了一个用户自定义类使用了坏的散列函数的后果——在这里，一个坏的散列函数（实际上是最糟糕的散列函数！）的代价是查询变慢21.8倍。

例4-7　好坏散列函数的时间区别

import string
import timeit

class BadHash(str):
  def __hash__(self):
    return 42

class GoodHash(str):
  def __hash__(self):
    """
    This is a slightly optimized version of twoletter_hash
    """
    return ord(self[1]) + 26 * ord(self[0]) - 2619

baddict = set()
gooddict = set()
for i in string.ascii_lowercase:
  for j in string.ascii_lowercase:
    key = i + j
    baddict.add(BadHash(key))
    gooddict.add(GoodHash(key))

badtime = timeit.repeat(
  "key in baddict",
  setup = "from __main__ import baddict, BadHash; key = BadHash('zz')",
  repeat = 3,
  number = 1000000,
)
goodtime = timeit.repeat(
  "key in gooddict",
  setup = "from __main__ import gooddict, GoodHash; key = GoodHash('zz')",
  repeat = 3,
  number = 1000000,
)

print "Min lookup time for baddict: ", min(badtime)
print "Min lookup time for gooddict: ", min(goodtime)

# Results:
# Min lookup time for baddict: 16.3375990391
# Min lookup time for gooddict: 0.748275995255

　问题　

1．证明对于一个有限字典（具有有限掩码），使用整数的值作为其散列值不会导致碰撞。

2．证明例4-6的散列函数对于一个大小为1024的散列表是完美的。为什么它对更小的散列表不完美？