0

Suppose you have an interface like so (Java example):

interface ImmutableMap<K,V> {
   V get(K key);
}

One way to implement it would be to use a hash table (HashMap), which gives O(1) average performance assuming a good hash function, and O(n) worst case.

However a hash table is mutable - it also allows removing and putting elements in the map - which may mean compromises are being made in the performance of get, for the sake of making put and delete faster.

So the question is - what improvements could be made for just implementing get - perhaps O(1) worst case, or just better general performance (e.g. by a factor of 2) if not asymptotically faster?

greybeard
  • 2,249
  • 8
  • 30
  • 66
Fudge Fudge
  • 1,024
  • 1
  • 10
  • 25
  • 1
    https://en.wikipedia.org/wiki/Perfect_hash_function – Matt Timmermans Jan 31 '22 at 17:31
  • https://stackoverflow.com/questions/70925012/perfect-hash-function-for-random-integer/70926647#70926647 – Matt Timmermans Jan 31 '22 at 17:36
  • If you got the perfect implementation but for immutability, use [`Collections.unmodifiableMap(java.util.Map)`](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Collections.html#unmodifiableMap(java.util.Map)). – greybeard Jan 31 '22 at 17:36
  • (Contemporary implementations using hashing may use balanced trees for bins over some threshold.) – greybeard Jan 31 '22 at 17:38
  • I'm looking for a practical solution (perfect hashing is not practical - https://stackoverflow.com/a/29778785/7773885) and for something not language dependant. – Fudge Fudge Feb 01 '22 at 08:41

1 Answers1

0

A hashtable that uses cuckoo hashing is guaranteed at most one miss (for an item present in the hashtable) and at most two misses (for an item not present in the hashtable) on a lookup in the worst-case. The trade-off is that insertions are slightly slower, but still the same complexity as regular hash table insertions. And while the worst case is guaranteed O(1), on average lookups are still 20%-30% slower compared to linear probing for cache-related reasons (ref: https://en.wikipedia.org/wiki/Cuckoo_hashing).

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118