<p>我正在学习抽象数据类型<a href="http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html#implementing-the-map-abstract-data-type" rel="nofollow">here</a>。最近我读到了关于使用Map(或者像dict这样的数据结构)进行散列的文章。在</p>
<p>代码如下所示:</p>
<pre><code>class HashTable:
def __init__(self):
self.size = 11
self.slots = [None] * self.size
self.data = [None] * self.size
def put(self,key,data):
hashvalue = self.hashfunction(key,len(self.slots))
if self.slots[hashvalue] == None:
self.slots[hashvalue] = key
self.data[hashvalue] = data
else:
if self.slots[hashvalue] == key:
self.data[hashvalue] = data #replace
else:
nextslot = self.rehash(hashvalue,len(self.slots))
while self.slots[nextslot] != None and \
self.slots[nextslot] != key:
nextslot = self.rehash(nextslot,len(self.slots))
if self.slots[nextslot] == None:
self.slots[nextslot]=key
self.data[nextslot]=data
else:
self.data[nextslot] = data #replace
def hashfunction(self,key,size):
return key%size
def rehash(self,oldhash,size):
return (oldhash+1)%size
def get(self,key):
startslot = self.hashfunction(key,len(self.slots))
data = None
stop = False
found = False
position = startslot
while self.slots[position] != None and \
not found and not stop:
if self.slots[position] == key:
found = True
data = self.data[position]
else:
position=self.rehash(position,len(self.slots))
if position == startslot:
stop = True
return data
def __getitem__(self,key):
return self.get(key)
def __setitem__(self,key,data):
self.put(key,data)
</code></pre>
<p>现在在教科书中,作者声明哈希表的大小是任意的。请看这里:</p>
<blockquote>
<p>Note that the initial size for the hash table has been chosen to be
11. Although this is arbitrary, it is important that the size be a prime number so that the collision resolution algorithm can be as
efficient as possible.</p>
</blockquote>
<p>为什么这是武断的?似乎给定的插槽数与可以存储的值的数量直接相关。我知道其他哈希表可能是灵活的,能够在一个数据槽中存储更多的数据,但是在这个</strong>特定的例子中,它不仅仅是“任意的”。它就是可以存储多少个值。在</p>
<p>我是不是少了点什么?在</p>