Class SplayMap<E>

  • Type Parameters:
    E - The type stored in the map entries
    All Implemented Interfaces:
    Map<UnsignedInteger,​E>, NavigableMap<UnsignedInteger,​E>, SortedMap<UnsignedInteger,​E>
    Direct Known Subclasses:
    LinkedSplayMap

    public class SplayMap<E>
    extends Object
    implements NavigableMap<UnsignedInteger,​E>
    Map class that is implemented using a Splay Tree and uses primitive integers as the keys for the specified value type. The splay tree is a specialized form of a binary search tree that is self balancing and provides faster access in general to frequently used items. The splay tree serves well as an LRU cache of sorts where 80 percent of the accessed elements comes from 20 percent of the overall load in the Map. The best case access time is generally O(long n) however it can be Theta(n) in a very worst case scenario.