哈希表

values[key] = value

index = hash(key) % capacity

_MISSING = object()


class ChainedHashMap:
    def __init__(self, capacity=8, max_load_factor=0.75):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        if not 0 < max_load_factor < 1:
            raise ValueError("max_load_factor must be between 0 and 1")
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        self._max_load_factor = max_load_factor

    def __len__(self):
        return self._size

    def _index(self, key):
        # 不可哈希 key 会在这里抛 TypeError
        return hash(key) % len(self._buckets)

    def _find_in_bucket(self, bucket, key):
        for position, (stored_key, value) in enumerate(bucket):
            if stored_key == key:
                return position, value
        return None, _MISSING

    def put(self, key, value):
        bucket = self._buckets[self._index(key)]
        position, _ = self._find_in_bucket(bucket, key)

        if position is not None:
            bucket[position] = (key, value)  # 覆盖，不增加 size
            return False

        bucket.append((key, value))
        self._size += 1
        if self._size / len(self._buckets) > self._max_load_factor:
            self._resize(len(self._buckets) * 2)
        return True

    def get(self, key, default=_MISSING):
        bucket = self._buckets[self._index(key)]
        _, value = self._find_in_bucket(bucket, key)
        if value is not _MISSING:
            return value
        if default is not _MISSING:
            return default
        raise KeyError(key)

    def contains(self, key):
        bucket = self._buckets[self._index(key)]
        position, _ = self._find_in_bucket(bucket, key)
        return position is not None

    def remove(self, key):
        bucket = self._buckets[self._index(key)]
        position, value = self._find_in_bucket(bucket, key)
        if position is None:
            raise KeyError(key)
        bucket.pop(position)
        self._size -= 1
        return value

    def items(self):
        for bucket in self._buckets:
            yield from bucket

    def _resize(self, new_capacity):
        old_items = list(self.items())
        self._buckets = [[] for _ in range(new_capacity)]
        for key, value in old_items:
            bucket = self._buckets[self._index(key)]
            bucket.append((key, value))

_EMPTY = object()
_DELETED = object()


class ProbingHashMap:
    def __init__(self, capacity=8, max_load_factor=0.7):
        if capacity < 1:
            raise ValueError("capacity must be positive")
        if not 0 < max_load_factor < 1:
            raise ValueError("max_load_factor must be between 0 and 1")
        self._table = [_EMPTY] * capacity
        self._size = 0          # 有效 key/value 数量
        self._used = 0          # 有效元素 + 墓碑数量
        self._max_load_factor = max_load_factor

    def __len__(self):
        return self._size

    def _start(self, key):
        return hash(key) % len(self._table)

    def _locate(self, key):
        capacity = len(self._table)
        start = self._start(key)
        for step in range(capacity):
            index = (start + step) % capacity
            slot = self._table[index]
            if slot is _EMPTY:
                return None
            if slot is not _DELETED and slot[0] == key:
                return index
        return None

    def _slot_for_insert(self, key):
        capacity = len(self._table)
        start = self._start(key)
        first_deleted = None

        for step in range(capacity):
            index = (start + step) % capacity
            slot = self._table[index]
            if slot is _EMPTY:
                return first_deleted if first_deleted is not None else index
            if slot is _DELETED:
                if first_deleted is None:
                    first_deleted = index
            elif slot[0] == key:
                return index

        return first_deleted

    def put(self, key, value):
        # _used 包含墓碑，避免探测空间被墓碑耗尽
        if (self._used + 1) / len(self._table) > self._max_load_factor:
            self._resize(len(self._table) * 2)

        index = self._slot_for_insert(key)
        if index is None:
            self._resize(len(self._table) * 2)
            index = self._slot_for_insert(key)

        old_slot = self._table[index]
        is_new = old_slot is _EMPTY or old_slot is _DELETED
        if old_slot is _EMPTY:
            self._used += 1
            self._size += 1
        elif old_slot is _DELETED:
            self._size += 1

        self._table[index] = (key, value)
        return is_new

    def get(self, key, default=_MISSING):
        index = self._locate(key)
        if index is not None:
            return self._table[index][1]
        if default is not _MISSING:
            return default
        raise KeyError(key)

    def contains(self, key):
        return self._locate(key) is not None

    def remove(self, key):
        index = self._locate(key)
        if index is None:
            raise KeyError(key)
        value = self._table[index][1]
        self._table[index] = _DELETED
        self._size -= 1
        return value

    def _resize(self, new_capacity):
        old_items = [
            slot for slot in self._table
            if slot is not _EMPTY and slot is not _DELETED
        ]
        self._table = [_EMPTY] * new_capacity
        self._size = 0
        self._used = 0
        for key, value in old_items:
            self.put(key, value)

    def items(self):
        for slot in self._table:
            if slot is not _EMPTY and slot is not _DELETED:
                yield slot

