LruHashMap (Apache HBase 1.2.12 API)

java.lang.Object
- org.apache.hadoop.hbase.regionserver.LruHashMap<K,V>

All Implemented Interfaces:

Map<K,V>, HeapSize
```
@InterfaceAudience.Private
public class LruHashMap<K extends HeapSize,V extends HeapSize>
extends Object
implements HeapSize, Map<K,V>
```
The LruHashMap is a memory-aware HashMap with a configurable maximum memory footprint.
It maintains an ordered list of all entries in the/ map ordered by access time. When space needs to be freed becase the maximum has been reached, or the application has asked to free memory, entries will be evicted according to an LRU (least-recently-used) algorithm. That is, those entries which have not been accessed the longest will be evicted first.
Both the Key and Value Objects used for this class must extend HeapSize in order to track heap usage.
This class contains internal synchronization and is thread-safe.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

protected static class LruHashMap.Entry<K extends HeapSize,V extends HeapSize>
Entry to store key/value mappings.

Nested Classes
Modifier and Type	Class and Description
`protected static class`	`LruHashMap.Entry<K extends HeapSize,V extends HeapSize>` Entry to store key/value mappings.

Field Summary

Fields
Modifier and Type	Field and Description
`private static int`	`DEFAULT_INITIAL_CAPACITY` The default capacity of the hash table
`private static float`	`DEFAULT_LOAD_FACTOR` The default load factor to use
`private static long`	`DEFAULT_MAX_MEM_USAGE` The default size (in bytes) of the LRU
`private LruHashMap.Entry[]`	`entries` Entries in the map
`private LruHashMap.Entry<K,V>`	`headPtr` Pointer to least recently used entry
`private long`	`hitCount` Number of successful (found) get() calls
`private float`	`loadFactor` Load factor allowed (usually 75%)
`private static org.apache.commons.logging.Log`	`LOG`
`private static int`	`MAXIMUM_CAPACITY` The maxmum capacity of the hash table
`private long`	`memFree` Amount of available memory
`private long`	`memTotal` Maximum memory usage of this map
`private long`	`missCount` Number of unsuccessful (not found) get() calls
`private static int`	`OVERHEAD` Memory overhead of this Object (for HeapSize)
`private int`	`size` Number of key/vals in the map
`private LruHashMap.Entry<K,V>`	`tailPtr` Pointer to most recently used entry
`private int`	`threshold` Size at which we grow hash

Constructor Summary

Constructors
Constructor and Description
`LruHashMap()` Constructs a new, empty map with the default initial capacity, load factor and maximum memory usage.
`LruHashMap(int initialCapacity)` Constructs a new, empty map with the specified initial capacity and with the default load factor and maximum memory usage.
`LruHashMap(int initialCapacity, float loadFactor)` Constructs a new, empty map with the specified initial capacity and load factor, and default maximum memory usage.
`LruHashMap(int initialCapacity, float loadFactor, long maxMemUsage)` Constructs a new, empty map with the specified initial capacity, load factor, and maximum memory usage.
`LruHashMap(long maxMemUsage)` Constructs a new, empty map with the specified maximum memory usage and with default initial capacity and load factor.

Method Summary

