Python中的字典/哈希映射设置

Question

我已经在著名的《Learn Python the Hard Way》教程上学习Python好几天了。在讨论练习39中的字典时，有几个这样的小函数:

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

1. 哈希表的目的是为您提供即时查找时间。%模函数用于确保始终拥有一个在哈希表范围内的键(因此不存在IndexError问题)。在此之前通常会有额外的散列(例如在您的情况下)，以尝试并确保键尽可能均匀分布，以减少冲突。

2. 是的，对于一般哈希表是可能的。散列表可以通过以下方式解决这个问题:1)重新散列值以将其放入另一个槽中，2)将其放入下一个可用槽中，或者3)将值列表放入该槽中，而不仅仅是单个值。

Answer 2

我认为这个链接为练习39提供了一个很好的字典或hashmap如何工作的演练- https://nicolasgkruk.wordpress.com/2014/07/11/understanding-making-your-own-dictionary-module-from-learning-python-the-hard-way-exercise-39/