Removing the first half of the entries in LinkedHashMap other than looping

user_455796 0
Viewed 78

I was going to use Hashtable but some existing answer said only LinkedHashMap preserve the insertion order. So, it seems that I can get the insertion order with the entries or keys properties.

My question is, when the map has n elements, if I want to remove the first n/2 elements, is there a better way than looping through the keys and repeatedly calling remove(key)? That is, something like this

val a = LinkedHashMap<Int, Int>();
val n = 10;
for(i in 1 .. n)
{
    a[i] = i*10;
}
a.removeRange(0,n/2);

instead of

val a = LinkedHashMap<Int, Int>();
val n = 10;
for(i in 1 .. n)
{
    a[i] = i*10;
}

var i = 0;
var keysToRemove= ArrayList<Int>();
for(k in a.keys)
{
    if(i >= n/2)
        break;
    else
        i++

    keysToRemove.add(k);
}

for(k in keysToRemove)
{
    a.remove(k);
}

The purpose of this is that I use the map as a cache, and when the cache is full, I want to purge the oldest half of the entries. I do not have to use LinkedHashMap as long as I can:

  • Find the value using a key, efficiently.
  • Remove a range of entries at once.
kotlin linkedhashmap dictionary
2 Answers

EDIT: sorry I missed the part about using this as an LRU cache, for that use case, TreeMap will not be suitable.

If insertion order is just incidental for you, and what you want is in fact the actual order of comparable keys, you should use a TreeMap instead.

However, the specific use case of removing half the keys might not be supported directly. You will rather find methods to remove keys below/above a certain value, and get the highest/lowest keys.

user_15408180

There's no method in the class that makes this possible. The source code doesn't have any operations for ranges of keys or entries. Since the linking is built on top of the HashMap logic, individual entries still have to be individuatlly found by a hashed key lookup to remove them, so being able to remove a range couldn't be done faster in a LinkedHashMap, which is unlike the analogy of a LinkedList to an ArrayList.

For simpler code that's equivalent to what you're doing:

a.keys.take(a.size / 2).forEach(a::remove)

If you don't want to use a library for a cache set, LinkedHashSet is designed so you can easily build your own by subclassing. For instance, a basic one that simply removes the oldest entry when you add elements above a certain collection size:

class CacheHashMap<K, V>(private var maxSize: Int): LinkedHashMap<K, V>() {
    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<K, V>?): Boolean =
        size == maxSize
}

Also, if you set accessOrder to true in your constructor call, it orders by last used to most recently used entry, which might be more apt for your situation than insertion order.

user_5067960
Related