class Node:
    """链表节点，用于存储键值对"""
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class SimpleHashTable:
    """一个简单的哈希表，使用链地址法解决冲突"""
    def __init__(self, capacity=10):
        # 初始化一个固定大小的数组（桶），每个桶是一个链表的头节点
        self.capacity = capacity
        self.size = 0
        self.buckets = [None] * self.capacity  # 初始所有桶为空

    def _hash(self, key):
        """一个简单的哈希函数：将键转换为索引"""
        # 使用内置的hash函数，并用容量取模确保索引在数组范围内
        return hash(key) % self.capacity

    def put(self, key, value):
        """插入或更新键值对"""
        index = self._hash(key)
        node = self.buckets[index]

        # 遍历当前索引对应的链表
        # 1. 如果键已存在，则更新其值
        while node:
            if node.key == key:
                node.value = value  # 更新值
                return
            node = node.next

        # 2. 如果键不存在，则创建一个新节点插入到链表头部（头插法）
        new_node = Node(key, value)
        new_node.next = self.buckets[index] # 新节点指向原来的头节点
        self.buckets[index] = new_node      # 新节点成为新的头节点
        self.size += 1

        # 简单的扩容逻辑（可选）：当负载因子>1时，进行扩容
        # 注意：实际应用中负载因子阈值通常更低（如0.75）
        if self.size / self.capacity > 1:
            self._resize()

    def get(self, key):
        """根据键查找值"""
        index = self._hash(key)
        node = self.buckets[index]

        # 在链表中查找键
        while node:
            if node.key == key:
                return node.value  # 找到，返回值
            node = node.next

        return None  # 未找到

    def remove(self, key):
        """根据键删除键值对"""
        index = self._hash(key)
        node = self.buckets[index]
        prev = None  # 记录前一个节点，用于链表操作

        # 在链表中查找要删除的节点
        while node:
            if node.key == key:
                if prev:
                    prev.next = node.next  # 跳过当前节点（中间或尾部删除）
                else:
                    self.buckets[index] = node.next  # 删除的是头节点
                self.size -= 1
                return True  # 删除成功
            prev = node
            node = node.next

        return False  # 键不存在，删除失败

    def _resize(self):
        """当负载因子过高时，进行扩容和再哈希"""
        old_buckets = self.buckets
        self.capacity *= 2  # 容量翻倍
        self.buckets = [None] * self.capacity
        self.size = 0  # size会在重新put时重新计算

        # 将旧表中的所有数据重新插入新表
        for head_node in old_buckets:
            node = head_node
            while node:
                self.put(node.key, node.value) # 重新哈希并插入
                node = node.next

# 测试我们的哈希表
if __name__ == "__main__":
    ht = SimpleHashTable()
    ht.put("apple", 5)
    ht.put("banana", 3)
    ht.put("orange", 8)
    ht.put("pear", 2)
    ht.put("grape", 6) # 可能引起冲突，取决于哈希函数和容量

    print(f"苹果的价格: {ht.get('apple')}")   # 输出: 5
    print(f"香蕉的价格: {ht.get('banana')}")   # 输出: 3
    print(f"葡萄的价格: {ht.get('grape')}")    # 输出: 6

    ht.put("apple", 10) # 更新苹果的价格
    print(f"更新后苹果的价格: {ht.get('apple')}") # 输出: 10

    ht.remove("orange")
    print(f"删除橙子后查找: {ht.get('orange')}") # 输出: None

    print(f"哈希表当前大小: {ht.size}") # 输出: 4