Methods
Modifier and Type	Method and Description
`private long`	`addEntry(int hash, K key, V value, int bucketIndex)` Adds a new entry with the specified key, value, hash code, and bucket index to the map.
`private int`	`calculateCapacity(int proposedCapacity)` Calculates the capacity of the array backing the hash by normalizing capacity to a power of 2 and enforcing capacity limits.
`private int`	`calculateThreshold(int capacity, float factor)` Calculates the threshold of the map given the capacity and load factor.
`private void`	`checkAndFreeMemory(long memNeeded)` Evicts and frees based on LRU until at least as much memory as requested is available.
`private void`	`checkKey(K key)` Enforces key constraints.
`private void`	`checkValue(V value)` Enforces value constraints.
`void`	`clear()` Clears all entries from the map.
`private long`	`clearAll()` Clears all the entries in the map.
`boolean`	`containsKey(Object key)` Checks whether there is a value in the map for the specified key.
`boolean`	`containsValue(Object value)` Checks whether this is a mapping which contains the specified value.
`List<LruHashMap.Entry<K,V>>`	`entryLruList()` Debugging function that returns a List sorted by access time.
`Set<Map.Entry<K,V>>`	`entrySet()` Intentionally unimplemented.
`Set<LruHashMap.Entry<K,V>>`	`entryTableSet()` Debugging function that returns a Set of all entries in the hash table.
`boolean`	`equals(Object o)` Intentionally unimplemented.
`private long`	`evictFromLru()` Evicts based on LRU.
`long`	`freeMemory(long requestedAmount)` Free the requested amount of memory from the LRU map.
`V`	`get(Object key)` Retrieves the value associated with the specified key.
`LruHashMap.Entry`	`getHeadPtr()` Get the head of the linked list (least recently used).
`long`	`getHitCount()` Get the number of hits to the map.
`double`	`getHitRatio()` Get the hit ratio.
`long`	`getMemFree()` Get the currently available memory for this LRU in bytes.
`long`	`getMemMax()` Get the maximum memory allowed for this LRU in bytes.
`long`	`getMemUsed()` Get the currently used memory for this LRU in bytes.
`private long`	`getMinimumUsage()` Returns the minimum memory usage of the base map structure.
`long`	`getMissCount()` Get the number of misses to the map.
`LruHashMap.Entry`	`getTailPtr()` Get the tail of the linked list (most recently used).
`private void`	`growTable(int newCapacity)` Recreates the entire contents of the hashmap into a new array with double the capacity.
`private int`	`hash(Object key)` Gets the hash code for the specified key.
`int`	`hashCode()` Intentionally unimplemented.
`private int`	`hashIndex(int hashValue, int length)` Determines the index into the current hash table for the specified hashValue.
`long`	`heapSize()` The total memory usage of this map
`private void`	`init()` Set the initial heap usage of this class.
`boolean`	`isEmpty()` Checks whether the map is currently empty.
`private boolean`	`isEqual(Object x, Object y)` Compares two objects for equality.
`Set<K>`	`keySet()` Intentionally unimplemented.
`V`	`put(K key, V value)` Insert a key-value mapping into the map.
`void`	`putAll(Map<? extends K,? extends V> m)` Intentionally unimplemented.
`V`	`remove(Object key)` Deletes the mapping for the specified key if it exists.
`private void`	`removeEntry(LruHashMap.Entry<K,V> entry)` Removes the specified entry from the map and LRU structure.
`private LruHashMap.Entry<K,V>`	`removeEntryForKey(K key)` Removes and returns the entry associated with the specified key.
`int`	`size()` Gets the size (number of entries) of the map.
`private void`	`updateLru(LruHashMap.Entry<K,V> e)` Moves the specified entry to the most recently used slot of the LRU.
`Collection<V>`	`values()` Intentionally unimplemented.

Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - LOG
```
private static final org.apache.commons.logging.Log LOG
```
  - DEFAULT_MAX_MEM_USAGE
```
private static final long DEFAULT_MAX_MEM_USAGE
```
    The default size (in bytes) of the LRU
    
    See Also:
    Constant Field Values
  - DEFAULT_INITIAL_CAPACITY
```
private static final int DEFAULT_INITIAL_CAPACITY
```
    The default capacity of the hash table
    
    See Also:
    Constant Field Values
  - MAXIMUM_CAPACITY
```
private static final int MAXIMUM_CAPACITY
```
    The maxmum capacity of the hash table
    
    See Also:
    Constant Field Values
  - DEFAULT_LOAD_FACTOR
```
private static final float DEFAULT_LOAD_FACTOR
```
    The default load factor to use
    
    See Also:
    Constant Field Values
  - OVERHEAD
```
private static final int OVERHEAD
```
    Memory overhead of this Object (for HeapSize)
  - loadFactor
```
private final float loadFactor
```
    Load factor allowed (usually 75%)
  - size
```
private int size
```
    Number of key/vals in the map
  - threshold
```
private int threshold
```
    Size at which we grow hash
  - entries
```
private LruHashMap.Entry[] entries
```
    Entries in the map
  - headPtr
```
private LruHashMap.Entry<K extends HeapSize,V extends HeapSize> headPtr
```
    Pointer to least recently used entry
  - tailPtr
```
private LruHashMap.Entry<K extends HeapSize,V extends HeapSize> tailPtr
```
    Pointer to most recently used entry
  - memTotal
```
private long memTotal
```
    Maximum memory usage of this map
  - memFree
```
private long memFree
```
    Amount of available memory
  - hitCount
```
private long hitCount
```
    Number of successful (found) get() calls
  - missCount
```
private long missCount
```
    Number of unsuccessful (not found) get() calls
- Constructor Detail
  - LruHashMap
