Dictionary with limited size that removes oldest elements?

Question

Is there an existing data structure usable for hashing data that will give ability to delete the oldest element?

The approach that I am thinking of right now is to have a Dictionary and a Queue having fast lookup using the Dictionary and being able to delete oldest element from the Dictionary using a Queue.

Will you need to remove elements other than the oldest? And will you need to store a lot of elements - in other words, how important is performance on such deletes? — Tomas Aschan, Apr 02 '13 at 00:23
What type of Data with this potential collection be storing..? — MethodMan, Apr 02 '13 at 00:23
To delete the oldest element you need a set size or time to... — Cole Tobin, Apr 02 '13 at 00:27
You may want a circular buffer. maybe see http://stackoverflow.com/questions/590069/how-would-you-code-an-efficient-circular-buffer-in-java-or-c-sharp — Cheeso, Apr 02 '13 at 00:27
Wouldn't an `OrderedDictionary` be useful here? http://msdn.microsoft.com/en-us/library/ms132577.aspx — keyboardP, Apr 02 '13 at 00:28
@keyboardP, I think your comment satisfies current requirements (also removal of first entry will likely be O(n) ). — Alexei Levenkov, Apr 02 '13 at 00:38
I have edited your title. Please see, "[Should questions include “tags” in their titles?](http://meta.stackexchange.com/questions/19190/)", where the consensus is "no, they should not". — John Saunders, Apr 02 '13 at 00:38
@AlexeiLevenkov - Yup, assuming there's no other criterion I think an OrderedDictionary will be a good option for this. — keyboardP, Apr 02 '13 at 00:43

score 16 · Accepted Answer · answered Apr 02 '13 at 00:41

16

You can use an OrderedDictionary. This will maintain insertion order (unlike a SortedDictionary which will be ordered by keys). You can then remove the first available element which would considered the oldest.

answered Apr 02 '13 at 00:41

keyboardP

68,824
13
156
205

5

+1. Note that removal of first element is O(n), which may be ok as question does not specify any timing requirements for that operation. – Alexei Levenkov Apr 02 '13 at 00:45
@AlexeiLevenkov - Good point. Also to OP, if optimization is key then it may be worth testing capacity sizes to initialize the OrderedDictionary with http://www.dotnetperls.com/dictionary-optimization (although the article relates to the standard Dictionary collection, the principle should still apply) – keyboardP Apr 02 '13 at 00:55

Nick · Answer 2 · 2021-03-24T12:02:20.433

An OrderedDictionary is a good suggestion, but if you need types other than a string in your dictionary, try this;

public sealed class SizedDictionary<TKey, TValue> : Dictionary<TKey, TValue> {

private int maxSize;
private Queue<TKey> keys;

public SizedDictionary(int size) {
    maxSize = size;
    keys = new Queue<TKey>();
}

new public void Add (TKey key, TValue value) {
    if (key==null) throw new ArgumentNullException();
    base.Add(key, value);
    keys.Enqueue(key);
    if (keys.Count > maxSize) base.Remove(keys.Dequeue());
}

new public bool Remove (TKey key) {
    if (key==null) throw new ArgumentNullException();
    if (!keys.Contains(key)) return false;
    var newQueue = new Queue<TKey>();
    while (keys.Count>0) {
        var thisKey = keys.Dequeue();
        if (!thisKey.Equals(key)) newQueue.Enqueue(thisKey);
    }
    keys=newQueue;
    return base.Remove(key);
}
}

I'm using a sealed class because we are just hiding the add and remove methods, so if this class were to be inherited it wouldn't be clear which version was used. A more complete solution would use an internal dictionary and not inherit, but that would be a lot more long winded

score 0 · Answer 3 · answered Apr 02 '13 at 00:44

System.Collections.Generic.SortedList is just a dictionary that sorts by key. If the key is temporal in some way, you can simply use RemoveAt to remove the first element when you reach a certain size when you want to add another entry.

Likely, since you mentioned Dictionary, you probably don't have a temporal key. But, a Dictionary is just a collection of KeyValuePair<K,V> objects. So, you could have a sorted list where the value is a KeyValuePair<K,V> and the key is the date/time the element was added.

score 0 · Answer 4 · answered Apr 02 '13 at 01:13

0

Since you have a specific requirement I'd implement the Dictionary with a Queue / Buffer behind (e.g. circular buffer mentioned in comments).

OrderedDictionary is a good choice and a good source on how to do that (I don't want to post it here but you can find it easily) - you just need something better than an ArrayList to hold your elements (and do the dequeueing)- since you're constantly removing the 'first'.

answered Apr 02 '13 at 01:13

NSGaga-mostly-inactive

14,052
3
41
51

1

"_a good source on how to do that (I don't want to post it here but you can find it easily)_" -- is there a specific, secret source for understanding `OrderedDictionary`s I should be looking for here? – ruffin Apr 19 '19 at 19:31
1

@ruffin what I meant is go google (or duckduckgo:) "OrderedDictionary source code" or something of that sort. If I remember correctly (it was many yrs ago) the actual OrderedDictionary implementation can show you how to whip up your own specific dictionary for specific purposes. I didn't want to post the link as at that time .NET was closed source. – NSGaga-mostly-inactive Apr 19 '19 at 20:32
Gotcha. Was confused why you needed "a good source" for one [as if MS' was broken](https://learn.microsoft.com/en-us/dotnet/api/system.collections.specialized.ordereddictionary?redirectedfrom=MSDN&view=netframework-4.8#methods), but you literally meant [get some good source \[code\] for one](https://github.com/microsoft/referencesource/blob/3b1eaf5203992df69de44c783a3eda37d3d4cd10/System/compmod/system/collections/specialized/ordereddictionary.cs). Thanks! – ruffin May 13 '19 at 18:54

Dictionary with limited size that removes oldest elements?

4 Answers4