# ===== CodeLab: 哈希表:空间换时间 =====
# 来源: https://aoerliang.dpdns.org/articles/algo-hash
# 以下代码片段按文章出现顺序拼接, 共 3 段

# ----- 片段 1 (python) -----
# 模拟一个简易哈希表:只处理字符串键
def simple_hash(key, size):
    total = 0
    for ch in key:
        total += ord(ch)
    return total % size

print(simple_hash("cat", 10))   # 3
print(simple_hash("act", 10))   # 3  ← 冲突了!

# ----- 片段 2 (python) -----
# dict:键值对,查找 / 插入 / 删除都是平均 O(1)
scores = {"Ada": 95, "Bob": 87}
scores["Cindy"] = 92           # 插入
print(scores.get("Ada"))       # 95,不存在返回 None 而不报错
print("Bob" in scores)         # True,成员判断 O(1)

# set:只存键,天然去重
words = ["a", "b", "a", "c"]
print(len(set(words)))         # 3,去重后数量
print("b" in set(words))       # True

# ----- 片段 3 (python) -----
def two_sum(nums, target):
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]