```
public LruHashMap(int initialCapacity,
          float loadFactor,
          long maxMemUsage)
```
    Constructs a new, empty map with the specified initial capacity, load factor, and maximum memory usage.
    
    Parameters:
    initialCapacity - the initial capacity
    loadFactor - the load factor
    maxMemUsage - the maximum total memory usage
    
    Throws:
    
    IllegalArgumentException - if the initial capacity is less than one
    
    IllegalArgumentException - if the initial capacity is greater than the maximum capacity
    
    IllegalArgumentException - if the load factor is <= 0
    
    IllegalArgumentException - if the max memory usage is too small to support the base overhead
  - LruHashMap
```
public LruHashMap(int initialCapacity,
          float loadFactor)
```
    Constructs a new, empty map with the specified initial capacity and load factor, and default maximum memory usage.
    
    Parameters:
    initialCapacity - the initial capacity
    loadFactor - the load factor
    
    Throws:
    
    IllegalArgumentException - if the initial capacity is less than one
    
    IllegalArgumentException - if the initial capacity is greater than the maximum capacity
    
    IllegalArgumentException - if the load factor is <= 0
  - LruHashMap
```
public LruHashMap(int initialCapacity)
```
    Constructs a new, empty map with the specified initial capacity and with the default load factor and maximum memory usage.
    
    Parameters:
    initialCapacity - the initial capacity
    
    Throws:
    
    IllegalArgumentException - if the initial capacity is less than one
    
    IllegalArgumentException - if the initial capacity is greater than the maximum capacity
  - LruHashMap
```
public LruHashMap(long maxMemUsage)
```
    Constructs a new, empty map with the specified maximum memory usage and with default initial capacity and load factor.
    
    Parameters:
    maxMemUsage - the maximum total memory usage
    
    Throws:
    
    IllegalArgumentException - if the max memory usage is too small to support the base overhead
  - LruHashMap
```
public LruHashMap()
```
    Constructs a new, empty map with the default initial capacity, load factor and maximum memory usage.
- Method Detail
  - getMemFree
```
public long getMemFree()
```
    Get the currently available memory for this LRU in bytes. This is (maxAllowed - currentlyUsed).
    
    Returns:
    currently available bytes
  - getMemMax
```
public long getMemMax()
```
    Get the maximum memory allowed for this LRU in bytes.
    
    Returns:
    maximum allowed bytes
  - getMemUsed
```
public long getMemUsed()
```
    Get the currently used memory for this LRU in bytes.
    
    Returns:
    currently used memory in bytes
  - getHitCount
```
public long getHitCount()
```
    Get the number of hits to the map. This is the number of times a call to get() returns a matched key.
    
    Returns:
    number of hits
  - getMissCount
```
public long getMissCount()
```
    Get the number of misses to the map. This is the number of times a call to get() returns null.
    
    Returns:
    number of misses
  - getHitRatio
```
public double getHitRatio()
```
    Get the hit ratio. This is the number of hits divided by the total number of requests.
    
    Returns:
    hit ratio (double between 0 and 1)
  - freeMemory
```
public long freeMemory(long requestedAmount)
                throws Exception
```
    Free the requested amount of memory from the LRU map. This will do LRU eviction from the map until at least as much memory as requested is freed. This does not affect the maximum memory usage parameter.
    
    Parameters:
    requestedAmount - memory to free from LRU in bytes
    
    Returns:
    actual amount of memory freed in bytes
    
    Throws:
    
    Exception
  - heapSize
```
public long heapSize()
```
    The total memory usage of this map
    
    Specified by:
    
    heapSize in interface HeapSize
    
    Returns:
    memory usage of map in bytes
  - get
```
public V get(Object key)
```
    Retrieves the value associated with the specified key. If an entry is found, it is updated in the LRU as the most recently used (last to be evicted) entry in the map.
    
    Specified by:
    
    get in interface Map<K extends HeapSize,V extends HeapSize>
    
    Parameters:
    key - the key
    
    Returns:
    the associated value, or null if none found
    
    Throws:
    
    NullPointerException - if key is null
  - put
```
public V put(K key,
    V value)
```
    Insert a key-value mapping into the map. Entry will be inserted as the most recently used. Both the key and value are required to be Objects and must implement the HeapSize interface.
    
    Specified by:
    
    put in interface Map<K extends HeapSize,V extends HeapSize>
    
    Parameters:
    key - the key
    value - the value
    
    Returns:
    the value that was previously mapped to this key, null if none
    
    Throws:
    
    UnsupportedOperationException - if either objects do not implement HeapSize
    
    NullPointerException - if the key or value is null
  - remove
```
public V remove(Object key)
```
    Deletes the mapping for the specified key if it exists.
    
    Specified by:
    
    remove in interface Map<K extends HeapSize,V extends HeapSize>
    
    Parameters:
    key - the key of the entry to be removed from the map
    
    Returns:
    the value associated with the specified key, or null if no mapping exists.
  - size
