基础数据结构

data_structures.py

from collections import deque


class HashMap:
    """Separate chaining: each bucket is a list of (key, value) pairs."""

    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > 0.75 * len(self.buckets):  # load factor limit
            old = self.buckets
            self.buckets = [[] for _ in range(2 * len(old))]
            for pairs in old:
                for k, v in pairs:
                    self._bucket(k).append((k, v))

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default


stack = [1, 2, 3]
stack.append(4)
print("stack pop:", stack.pop())        # 4 (LIFO)

queue = deque([1, 2, 3])
queue.append(4)
print("queue popleft:", queue.popleft())  # 1 (FIFO)

ages = HashMap()
for name, age in [("ada", 36), ("alan", 41), ("grace", 85)]:
    ages.put(name, age)
ages.put("ada", 37)
print("ada:", ages.get("ada"), "size:", ages.size)  # ada: 37 size: 3

python data_structures.py