class UserKey:
    def __init__(self, user_id):
        self.user_id = user_id

    def __hash__(self):
        return hash(self.user_id)

    def __eq__(self, other):
        return isinstance(other, UserKey) and self.user_id == other.user_id


key = UserKey(1)
table = ChainedHashMap()
table.put(key, "alice")
key.user_id = 2
# key 仍在旧 bucket，但查找会按新 hash 去另一个位置

class BadHash:
    def __init__(self, name):
        self.name = name

    def __hash__(self):
        return 1  # 所有 key 强制落在同一初始槽位

    def __eq__(self, other):
        return isinstance(other, BadHash) and self.name == other.name


def exercise(map_type):
    table = map_type(capacity=4)
    a, b, c = BadHash("a"), BadHash("b"), BadHash("c")

    assert table.put(a, 1) is True
    assert table.put(b, 2) is True       # 触发冲突
    assert table.put(c, 3) is True       # 继续冲突，并可能扩容
    assert table.put(b, 20) is False     # 覆盖，不增加 size
    assert len(table) == 3
    assert table.get(b) == 20

    assert table.remove(a) == 1
    assert table.get(b) == 20            # 开放寻址不能被墓碑截断
    assert table.get(BadHash("x"), "missing") == "missing"


exercise(ChainedHashMap)
exercise(ProbingHashMap)

d = {"apple": 3, "banana": 5}
d["cherry"] = 7           # 增
d["apple"] = 10           # 改（覆盖旧值）
val = d.get("grape", 0)   # 查，不存在返回默认值
del d["banana"]           # 删
val = d.pop("cherry", None)
if "apple" in d:          # 判断键是否存在
    print(d["apple"])

for k, v in d.items():    # 遍历键值对；也可用 .keys()、.values()
    print(k, v)

squared = {x: x ** 2 for x in [1, 2, 3, 4]}
# {1: 1, 2: 4, 3: 9, 4: 16}

from collections import Counter

cnt = Counter(["apple", "banana", "apple", "cherry", "banana", "apple"])
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})

cnt["grape"]               # 不存在返回 0，不抛异常
cnt.most_common(2)         # [('apple', 3), ('banana', 2)]

freq = Counter("abracadabra")  # 字符频率统计
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

from collections import defaultdict

# defaultdict(int)：默认值 0，适合计数
counter = defaultdict(int)
for ch in "hello":
    counter[ch] += 1  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

# defaultdict(list)：默认值空列表，适合分组
groups = defaultdict(list)
for category, item in [("fruit", "apple"), ("fruit", "banana"), ("veggie", "carrot")]:
    groups[category].append(item)

# defaultdict(set)：去重分组，常用于建图
graph = defaultdict(set)
for u, v in [(1, 2), (1, 3), (2, 3)]:
    graph[u].add(v)
    graph[v].add(u)

s = set([1, 2, 2, 3])     # 自动去重 -> {1, 2, 3}
s.add(4)
s.discard(2)               # 不存在也不报错
if 3 in s:                 # O(1) 成员检查
    print("found")

a, b = {1, 2, 3, 4}, {3, 4, 5, 6}
a & b   # 交集 {3, 4}
a | b   # 并集 {1, 2, 3, 4, 5, 6}
a - b   # 差集 {1, 2}
a ^ b   # 对称差集 {1, 2, 5, 6}

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

    def __hash__(self):
        return hash(self.value)

    def __eq__(self, other):
        return isinstance(other, StableKey) and self.value == other.value


first = StableKey("same")
second = StableKey("same")
table = ChainedHashMap()
table.put(first, 1)
table.put(second, 2)
assert len(table) == 1
assert table.get(first) == 2

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # val -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))
        groups[key].append(s)
    return list(groups.values())

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix_sum = 0
    prefix_count = defaultdict(int)
    prefix_count[0] = 1  # 空前缀
    for num in nums:
        prefix_sum += num
        count += prefix_count[prefix_sum - k]
        prefix_count[prefix_sum] += 1
    return count

def find_anagrams(s: str, p: str) -> list[int]:
    if len(s) < len(p):
        return []
    p_count = Counter(p)
    s_count = Counter(s[:len(p)])
    result = []
    if s_count == p_count:
        result.append(0)
    for i in range(len(p), len(s)):
        # 右端加入
        s_count[s[i]] += 1
        # 左端移出
        left = s[i - len(p)]
        s_count[left] -= 1
        if s_count[left] == 0:
            del s_count[left]
        if s_count == p_count:
            result.append(i - len(p) + 1)
    return result