```
public int size()
```
    Gets the size (number of entries) of the map.
    
    Specified by:
    
    size in interface Map<K extends HeapSize,V extends HeapSize>
    
    Returns:
    size of the map
  - isEmpty
```
public boolean isEmpty()
```
    Checks whether the map is currently empty.
    
    Specified by:
    
    isEmpty in interface Map<K extends HeapSize,V extends HeapSize>
    
    Returns:
    true if size of map is zero
  - clear
```
public void clear()
```
    Clears all entries from the map. This frees all entries, tracking memory usage along the way. All references to entries are removed so they can be GC'd.
    
    Specified by:
    
    clear in interface Map<K extends HeapSize,V extends HeapSize>
  - containsKey
```
public boolean containsKey(Object key)
```
    Checks whether there is a value in the map for the specified key. Does not affect the LRU.
    
    Specified by:
    
    containsKey in interface Map<K extends HeapSize,V extends HeapSize>
    
    Parameters:
    key - the key to check
    
    Returns:
    true if the map contains a value for this key, false if not
    
    Throws:
    
    NullPointerException - if the key is null
  - containsValue
```
public boolean containsValue(Object value)
```
    Checks whether this is a mapping which contains the specified value. Does not affect the LRU. This is an inefficient operation.
    
    Specified by:
    
    containsValue in interface Map<K extends HeapSize,V extends HeapSize>
    
    Parameters:
    value - the value to check
    
    Returns:
    true if the map contains an entry for this value, false if not
    
    Throws:
    
    NullPointerException - if the value is null
  - checkKey
```
private void checkKey(K key)
```
    Enforces key constraints. Null keys are not permitted and key must implement HeapSize. It should not be necessary to verify the second constraint because that's enforced on instantiation? Can add other constraints in the future.
    
    Parameters:
    key - the key
    
    Throws:
    
    NullPointerException - if the key is null
    
    UnsupportedOperationException - if the key class does not implement the HeapSize interface
  - checkValue
```
private void checkValue(V value)
```
    Enforces value constraints. Null values are not permitted and value must implement HeapSize. It should not be necessary to verify the second constraint because that's enforced on instantiation? Can add other contraints in the future.
    
    Parameters:
    value - the value
    
    Throws:
    
    NullPointerException - if the value is null
    
    UnsupportedOperationException - if the value class does not implement the HeapSize interface
  - getMinimumUsage
```
private long getMinimumUsage()
```
    Returns the minimum memory usage of the base map structure.
    
    Returns:
    baseline memory overhead of object in bytes
  - checkAndFreeMemory
```
private void checkAndFreeMemory(long memNeeded)
```
    Evicts and frees based on LRU until at least as much memory as requested is available.
    
    Parameters:
    memNeeded - the amount of memory needed in bytes
  - evictFromLru
```
private long evictFromLru()
```
    Evicts based on LRU. This removes all references and updates available memory.
    
    Returns:
    amount of memory freed in bytes
  - updateLru
```
private void updateLru(LruHashMap.Entry<K,V> e)
```
    Moves the specified entry to the most recently used slot of the LRU. This is called whenever an entry is fetched.
    
    Parameters:
    e - entry that was accessed
  - removeEntry
```
private void removeEntry(LruHashMap.Entry<K,V> entry)
```
    Removes the specified entry from the map and LRU structure.
    
    Parameters:
    entry - entry to be removed
  - removeEntryForKey
```
private LruHashMap.Entry<K,V> removeEntryForKey(K key)
```
    Removes and returns the entry associated with the specified key.
    
    Parameters:
    key - key of the entry to be deleted
    
    Returns:
    entry that was removed, or null if none found
  - addEntry
```
private long addEntry(int hash,
            K key,
            V value,
            int bucketIndex)
```
    Adds a new entry with the specified key, value, hash code, and bucket index to the map. Also puts it in the bottom (most-recent) slot of the list and checks to see if we need to grow the array.
    
    Parameters:
    hash - hash value of key
    key - the key
    value - the value
    bucketIndex - index into hash array to store this entry
    
    Returns:
    the amount of heap size used to store the new entry
  - clearAll
```
private long clearAll()
```
    Clears all the entries in the map. Tracks the amount of memory being freed along the way and returns the total. Cleans up all references to allow old entries to be GC'd.
    
    Returns:
    total memory freed in bytes
  - growTable
```
private void growTable(int newCapacity)
```
    Recreates the entire contents of the hashmap into a new array with double the capacity. This method is called when the number of keys in the map reaches the current threshold.
    
    Parameters:
    newCapacity - the new size of the hash entries
  - hash
