We build a stack, a ring-buffer queue and a chained hash map in Python, then port the hash map core (put, get, resize) to C++, Java and TypeScript. In real code you would use list, deque and dict; writing them once shows what those types do for you.
Stack and queue in Python
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item)
def pop(self):
if not self._items:
raise IndexError("pop from empty stack")
return self._items.pop()
def peek(self):
return self._items[-1]
class Queue:
def __init__(self, capacity=4):
self._slots = [None] * capacity
self._head = 0 # index of the oldest item
self._size = 0
def enqueue(self, item):
if self._size == len(self._slots):
self._grow()
tail = (self._head + self._size) % len(self._slots)
self._slots[tail] = item
self._size += 1
def dequeue(self):
if self._size == 0:
raise IndexError("dequeue from empty queue")
item = self._slots[self._head]
self._slots[self._head] = None # drop the reference
self._head = (self._head + 1) % len(self._slots)
self._size -= 1
return item
def _grow(self):
n = len(self._slots)
ordered = [self._slots[(self._head + i) % n] for i in range(self._size)]
self._slots = ordered + [None] * n # double, oldest first
self._head = 0
def __len__(self):
return self._size
s, q = Stack(), Queue()
for x in range(6):
s.push(x)
q.enqueue(x)
print(s.pop(), q.dequeue(), len(q)) # 5 0 5
How it works, line by line:
Stack only touches the end of a list, so push and pop are O(1) amortized.Queue keeps the oldest item's index in _head and derives the tail as (_head + _size) % capacity. Storing a size avoids the ambiguity where head == tail could mean empty or full.dequeue clears the slot so the queue does not keep the object alive._grow copies items in queue order into a doubled array and resets _head to 0.
Hash map with separate chaining in Python
class HashMap:
def __init__(self, capacity=8, max_load=0.75):
self._buckets = [[] for _ in range(capacity)]
self._size = 0
self._max_load = max_load
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: # existing key: replace the value
bucket[i] = (key, value)
return
bucket.append((key, value))
self._size += 1
if self._size / len(self._buckets) > self._max_load:
self._resize(2 * len(self._buckets))
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
def remove(self, key):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i)
self._size -= 1
return True
return False
def _resize(self, capacity):
old = self._buckets
self._buckets = [[] for _ in range(capacity)]
for bucket in old:
for key, value in bucket:
self._bucket(key).append((key, value))
def __len__(self):
return self._size
m = HashMap()
for word in "the quick brown fox jumps over the lazy dog the end".split():
m.put(word, m.get(word, 0) + 1)
print(m.get("the"), m.get("cat"), len(m), len(m._buckets)) # 3 None 9 16
0 則留言
登入 · 登入後即可留言。