As I think of data structures I studied and dealt with, they are all optimized to retrieve/put a random element, to perform optimally based on unspoken assumption that each element has equal odds of being asked for (e.g. Red-Black trees).
By the nature of my program, I need to maintain an online dictionary of items that typically serves items that were added last.
That is, the later an item has been added, the higher the likelihood of it being retrieved back in the nearest future.
Speaking more formally, let's define a set $S$ of pair $(k_i, d_i)$, where $k_i \in K $ and $K$ has a comparison operator $\leq$ defined, $d_i \in D$. Let $p(k)$ be the probability of our need to retrieve pair $(k, d)$.
What is an efficient way to store $S$ with regard to function $p$ ?