python - 分配/检索方法在单独的链接 Python 哈希图中不起作用

Question

虽然我知道 Python 有用于实用目的的内置字典，但我试图通过创建一个带有花及其定义的哈希映射来理解单独链接哈希映射的概念。

但是，当我尝试从哈希映射打印检索时，我得到None.

from linked_list import Node, LinkedList

class HashMap:
  def __init__(self, size):
    self.array_size = size
    self.array = [LinkedList() for i in range(size)]

  def hash(self, key):
    return sum(key.encode())

  def compress(self, hash_code):
    return hash_code % self.array_size

  def assign(self, key, value):
    hash_code = self.hash(key)
    array_index = self.compress(hash_code)
    payload = Node([key, value])
    list_at_array = self.array[array_index]
    for item in list_at_array:
      if key == item[0]:
        item[1] = value
      else:
        self.array[array_index].insert(payload)

  def retrieve(self, key):
    hash_code = self.hash(key)
    array_index = self.compress(hash_code)
    list_at_index = self.array[array_index]
    for item in list_at_index:
      if item[0] == key:
        return item[1]
      else:
        return None

from blossom_lib import flower_definitions

blossom = HashMap(len(flower_definitions))

for each in flower_definitions:
  blossom.assign(each[0], each[1])
print(blossom.retrieve('daisy'))

以下是两个模块：

开花lib.py

flower_definitions = [['begonia', 'cautiousness'], ['chrysanthemum', 'cheerfulness'], ['carnation', 'memories'], ['daisy', 'innocence'], ['hyacinth', 'playfulness'], ['lavender', 'devotion'], ['magnolia', 'dignity'], ['morning glory', 'unrequited love'], ['periwinkle', 'new friendship'], ['poppy', 'rest'], ['rose', 'love'], ['snapdragon', 'grace'], ['sunflower', 'longevity'], ['wisteria', 'good luck']]

链接列表.py

class Node:
  def __init__(self, value):
    self.value = value

  def get_value(self):
    return self.value

  def get_next_node(self):
    return self.next_node

  def set_next_node(self, next_node):
    self.next_node = next_node

class LinkedList:
  def __init__(self, head_node=None):
    self.head_node = head_node

  def insert(self, new_node):
    current_node = self.head_node

    if not current_node:
      self.head_node = new_node

    while(current_node):
      next_node = current_node.get_next_node()
      if not next_node:
        current_node.set_next_node(new_node)

  def __iter__(self):
    current_node = self.head_node
    while(current_node):
      yield current_node.get_value()

提前致谢！

标签： pythonhashmap

Answer 1

这里有几个问题。

1)Node初始化next_node- 导致 AttributeError

def __init__(self, value):
    self.value = value
    self.next_node = None

2)LinkedList迭代 - current_node控制循环的变量从未移动到列表中的下一个元素。

def __iter__(self):
    current_node = self.head_node
    while (current_node):
        value = current_node.get_value()
        current_node = current_node.get_next_node()
        yield value

3) LinkedList insert- 与前一种情况类似，current_node从未移动到列表中的下一个元素。

while (current_node):
    next_node = current_node.get_next_node()
    if not next_node:
        current_node.set_next_node(new_node)
    current_node = next_node

4）HashMap assign- 它过于复杂，在识别出正确的列表来放置它之后，使用该insert列表的方法就足够了。

def assign(self, key, value):
    hash_code = self.hash(key)
    array_index = self.compress(hash_code)
    payload = Node([key, value])
    list_at_array = self.array[array_index]
    list_at_array.insert(payload)

5) HashMap retrieve- 如果列表有多个元素（具有相同的哈希值）并且第一个元素不是我们要查找的元素，它将返回 None。正确的做法是None遍历列表中的所有元素后返回，如果没有找到则None返回，所以解决方法是减少return None.

def retrieve(self, key):
    hash_code = self.hash(key)
    array_index = self.compress(hash_code)
    list_at_index = self.array[array_index]
    for item in list_at_index:
        if item[0] == key:
            return item[1]
    return None

使用以下命令检查示例的正确性：

for each in flower_definitions:
    print(each[0] + ' (' + str(sum(each[0].encode()) % len(flower_definitions)) + '): ' + blossom.retrieve(each[0]))

给出：

begonia (11): cautiousness
chrysanthemum (2): cheerfulness
carnation (7): memories
daisy (6): innocence
hyacinth (2): playfulness
lavender (9): devotion
magnolia (0): dignity
morning glory (7): unrequited love
periwinkle (4): new friendship
poppy (8): rest
rose (7): love
snapdragon (5): grace
sunflower (3): longevity
wisteria (4): good luck

完整的解决方案可以在这里找到