```
private int hash(Object key)
```
    Gets the hash code for the specified key. This implementation uses the additional hashing routine from JDK 1.4.
    
    Parameters:
    key - the key to get a hash value for
    
    Returns:
    the hash value
  - isEqual
```
private boolean isEqual(Object x,
              Object y)
```
    Compares two objects for equality. Method uses equals method and assumes neither value is null.
    
    Parameters:
    x - the first value
    y - the second value
    
    Returns:
    true if equal
  - hashIndex
```
private int hashIndex(int hashValue,
            int length)
```
    Determines the index into the current hash table for the specified hashValue.
    
    Parameters:
    hashValue - the hash value
    length - the current number of hash buckets
    
    Returns:
    the index of the current hash array to use
  - calculateCapacity
```
private int calculateCapacity(int proposedCapacity)
```
    Calculates the capacity of the array backing the hash by normalizing capacity to a power of 2 and enforcing capacity limits.
    
    Parameters:
    proposedCapacity - the proposed capacity
    
    Returns:
    the normalized capacity
  - calculateThreshold
```
private int calculateThreshold(int capacity,
                     float factor)
```
    Calculates the threshold of the map given the capacity and load factor. Once the number of entries in the map grows to the threshold we will double the size of the array.
    
    Parameters:
    capacity - the size of the array
    factor - the load factor of the hash
  - init
```
private void init()
```
    Set the initial heap usage of this class. Includes class variable overhead and the entry array.
  - entryLruList
```
public List<LruHashMap.Entry<K,V>> entryLruList()
```
    Debugging function that returns a List sorted by access time. The order is oldest to newest (first in list is next to be evicted).
    
    Returns:
    Sorted list of entries
  - entryTableSet
```
public Set<LruHashMap.Entry<K,V>> entryTableSet()
```
    Debugging function that returns a Set of all entries in the hash table.
    
    Returns:
    Set of entries in hash
  - getHeadPtr
```
public LruHashMap.Entry getHeadPtr()
```
    Get the head of the linked list (least recently used).
    
    Returns:
    head of linked list
  - getTailPtr
```
public LruHashMap.Entry getTailPtr()
```
    Get the tail of the linked list (most recently used).
    
    Returns:
    tail of linked list
  - entrySet
```
public Set<Map.Entry<K,V>> entrySet()
```
    Intentionally unimplemented.
    
    Specified by:
    
    entrySet in interface Map<K extends HeapSize,V extends HeapSize>
  - equals
```
public boolean equals(Object o)
```
    Intentionally unimplemented.
    
    Specified by:
    
    equals in interface Map<K extends HeapSize,V extends HeapSize>
    
    Overrides:
    
    equals in class Object
  - hashCode
```
public int hashCode()
```
    Intentionally unimplemented.
    
    Specified by:
    
    hashCode in interface Map<K extends HeapSize,V extends HeapSize>
    
    Overrides:
    
    hashCode in class Object
  - keySet
```
public Set<K> keySet()
```
    Intentionally unimplemented.
    
    Specified by:
    
    keySet in interface Map<K extends HeapSize,V extends HeapSize>
  - putAll
```
public void putAll(Map<? extends K,? extends V> m)
```
    Intentionally unimplemented.
    
    Specified by:
    
    putAll in interface Map<K extends HeapSize,V extends HeapSize>
  - values
```
public Collection<V> values()
```
    Intentionally unimplemented.
    
    Specified by:
    
    values in interface Map<K extends HeapSize,V extends HeapSize>

Class LruHashMap<K extends HeapSize,V extends HeapSize>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

LOG

DEFAULT_MAX_MEM_USAGE

DEFAULT_INITIAL_CAPACITY

MAXIMUM_CAPACITY

DEFAULT_LOAD_FACTOR

OVERHEAD

loadFactor

size

threshold

entries

headPtr

tailPtr

memTotal

memFree

hitCount

missCount

Constructor Detail

LruHashMap

LruHashMap

LruHashMap

LruHashMap

LruHashMap

Method Detail

getMemFree

getMemMax

getMemUsed

getHitCount

getMissCount

getHitRatio

freeMemory

heapSize

get

put

remove

size

isEmpty

clear

containsKey

containsValue

checkKey

checkValue

getMinimumUsage

checkAndFreeMemory

evictFromLru

updateLru

removeEntry

removeEntryForKey

addEntry

clearAll

growTable

hash

isEqual

hashIndex

calculateCapacity

calculateThreshold

init

entryLruList

entryTableSet

getHeadPtr

getTailPtr

entrySet

equals

hashCode

keySet

putAll

values