Guida a Strutture dati di base · 3/6
Per ora questo capitolo è disponibile solo in inglese.
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.
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 5How 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.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_bucket maps a key to hash(key) % capacity. Python's % is non-negative for a positive divisor, so negative hashes are safe.put scans the chain first; updating an existing key must not grow _size._resize reinserts every pair because the index depends on the capacity.get and remove hash once and scan one short chain: O(1) on average.#include <functional>
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>
template <typename K, typename V>
class HashMap {
std::vector<std::list<std::pair<K, V>>> buckets_;
std::size_t size_ = 0;
std::size_t index(const K& key, std::size_t n) const { return std::hash<K>{}(key) % n; }
void resize(std::size_t capacity) {
std::vector<std::list<std::pair<K, V>>> next(capacity);
for (auto& bucket : buckets_)
for (auto& kv : bucket) next[index(kv.first, capacity)].push_back(std::move(kv));
buckets_.swap(next);
}
public:
explicit HashMap(std::size_t capacity = 8) : buckets_(capacity) {}
void put(const K& key, const V& value) {
auto& bucket = buckets_[index(key, buckets_.size())];
for (auto& kv : bucket)
if (kv.first == key) { kv.second = value; return; }
bucket.emplace_back(key, value);
if (++size_ * 4 > buckets_.size() * 3) resize(buckets_.size() * 2); // load factor 0.75
}
const V* get(const K& key) const {
for (const auto& kv : buckets_[index(key, buckets_.size())])
if (kv.first == key) return &kv.second;
return nullptr;
}
std::size_t size() const { return size_; }
};
int main() {
HashMap<std::string, int> ages;
ages.put("ada", 36);
ages.put("ada", 37);
ages.put("alan", 41);
std::cout << *ages.get("ada") << ' ' << ages.size() << ' ' << (ages.get("bob") == nullptr) << '\n'; // 37 2 1
}get returns a null pointer for a missing key, and the load-factor check size * 4 > capacity * 3 stays in integer arithmetic. remove would be the same scan followed by erase.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
public class ChainedHashMap<K, V> {
private record Entry<K, V>(K key, V value) {}
private List<LinkedList<Entry<K, V>>> buckets = newBuckets(8);
private int size = 0;
private static <K, V> List<LinkedList<Entry<K, V>>> newBuckets(int n) {
List<LinkedList<Entry<K, V>>> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) list.add(new LinkedList<>());
return list;
}
private LinkedList<Entry<K, V>> bucket(K key) {
return buckets.get(Math.floorMod(Objects.hashCode(key), buckets.size()));
}
public void put(K key, V value) {
var bucket = bucket(key);
for (var it = bucket.listIterator(); it.hasNext(); ) {
if (Objects.equals(it.next().key(), key)) { it.set(new Entry<>(key, value)); return; }
}
bucket.add(new Entry<>(key, value));
if (++size * 4 > buckets.size() * 3) resize(buckets.size() * 2);
}
public V get(K key) {
for (var e : bucket(key)) if (Objects.equals(e.key(), key)) return e.value();
return null;
}
private void resize(int capacity) {
var old = buckets;
buckets = newBuckets(capacity);
for (var b : old) for (var e : b) bucket(e.key()).add(e);
}
public int size() { return size; }
public static void main(String[] args) {
var m = new ChainedHashMap<String, Integer>();
for (var w : "to be or not to be".split(" ")) m.put(w, m.get(w) == null ? 1 : m.get(w) + 1);
System.out.println(m.get("be") + " " + m.size()); // 2 4
}
}Math.floorMod matters: hashCode() can be negative, and Java's % would then produce a negative index.
class ChainedHashMap<V> {
private buckets: [string, V][][] = Array.from({ length: 8 }, () => []);
private count = 0;
private hash(key: string): number {
let h = 2166136261; // FNV-1a, 32-bit
for (let i = 0; i < key.length; i++) {
h ^= key.charCodeAt(i);
h = Math.imul(h, 16777619);
}
return h >>> 0; // unsigned
}
private bucket(key: string): [string, V][] {
return this.buckets[this.hash(key) % this.buckets.length];
}
put(key: string, value: V): void {
const bucket = this.bucket(key);
const entry = bucket.find(([k]) => k === key);
if (entry) { entry[1] = value; return; }
bucket.push([key, value]);
if (++this.count > this.buckets.length * 0.75) this.resize(this.buckets.length * 2);
}
get(key: string): V | undefined {
return this.bucket(key).find(([k]) => k === key)?.[1];
}
private resize(capacity: number): void {
const old = this.buckets;
this.buckets = Array.from({ length: capacity }, () => []);
for (const bucket of old) for (const [k, v] of bucket) this.bucket(k).push([k, v]);
}
get size(): number { return this.count; }
}
const m = new ChainedHashMap<number>();
for (const w of "a b a c b a".split(" ")) m.put(w, (m.get(w) ?? 0) + 1);
console.log(m.get("a"), m.size); // 3 3JavaScript exposes no hash for arbitrary values, so this version takes string keys and hashes them with FNV-1a; Math.imul keeps the product in 32 bits and >>> 0 makes it unsigned.
A stack is a thin wrapper over a dynamic array, a queue becomes O(1) on both ends with a ring buffer, and a hash map is an array of short chains that doubles when the load factor passes a threshold. The four ports share the same three steps: hash the key, reduce it to a bucket index, scan one chain.
0 commenti
Accedi · Accedi per lasciare un commento.