Posts tagged “Data Structures”
8 posts Subscribe by RSS
8 posts
Jump consistent hash: picking a shard number without a lookup table, and what it assumes
Growing from 10 to 12 shards, hash mod n moves 5/6 of the keys; only 1/6 has to move. Lamping and Veach's code, why it works, and what adding or removing buckets does.
Union-find path compression and weighting: which implementation the α(n) bound belongs to
How size weighting, path compression and path halving change a union-find parent array, and which bound, worst-case Θ(log n) or O(m α(n)) per sequence, algs4 gives each implementation.
The Linux kernel rbtree: a red-black tree with embedded nodes and no stored comparator
Linux's red-black tree never stores a comparator. Embedded nodes, your own search loop, helpers taking per-call compare functions, colour bits, cached and augmented trees, lockless lookup in v6.17.
Skip lists: how coin-flip levels give O(log n) expected search
Why does adding random-level pointers to a sorted linked list make search O(log n) expected? Pugh's algorithms, what 'expected' covers, and what Java's ConcurrentSkipListMap docs promise.
When is a hash table not O(1)? Collisions, O(n²) inserts and hash flooding
dict and HashMap are O(1) in expectation. Why n keys with one hash value need at least n(n−1)/2 comparisons. Python hash randomization and PYTHONHASHSEED, Rust's SipHash, Java's Comparable fallback.
Why a Bloom filter is only ever sure about "no"
Why a Bloom filter answers only "definitely not" or "possibly", the conditions behind its no-false-negative guarantee, the false positive formula, and why deleting bits breaks it.
A heap is not a sorted list: priority queue order and the 0-based index formulas
Why doesn't a printed heapq list or PriorityQueue look sorted? The heap invariant, 0-based parent/child formulas, costs versus a sorted list, and equal priorities.
Why appending to a dynamic array is O(1): capacity, growth and amortized time
Append sometimes copies the whole array, yet it counts as O(1). Capacity, amortized cost, what the Java, C++, Rust and Go docs promise, and reserving space.
No posts match. Try another word.