average O(1) vs worst O(n)

Source board

This definition comes from the board below. Open it to see the term in context.

HashingDSA

More terms from this board

• bucketan array slot
• chainingbucket holds a linked list
• collisiontwo keys → same bucket (inevitable, pigeonhole)
• 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