linear probing+alternatives #phrasebook

collision — Each hash table has a hash collision resolution strategy. Common choices include separate-chaining (SC), linear-probing (LP), double-hashing (DH)

  • cache — In terms of CPU d-cache efficiency, linear probing beats quadratic-probing which beats separate-chaining. CPU cache efficiency is more relevant for very hot data content.
  • clustering — Like street-parking, this can hurt linear probing. Quadratic-probing and double-hashing can cope better.
  • failure — failing to locate an open slot (when available) is a problem with quadratic probing. DH, LP and SC are guaranteed safe.
  • open-addressing — is alternative to chaining. It includes LP, DH etc.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s