Class ConcurrentLinkedHashMap<K,V>
- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.googlecode.concurrentlinkedhashmap.ConcurrentLinkedHashMap<K,V>
-
- Type Parameters:
K
- the type of keys maintained by this mapV
- the type of mapped values
- All Implemented Interfaces:
java.io.Serializable
,java.util.concurrent.ConcurrentMap<K,V>
,java.util.Map<K,V>
@ThreadSafe public final class ConcurrentLinkedHashMap<K,V> extends java.util.AbstractMap<K,V> implements java.util.concurrent.ConcurrentMap<K,V>, java.io.Serializable
A hash table supporting full concurrency of retrievals, adjustable expected concurrency for updates, and a maximum capacity to bound the map by. This implementation differs fromConcurrentHashMap
in that it maintains a page replacement algorithm that is used to evict an entry when the map has exceeded its capacity. Unlike the Java Collections Framework, this map does not have a publicly visible constructor and instances are created through aConcurrentLinkedHashMap.Builder
.An entry is evicted from the map when the weighted capacity exceeds its maximum weighted capacity threshold. A
EntryWeigher
determines how many units of capacity that an entry consumes. The default weigher assigns each value a weight of 1 to bound the map by the total number of key-value pairs. A map that holds collections may choose to weigh values by the number of elements in the collection and bound the map by the total number of elements that it contains. A change to a value that modifies its weight requires that an update operation is performed on the map.An
EvictionListener
may be supplied for notification when an entry is evicted from the map. This listener is invoked on a caller's thread and will not block other threads from operating on the map. An implementation should be aware that the caller's thread will not expect long execution times or failures as a side effect of the listener being notified. Execution safety and a fast turn around time can be achieved by performing the operation asynchronously, such as by submitting a task to anExecutorService
.The concurrency level determines the number of threads that can concurrently modify the table. Using a significantly higher or lower value than needed can waste space or lead to thread contention, but an estimate within an order of magnitude of the ideal value does not usually have a noticeable impact. Because placement in hash tables is essentially random, the actual concurrency will vary.
This class and its views and iterators implement all of the optional methods of the
Map
andIterator
interfaces.Like
Hashtable
but unlikeHashMap
, this class does not allow null to be used as a key or value. UnlikeLinkedHashMap
, this class does not provide predictable iteration order. A snapshot of the keys and entries may be obtained in ascending and descending order of retention.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
ConcurrentLinkedHashMap.AbstractTask
A skeletal implementation of the Task interface.(package private) class
ConcurrentLinkedHashMap.AddTask
Adds the node to the page replacement policy.(package private) static class
ConcurrentLinkedHashMap.BoundedEntryWeigher<K,V>
A weigher that enforces that the weight falls within a valid range.static class
ConcurrentLinkedHashMap.Builder<K,V>
A builder that createsConcurrentLinkedHashMap
instances.(package private) static class
ConcurrentLinkedHashMap.DiscardingListener
A listener that ignores all notifications.(package private) static class
ConcurrentLinkedHashMap.DiscardingQueue
A queue that discards all additions and is always empty.(package private) static class
ConcurrentLinkedHashMap.DrainStatus
The draining status of the buffers.(package private) class
ConcurrentLinkedHashMap.EntryIterator
An adapter to safely externalize the entry iterator.(package private) class
ConcurrentLinkedHashMap.EntrySet
An adapter to safely externalize the entries.(package private) class
ConcurrentLinkedHashMap.KeyIterator
An adapter to safely externalize the key iterator.(package private) class
ConcurrentLinkedHashMap.KeySet
An adapter to safely externalize the keys.(package private) class
ConcurrentLinkedHashMap.Node
A node contains the key, the weighted value, and the linkage pointers on the page-replacement algorithm's data structures.(package private) class
ConcurrentLinkedHashMap.ReadTask
Updates the node's location in the page replacement policy.(package private) class
ConcurrentLinkedHashMap.RemovalTask
Removes a node from the page replacement policy.(package private) static class
ConcurrentLinkedHashMap.SerializationProxy<K,V>
A proxy that is serialized instead of the map.(package private) static interface
ConcurrentLinkedHashMap.Task
An operation that can be lazily applied to the page replacement policy.(package private) class
ConcurrentLinkedHashMap.UpdateTask
Updates the weighted size and evicts an entry on overflow.(package private) class
ConcurrentLinkedHashMap.ValueIterator
An adapter to safely externalize the value iterator.(package private) class
ConcurrentLinkedHashMap.Values
An adapter to safely externalize the values.(package private) static class
ConcurrentLinkedHashMap.WeightedValue<V>
A value, its weight, and the entry's status.(package private) class
ConcurrentLinkedHashMap.WriteThroughEntry
An entry that allows updates to write through to the map.
-
Field Summary
Fields Modifier and Type Field Description (package private) static int
AMORTIZED_DRAIN_THRESHOLD
The maximum number of operations to perform per amortized drain.(package private) static int
BUFFER_MASK
Mask value for indexing into the buffers.(package private) static int
BUFFER_THRESHOLD
The number of pending operations per buffer before attempting to drain.(package private) java.util.concurrent.atomic.AtomicIntegerArray
bufferLengths
(package private) java.util.Queue<ConcurrentLinkedHashMap.Task>[]
buffers
(package private) long
capacity
(package private) int
concurrencyLevel
(package private) java.util.concurrent.ConcurrentMap<K,ConcurrentLinkedHashMap.Node>
data
(package private) static java.util.Queue<?>
DISCARDING_QUEUE
A queue that discards all entries.(package private) int
drainedOrder
(package private) java.util.concurrent.atomic.AtomicReference<ConcurrentLinkedHashMap.DrainStatus>
drainStatus
(package private) java.util.Set<java.util.Map.Entry<K,V>>
entrySet
(package private) LinkedDeque<ConcurrentLinkedHashMap.Node>
evictionDeque
(package private) java.util.concurrent.locks.Lock
evictionLock
(package private) java.util.Set<K>
keySet
(package private) EvictionListener<K,V>
listener
(package private) static int
MAXIMUM_BUFFER_SIZE
The maximum number of pending operations per buffer.(package private) static long
MAXIMUM_CAPACITY
The maximum weighted capacity of the map.(package private) int
nextOrder
(package private) static int
NUMBER_OF_BUFFERS
The number of buffers to use.(package private) java.util.Queue<ConcurrentLinkedHashMap.Node>
pendingNotifications
(package private) static long
serialVersionUID
(package private) ConcurrentLinkedHashMap.Task[]
tasks
(package private) java.util.Collection<V>
values
(package private) EntryWeigher<? super K,? super V>
weigher
(package private) java.util.concurrent.atomic.AtomicLong
weightedSize
-
Constructor Summary
Constructors Modifier Constructor Description private
ConcurrentLinkedHashMap(ConcurrentLinkedHashMap.Builder<K,V> builder)
Creates an instance based on the builder's configuration.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
addTaskToChain(ConcurrentLinkedHashMap.Task[] tasks, ConcurrentLinkedHashMap.Task task, int index)
Adds the task as the head of the chain at the index location.(package private) void
afterCompletion(ConcurrentLinkedHashMap.Task task)
Performs the post-processing work required after the map operation.java.util.Set<K>
ascendingKeySet()
Returns a unmodifiable snapshotSet
view of the keys contained in this map.java.util.Set<K>
ascendingKeySetWithLimit(int limit)
Returns an unmodifiable snapshotSet
view of the keys contained in this map.java.util.Map<K,V>
ascendingMap()
Returns an unmodifiable snapshotMap
view of the mappings contained in this map.java.util.Map<K,V>
ascendingMapWithLimit(int limit)
Returns an unmodifiable snapshotMap
view of the mappings contained in this map.(package private) static int
bufferIndex()
Returns the index to the buffer that the task should be scheduled on.long
capacity()
Retrieves the maximum weighted capacity of the map.(package private) static int
ceilingNextPowerOfTwo(int x)
(package private) static void
checkArgument(boolean expression)
Ensures that the argument expression is true.(package private) static void
checkNotNull(java.lang.Object o)
Ensures that the object is not null.(package private) static void
checkState(boolean expression)
Ensures that the state expression is true.void
clear()
boolean
containsKey(java.lang.Object key)
boolean
containsValue(java.lang.Object value)
java.util.Set<K>
descendingKeySet()
Returns an unmodifiable snapshotSet
view of the keys contained in this map.java.util.Set<K>
descendingKeySetWithLimit(int limit)
Returns an unmodifiable snapshotSet
view of the keys contained in this map.java.util.Map<K,V>
descendingMap()
Returns an unmodifiable snapshotMap
view of the mappings contained in this map.java.util.Map<K,V>
descendingMapWithLimit(int limit)
Returns an unmodifiable snapshotMap
view of the mappings contained in this map.(package private) void
drainBuffers()
Drains the buffers up to the amortized threshold and applies the pending operations.java.util.Set<java.util.Map.Entry<K,V>>
entrySet()
(package private) void
evict()
Evicts entries from the map while it exceeds the capacity and appends evicted entries to the notification queue for processing.V
get(java.lang.Object key)
V
getQuietly(java.lang.Object key)
Returns the value to which the specified key is mapped, ornull
if this map contains no mapping for the key.(package private) boolean
hasOverflowed()
Determines whether the map has exceeded its capacity.boolean
isEmpty()
java.util.Set<K>
keySet()
(package private) int
moveTasksFromBuffer(ConcurrentLinkedHashMap.Task[] tasks, int bufferIndex)
Moves the tasks from the specified buffer into the output array.(package private) int
moveTasksFromBuffers(ConcurrentLinkedHashMap.Task[] tasks)
Moves the tasks from the buffers into the output array.(package private) int
nextOrdering()
Returns the ordering value to assign to a task.(package private) void
notifyListener()
Notifies the listener of entries that were evicted.(package private) java.util.Set<K>
orderedKeySet(boolean ascending, int limit)
(package private) java.util.Map<K,V>
orderedMap(boolean ascending, int limit)
V
put(K key, V value)
(package private) V
put(K key, V value, boolean onlyIfAbsent)
Adds a node to the list and the data store.V
putIfAbsent(K key, V value)
private void
readObject(java.io.ObjectInputStream stream)
V
remove(java.lang.Object key)
boolean
remove(java.lang.Object key, java.lang.Object value)
V
replace(K key, V value)
boolean
replace(K key, V oldValue, V newValue)
(package private) void
runTasks(ConcurrentLinkedHashMap.Task[] tasks, int maxTaskIndex)
Runs the pending page replacement policy operations.(package private) void
runTasksInChain(ConcurrentLinkedHashMap.Task task)
Runs the pending operations on the linked chain.(package private) boolean
schedule(ConcurrentLinkedHashMap.Task task)
Schedules the task to be applied to the page replacement policy.void
setCapacity(long capacity)
Sets the maximum weighted capacity of the map and eagerly evicts entries until it shrinks to the appropriate size.int
size()
(package private) void
tryToDrainBuffers()
Attempts to acquire the eviction lock and apply the pending operations, up to the amortized threshold, to the page replacement policy.(package private) void
updateDrainedOrder(ConcurrentLinkedHashMap.Task[] tasks, int maxTaskIndex)
Updates the order to start the next drain from.java.util.Collection<V>
values()
long
weightedSize()
Returns the weighted size of this map.(package private) java.lang.Object
writeReplace()
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
-
-
-
Field Detail
-
MAXIMUM_CAPACITY
static final long MAXIMUM_CAPACITY
The maximum weighted capacity of the map.- See Also:
- Constant Field Values
-
MAXIMUM_BUFFER_SIZE
static final int MAXIMUM_BUFFER_SIZE
The maximum number of pending operations per buffer.- See Also:
- Constant Field Values
-
BUFFER_THRESHOLD
static final int BUFFER_THRESHOLD
The number of pending operations per buffer before attempting to drain.- See Also:
- Constant Field Values
-
NUMBER_OF_BUFFERS
static final int NUMBER_OF_BUFFERS
The number of buffers to use.
-
BUFFER_MASK
static final int BUFFER_MASK
Mask value for indexing into the buffers.
-
AMORTIZED_DRAIN_THRESHOLD
static final int AMORTIZED_DRAIN_THRESHOLD
The maximum number of operations to perform per amortized drain.
-
DISCARDING_QUEUE
static final java.util.Queue<?> DISCARDING_QUEUE
A queue that discards all entries.
-
data
final java.util.concurrent.ConcurrentMap<K,ConcurrentLinkedHashMap.Node> data
-
concurrencyLevel
final int concurrencyLevel
-
evictionDeque
final LinkedDeque<ConcurrentLinkedHashMap.Node> evictionDeque
-
weightedSize
final java.util.concurrent.atomic.AtomicLong weightedSize
-
capacity
volatile long capacity
-
nextOrder
volatile int nextOrder
-
drainedOrder
int drainedOrder
-
tasks
final ConcurrentLinkedHashMap.Task[] tasks
-
evictionLock
final java.util.concurrent.locks.Lock evictionLock
-
buffers
final java.util.Queue<ConcurrentLinkedHashMap.Task>[] buffers
-
bufferLengths
final java.util.concurrent.atomic.AtomicIntegerArray bufferLengths
-
drainStatus
final java.util.concurrent.atomic.AtomicReference<ConcurrentLinkedHashMap.DrainStatus> drainStatus
-
weigher
final EntryWeigher<? super K,? super V> weigher
-
pendingNotifications
final java.util.Queue<ConcurrentLinkedHashMap.Node> pendingNotifications
-
listener
final EvictionListener<K,V> listener
-
keySet
transient java.util.Set<K> keySet
-
values
transient java.util.Collection<V> values
-
serialVersionUID
static final long serialVersionUID
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
ConcurrentLinkedHashMap
private ConcurrentLinkedHashMap(ConcurrentLinkedHashMap.Builder<K,V> builder)
Creates an instance based on the builder's configuration.
-
-
Method Detail
-
ceilingNextPowerOfTwo
static int ceilingNextPowerOfTwo(int x)
-
checkNotNull
static void checkNotNull(java.lang.Object o)
Ensures that the object is not null.
-
checkArgument
static void checkArgument(boolean expression)
Ensures that the argument expression is true.
-
checkState
static void checkState(boolean expression)
Ensures that the state expression is true.
-
capacity
public long capacity()
Retrieves the maximum weighted capacity of the map.- Returns:
- the maximum weighted capacity
-
setCapacity
public void setCapacity(long capacity)
Sets the maximum weighted capacity of the map and eagerly evicts entries until it shrinks to the appropriate size.- Parameters:
capacity
- the maximum weighted capacity of the map- Throws:
java.lang.IllegalArgumentException
- if the capacity is negative
-
hasOverflowed
boolean hasOverflowed()
Determines whether the map has exceeded its capacity.
-
evict
void evict()
Evicts entries from the map while it exceeds the capacity and appends evicted entries to the notification queue for processing.
-
afterCompletion
void afterCompletion(ConcurrentLinkedHashMap.Task task)
Performs the post-processing work required after the map operation.- Parameters:
task
- the pending operation to be applied
-
schedule
boolean schedule(ConcurrentLinkedHashMap.Task task)
Schedules the task to be applied to the page replacement policy.- Parameters:
task
- the pending operation- Returns:
- if the draining of the buffers can be delayed
-
bufferIndex
static int bufferIndex()
Returns the index to the buffer that the task should be scheduled on.
-
nextOrdering
int nextOrdering()
Returns the ordering value to assign to a task.
-
tryToDrainBuffers
void tryToDrainBuffers()
Attempts to acquire the eviction lock and apply the pending operations, up to the amortized threshold, to the page replacement policy.
-
drainBuffers
void drainBuffers()
Drains the buffers up to the amortized threshold and applies the pending operations.
-
moveTasksFromBuffers
int moveTasksFromBuffers(ConcurrentLinkedHashMap.Task[] tasks)
Moves the tasks from the buffers into the output array.- Parameters:
tasks
- the ordered array of the pending operations- Returns:
- the highest index location of a task that was added to the array
-
moveTasksFromBuffer
int moveTasksFromBuffer(ConcurrentLinkedHashMap.Task[] tasks, int bufferIndex)
Moves the tasks from the specified buffer into the output array.- Parameters:
tasks
- the ordered array of the pending operationsbufferIndex
- the buffer to drain into the tasks array- Returns:
- the highest index location of a task that was added to the array
-
addTaskToChain
void addTaskToChain(ConcurrentLinkedHashMap.Task[] tasks, ConcurrentLinkedHashMap.Task task, int index)
Adds the task as the head of the chain at the index location.- Parameters:
tasks
- the ordered array of the pending operationstask
- the pending operation to addindex
- the array location
-
runTasks
void runTasks(ConcurrentLinkedHashMap.Task[] tasks, int maxTaskIndex)
Runs the pending page replacement policy operations.- Parameters:
tasks
- the ordered array of the pending operationsmaxTaskIndex
- the maximum index of the array
-
runTasksInChain
void runTasksInChain(ConcurrentLinkedHashMap.Task task)
Runs the pending operations on the linked chain.- Parameters:
task
- the first task in the chain of operations
-
updateDrainedOrder
void updateDrainedOrder(ConcurrentLinkedHashMap.Task[] tasks, int maxTaskIndex)
Updates the order to start the next drain from.- Parameters:
tasks
- the ordered array of operationsmaxTaskIndex
- the maximum index of the array
-
notifyListener
void notifyListener()
Notifies the listener of entries that were evicted.
-
isEmpty
public boolean isEmpty()
-
size
public int size()
-
weightedSize
public long weightedSize()
Returns the weighted size of this map.- Returns:
- the combined weight of the values in this map
-
clear
public void clear()
-
containsKey
public boolean containsKey(java.lang.Object key)
-
containsValue
public boolean containsValue(java.lang.Object value)
-
get
public V get(java.lang.Object key)
-
getQuietly
public V getQuietly(java.lang.Object key)
Returns the value to which the specified key is mapped, ornull
if this map contains no mapping for the key. This method differs fromget(Object)
in that it does not record the operation with the page replacement policy.- Parameters:
key
- the key whose associated value is to be returned- Returns:
- the value to which the specified key is mapped, or
null
if this map contains no mapping for the key - Throws:
java.lang.NullPointerException
- if the specified key is null
-
put
V put(K key, V value, boolean onlyIfAbsent)
Adds a node to the list and the data store. If an existing node is found, then its value is updated if allowed.- Parameters:
key
- key with which the specified value is to be associatedvalue
- value to be associated with the specified keyonlyIfAbsent
- a write is performed only if the key is not already associated with a value- Returns:
- the prior value in the data store or null if no mapping was found
-
remove
public V remove(java.lang.Object key)
-
remove
public boolean remove(java.lang.Object key, java.lang.Object value)
-
keySet
public java.util.Set<K> keySet()
-
ascendingKeySet
public java.util.Set<K> ascendingKeySet()
Returns a unmodifiable snapshotSet
view of the keys contained in this map. The set's iterator returns the keys whose order of iteration is the ascending order in which its entries are considered eligible for retention, from the least-likely to be retained to the most-likely.Beware that, unlike in
keySet()
, obtaining the set is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the keys.- Returns:
- an ascending snapshot view of the keys in this map
-
ascendingKeySetWithLimit
public java.util.Set<K> ascendingKeySetWithLimit(int limit)
Returns an unmodifiable snapshotSet
view of the keys contained in this map. The set's iterator returns the keys whose order of iteration is the ascending order in which its entries are considered eligible for retention, from the least-likely to be retained to the most-likely.Beware that, unlike in
keySet()
, obtaining the set is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the keys.- Parameters:
limit
- the maximum size of the returned set- Returns:
- a ascending snapshot view of the keys in this map
- Throws:
java.lang.IllegalArgumentException
- if the limit is negative
-
descendingKeySet
public java.util.Set<K> descendingKeySet()
Returns an unmodifiable snapshotSet
view of the keys contained in this map. The set's iterator returns the keys whose order of iteration is the descending order in which its entries are considered eligible for retention, from the most-likely to be retained to the least-likely.Beware that, unlike in
keySet()
, obtaining the set is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the keys.- Returns:
- a descending snapshot view of the keys in this map
-
descendingKeySetWithLimit
public java.util.Set<K> descendingKeySetWithLimit(int limit)
Returns an unmodifiable snapshotSet
view of the keys contained in this map. The set's iterator returns the keys whose order of iteration is the descending order in which its entries are considered eligible for retention, from the most-likely to be retained to the least-likely.Beware that, unlike in
keySet()
, obtaining the set is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the keys.- Parameters:
limit
- the maximum size of the returned set- Returns:
- a descending snapshot view of the keys in this map
- Throws:
java.lang.IllegalArgumentException
- if the limit is negative
-
orderedKeySet
java.util.Set<K> orderedKeySet(boolean ascending, int limit)
-
values
public java.util.Collection<V> values()
-
ascendingMap
public java.util.Map<K,V> ascendingMap()
Returns an unmodifiable snapshotMap
view of the mappings contained in this map. The map's collections return the mappings whose order of iteration is the ascending order in which its entries are considered eligible for retention, from the least-likely to be retained to the most-likely.Beware that obtaining the mappings is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the entries.
- Returns:
- a ascending snapshot view of this map
-
ascendingMapWithLimit
public java.util.Map<K,V> ascendingMapWithLimit(int limit)
Returns an unmodifiable snapshotMap
view of the mappings contained in this map. The map's collections return the mappings whose order of iteration is the ascending order in which its entries are considered eligible for retention, from the least-likely to be retained to the most-likely.Beware that obtaining the mappings is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the entries.
- Parameters:
limit
- the maximum size of the returned map- Returns:
- a ascending snapshot view of this map
- Throws:
java.lang.IllegalArgumentException
- if the limit is negative
-
descendingMap
public java.util.Map<K,V> descendingMap()
Returns an unmodifiable snapshotMap
view of the mappings contained in this map. The map's collections return the mappings whose order of iteration is the descending order in which its entries are considered eligible for retention, from the most-likely to be retained to the least-likely.Beware that obtaining the mappings is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the entries.
- Returns:
- a descending snapshot view of this map
-
descendingMapWithLimit
public java.util.Map<K,V> descendingMapWithLimit(int limit)
Returns an unmodifiable snapshotMap
view of the mappings contained in this map. The map's collections return the mappings whose order of iteration is the descending order in which its entries are considered eligible for retention, from the most-likely to be retained to the least-likely.Beware that obtaining the mappings is NOT a constant-time operation. Because of the asynchronous nature of the page replacement policy, determining the retention ordering requires a traversal of the entries.
- Parameters:
limit
- the maximum size of the returned map- Returns:
- a descending snapshot view of this map
- Throws:
java.lang.IllegalArgumentException
- if the limit is negative
-
writeReplace
java.lang.Object writeReplace()
-
readObject
private void readObject(java.io.ObjectInputStream stream) throws java.io.InvalidObjectException
- Throws:
java.io.InvalidObjectException
-
-