CODEWITHSUNDEEP
algorithmhashtableaddressing
onno
onno

Reputation: 1391

What is the name for this hash table optimization?

While implementing a custom hash table with open addressing, I discovered that for my application, it helps performance if I swap the probed element in a row of filled slots with the one in the first probe location. (To optimize the table to quicker yield often-accessed elements)

Is there a name for this optimization?

Upvotes: 2

Views: 147

Answers (2)

Ami Tavory
Ami Tavory

Reputation: 76317

Your problem is very similar to the list update problem from the field of online-competitive algorithms.

The solution you used is known as MTF (move to front). This solution is known to be 2-competitive, meaning that it will do at most twice as bad as a hypothetical adversary which knows the future in advance.

Note that you can do slightly better than that with the bit algorithm, which requires another bit + random op, but is 7-4 competitive.

Upvotes: 1

nwellnhof
nwellnhof

Reputation: 33638

The most general term for this kind of optimization is probably self-organization.

Upvotes: 1

Related Questions