1

我正在编写一个包含 10 个桶列表的简单哈希表。该索引是使用内置计算的hash()，然后对表大小取模。但是，当我尝试将对象附加到该索引处的存储桶列表时，它会被附加到每个存储桶列表中。我尝试过以不同的方式定义 add_HT，但我一直得到相同的结果。我究竟做错了什么？

size = 10
HT = [ [] ] * size

def add_HT(data):
    index = hash(data) % size
    HT[index].append(data)

print HT

[[], [], [], [], [], [], [], [], [], []]

add_HT('hello')

[['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello']]
4

4 回答 4

5

HT = [ [] ] * size使size多个指针指向同一个列表。add_HT问题不在这里。您需要定义HT为[[] for i in xrange(size)].

于 2013-01-07T05:42:55.313 回答
4

您将定义HT为对单个列表的十个引用。相反，像这样定义它：

HT = [[] for _ in xrange(size)]
于 2013-01-07T05:43:03.657 回答
3

正如 Volatility 和 kindall 已经解释的那样，HT = [ [] ] * size制作 10 个相同的 empty 副本list，而不是 10 个不同的 empty lists。list身份总是会咬新程序员——有时甚至会咬专家。

他们已经向您展示了如何解决问题并获得 10 个不同的 empty lists。但是还有另一种方法可以解决这个问题。如果您可以重写您的程序以完全不改变lists，那么它们是否相同并不重要：

def add_HT(data):
    index = hash(data) % size
    HT[index] = HT[index] + [data]

现在：

>>> add_HT('hello')
>>> add_HT('goodbye')
>>> HT
[['goodbye'], ['hello'], [], [], [], [], [], [], [], []]

这里发生的情况是，您每次追加时都会创建一个新存储桶，并替换旧存储桶，因此这些存储桶是不可变的。（您可能希望将它们存储为tuples 而不是lists，以确保您不会意外地改变它们。）

您可以更进一步，不仅使每个HT[i]不可变，而且使其HT自身：

def add_HT(data):
    global HT
    index = hash(data) % size
    HT = [bucket if i != index else bucket + [data] for i, bucket in enumerate(HT)]

有时使事物不可变会使代码更简单，有时更复杂。（在这种情况下，我认为第一个不可变版本与可变版本一样简单，但第二个版本的可读性要差得多。）有时它使代码更快，有时更慢。（在这种情况下，快速测试显示第一个速度大致相同，但第二个速度慢 50 倍，并且使用更多内存。另一方面，使用 PyPy 而不是 CPython，它们分别是 15% 和 30%较慢，分别……）但它总是更容易推理——你不必担心对象身份。除非它使事情更容易编写、更容易阅读、更快，否则你必须考虑权衡。但值得知道如何去做。

于 2013-01-07T06:05:44.380 回答
0

这是正确的版本：

size = 10
HT = [ [] for x in range(size)]

def add_HT(data):
    index = hash(data) % size
    HT[index].append(data)

print HT

add_HT('hello')
print HT

输出：

>>> 
[[], [], [], [], [], [], [], [], [], []]
[[], ['hello'], [], [], [], [], [], [], [], []]
>>>
于 2013-01-07T05:47:56.143 回答