python腳本 「進口HashMap的」 打印 '0'和' -1的

Question

運行的時候，僅僅擁有代碼

import hashmap

一行Python腳本，它打印出來就這樣

0 
-1 
0 
-1 

以及更多0 s和-1 s

它是有線的，我找不出原因。這裏是hashmap.py文件：

def new(num_buckets=256): 
    """Initializes a Map with given number of buckets.""" 
    aMap = [] 
    for i in range(0, num_buckets): 
     aMap.append([]) 
    return aMap 

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) % -2# len(aMap) # WHAT'S THIS?!!! 

aMap = new() 
for i in range(0, 300): 
    print hash_key(aMap, "abc%r" % i) 

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] 

def get_slot(aMap, key, default=None): 
    """ 
    Returns the index, key, and value of a slot found in the bucket. 
    Returns -1, key, and default (None if not set) when not found. 
    """ 
    bucket = get_bucket(aMap, key) 

    for i, kv in enumerate(bucket): 
     k, v = kv 
     if key == k: 
      return i, k, v 

    return -1, key, default 

def get(aMap, key, default=None): 
    """Gets the value in a bucket for the given key, or the default.""" 
    i, k, v = get_slot(aMap, key, default=default) # what if just "default"?????? 
    return v 

def set(aMap, key, value): 
    """set the key to the value, replacing any existing value.""" 
    bucket = get_bucket(aMap, key) 
    i, k, v = get_slot(aMap, key) 

    if i >= 0: 
     # the key exists, replace it 
     bucket[i] = (key, value) 
    else: 
     # the key does not, append to create it 
     bucket.append((key, value)) 

def delete(aMap, key): 
    """Deletes the given key from the Map.""" 
    bucket = get_bucket(aMap, key) 

    for i in xrange(len(bucket)): 
     k, v = bucket[i] 
     if key == k: 
      del bucket[i] 
      break 

def list(aMap): 
    """Prints out what's in the Map.""" 
    for bucket in aMap: 
     if bucket: 
      for k, v in bucket: 
       print k,v 

Answer 1

這裏的原因是：

aMap = new() 
for i in range(0, 300): 
    print hash_key(aMap, "abc%r" % i) 

當導入模塊，執行所有的頂級代碼。特別是，您的hash_key函數返回x % -2（其中x是一些數字量）。因此，上面的代碼將打印0或-1 300次。

即使這是所需的行爲，你的散列函數仍然是錯誤的。看看這一行：

hash(key) % -2# len(aMap) # WHAT'S THIS?!!! 

這裏是回答你「這是什麼？」：x % len(aMap)部分用於約束[0; len(aMap))範圍中的值，以便它可用於選擇合適的存儲桶。通過使用-2，你將只在hashmap中選擇兩個桶，即第一個和最後一個。這會增加碰撞解決的重大開銷，無論是封閉式還是開放式尋址。

Answer 2

您需要刪除這部分腳本或將其添加到if __name__ == '__main__':塊：

aMap = new() 
for i in range(0, 300): 
    print hash_key(aMap, "abc%r" % i) 

當腳本（模塊）是進口的，則執行其代碼。所以你看到的數字就是上面代碼的輸出。