python哈希表链表

### Python 中哈希表与链表的实现及用法

#### 哈希表的概念及其组成部分
哈希表是一种线性表的存储结构，主要由一个直接寻址表和一个哈希函数构成。哈希函数 \( h(k) \) 将元素的关键字 \( k \) 作为输入参数，并返回该元素应存放在数组中的索引位置[^1]。

当多个不同的关键字通过相同的哈希函数映射到同一个地址时会发生哈希冲突。解决哈希冲突的方法有很多，其中一种常用的方式是在发生冲突的位置链接一条单向链表来保存具有相同哈希值的不同记录。

#### 使用内置 `dict` 类型创建简单的哈希表
Python 的内置字典类型实际上就是一个高效的哈希表实现：

hash_table = {}
hash_table['key'] = 'value'
print(hash_table.get('key'))

这段代码展示了如何利用 Python 自带的支持快速查找特性的字典对象构建简易版键值对形式的哈希表[^2]。

#### 手动编写带有拉链法处理碰撞的哈希表类
为了更深入理解哈希表的工作原理以及学习如何应对可能发生的哈希冲突问题，下面给出了一种基于拉链法的手工实现方案:

class HashTable:
    def __init__(self, size=7):  
        self.data_map = [None] * size
    
    def _hash(self, key):
        my_hash = 0
        for letter in str(key):
            my_hash = (my_hash + ord(letter)) % len(self.data_map)
        return my_hash
      
    def set_item(self, key, value):
        index = self._hash(key)
        if not self.data_map[index]:
            self.data_map[index] = []
        self.data_map[index].append([key, value])
        
    def get_item(self, key):
        index = self._hash(key)
        if self.data_map[index] is not None:
            for i in range(len(self.data_map[index])):
                if self.data_map[index][i][0] == key:
                    return self.data_map[index][i][1]
        return None
        
ht = HashTable()
ht.set_item('bolts', 1400)
ht.set_item('washers', 50)
print(ht.get_item('bolts'))  # 输出: 1400

上述例子定义了一个名为 `HashTable` 的类，它内部维护着一个固定大小的列表用于存放实际数据项；每当遇到新的条目加入时会调用 `_hash()` 方法计算其对应的桶编号并将其追加至相应位置处形成的链表末端；而在检索指定项目的过程中则需遍历对应槽位上的全部节点直至找到匹配者为止。

#### 单项链表的基础操作
对于链表而言，在 Python 中可以通过定义结点(Node)类来进行表示，每个 Node 对象包含两部分信息：一是当前储存的数据(data)，二是指向下一个 node 的指针(next)[^3]:

class ListNode:
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node


node1 = ListNode("apple")
node2 = ListNode("banana", node1)

current = node2
while current:
    print(current.data)
    current = current.next_node

此段程序片段建立了两个相连的节点实例(node1 和 node2), 并实现了从头到尾依次打印各节点所携带的信息的功能.