CODEWITHSUNDEEP
javaalgorithmdata-structureshashtable
Joel
Joel

Reputation: 3454

Hashtable with limited size?

For managing some cache, I need a sort of Hashtable with the ability to remove the oldest elements in order to keep the MAXSIZE last elements in the table. I need to program this in Java but any algorithm with pseudo code would be fine too.

public interface LimitedHashtable<K, V> {
    void put(K k, V v); // will remove the oldest element from the table if size > MAXSIZE
    V get(K k);
}

Any idea?

Upvotes: 1

Views: 1670

Answers (4)

Tim Bender
Tim Bender

Reputation: 20442

You want a LinkedHashMap. You'll have to add some hooks to remove entries when that map gets too big.

Upvotes: 1

Paul Bellora
Paul Bellora

Reputation: 55213

Consider using Guava's CacheBuilder, which offers a maximumSize() amongst other options. Note that this behavior is more nuanced than what you might be looking for:

Specifies the maximum number of entries the cache may contain. Note that the cache may evict an entry before this limit is exceeded. As the cache size grows close to the maximum, the cache evicts entries that are less likely to be used again. For example, the cache may evict an entry because it hasn't been used recently or very often.

Upvotes: 3

yshavit
yshavit

Reputation: 43391

Take a look at LinkedHashMap with an overridden removeEldestEntry -- if it returns size() > MAXSIZE, you'll have what you want. One of LinkedHashMap's constructors also has a boolean that says whether the "oldest" entry means the one that was added longest ago, or the one that was accessed longest ago.

Upvotes: 4

ControlAltDel
ControlAltDel

Reputation: 35011

The only way I know is to keep a queue of the keys in your hash, and use that to expel keys when the table & queue get too big

Upvotes: 3

Related Questions