Python中的字典/哈希表设置

Question

我最近在学习Python，参考了一个很有名的教程《Learn Python The Hard Way》。在某个阶段，讲到字典的时候，提到了一些小函数，代码大概是这样的：

def hash_key(aMap, key):
    """Given a key this will create a number and then convert it to
    an index for the aMap's buckets."""
    return hash(key) % len(aMap)

def get_bucket(aMap, key):
    """Given a key, find the bucket where it would go."""
    bucket_id = hash_key(aMap, key)
    return aMap[bucket_id]

我觉得有点难懂的是第一个函数是怎么决定“桶”的ID的。假设我想找到键“myCoolKey”的桶，Python会这样做：hash('myCoolKey') % len(aMap)。如果len(aMap)是“256”，那么结果就是“139”。所以接着看，如果我没理解错的话，“myCoolKey”会被放到aMap的第139个位置。

现在有几个问题：

1. 这样做有什么特别的原因吗？我看不太懂。
2. 那碰撞问题呢？是不是有可能因为这个映射的大小有限，两个键会被分配到同一个位置，而其他位置却还没用呢？

Answer 1

我觉得这个链接很好地解释了字典或哈希表是怎么工作的，特别是针对第39个练习 - https://nicolasgkruk.wordpress.com/2014/07/11/understanding-making-your-own-dictionary-module-from-learning-python-the-hard-way-exercise-39/

Answer 2

1. 哈希表的目的是让你能快速查找数据。这里提到的%取模函数是用来确保你得到的键值总是在哈希表的范围内，这样就不会出现IndexError的问题。通常在这之前还会有额外的哈希处理（就像你提到的那样），目的是让键值尽量均匀分布，这样可以减少冲突的发生。

2. 是的，对于一个通用的哈希表来说，这是可能的。哈希表可以通过以下几种方式来解决这个问题：1）重新哈希这个值，把它放到另一个位置；2）直接把它放到下一个可用的位置；或者3）在那个位置放一个值的列表，而不仅仅是一个单一的值。看起来你的代码选择了第三种方式。