DSA
collision
two keys → same bucket (inevitable, pigeonhole)
Source board
This definition comes from the board below. Open it to see the term in context.
HashingDSAMore terms from this board
- average O(1) vs worst O(n)typical vs all-collide
- bucketan array slot
- chainingbucket holds a linked list
- hash functionarbitrary input → fixed-size int (fast, uniform, deterministic)
- hash joinbuild-a-map + probe
- hash set / mapkeys only / key→value
- hash tablekey→index→bucket store
- HashDoSadversarial colliding keys forcing O(n)
- load factor αentries/buckets
- open addressingprobe for the next free slot (linear/quadratic/double hash)
- resize/rehashgrow the table & re-place keys (amortized O(1))
- SipHasha keyed hash that defeats it