Class ConcurrentLinkedHashMap<K,V>
- Type Parameters:
K
- the type of keys maintained by this mapV
- the type of mapped values
- All Implemented Interfaces:
Serializable
,ConcurrentMap<K,
,V> Map<K,
V>
ConcurrentHashMap
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 a ConcurrentLinkedHashMap.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 an
ExecutorService
.
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
and Iterator
interfaces.
Like Hashtable
but unlike HashMap
, this class
does not allow null to be used as a key or value. Unlike
LinkedHashMap
, 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.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) class
A skeletal implementation of the Task interface.(package private) final class
Adds the node to the page replacement policy.(package private) static final class
A weigher that enforces that the weight falls within a valid range.static final class
A builder that createsConcurrentLinkedHashMap
instances.(package private) static enum
A listener that ignores all notifications.(package private) static final class
A queue that discards all additions and is always empty.(package private) static enum
The draining status of the buffers.(package private) final class
An adapter to safely externalize the entry iterator.(package private) final class
An adapter to safely externalize the entries.(package private) final class
An adapter to safely externalize the key iterator.(package private) final class
An adapter to safely externalize the keys.(package private) final class
A node contains the key, the weighted value, and the linkage pointers on the page-replacement algorithm's data structures.(package private) class
Updates the node's location in the page replacement policy.(package private) final class
Removes a node from the page replacement policy.(package private) static final class
A proxy that is serialized instead of the map.(package private) static interface
An operation that can be lazily applied to the page replacement policy.(package private) final class
Updates the weighted size and evicts an entry on overflow.(package private) final class
An adapter to safely externalize the value iterator.(package private) final class
An adapter to safely externalize the values.(package private) static final class
A value, its weight, and the entry's status.(package private) final class
An entry that allows updates to write through to the map.Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescription(package private) static final int
The maximum number of operations to perform per amortized drain.(package private) static final int
Mask value for indexing into the buffers.(package private) static final int
The number of pending operations per buffer before attempting to drain.(package private) final AtomicIntegerArray
(package private) final Queue<ConcurrentLinkedHashMap.Task>[]
(package private) long
(package private) final int
(package private) final ConcurrentMap
<K, ConcurrentLinkedHashMap<K, V>.Node> (package private) static final Queue
<?> A queue that discards all entries.(package private) int
(package private) final AtomicReference
<ConcurrentLinkedHashMap.DrainStatus> (package private) final LinkedDeque
<ConcurrentLinkedHashMap<K, V>.Node> (package private) final Lock
(package private) final EvictionListener
<K, V> (package private) static final int
The maximum number of pending operations per buffer.(package private) static final long
The maximum weighted capacity of the map.(package private) int
(package private) static final int
The number of buffers to use.(package private) final Queue
<ConcurrentLinkedHashMap<K, V>.Node> (package private) static final long
(package private) final ConcurrentLinkedHashMap.Task[]
(package private) Collection
<V> (package private) final EntryWeigher
<? super K, ? super V> (package private) final AtomicLong
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
Creates an instance based on the builder's configuration. -
Method Summary
Modifier and TypeMethodDescription(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
Performs the post-processing work required after the map operation.Returns a unmodifiable snapshotSet
view of the keys contained in this map.ascendingKeySetWithLimit
(int limit) Returns an unmodifiable snapshotSet
view of the keys contained in this map.Returns an unmodifiable snapshotMap
view of the mappings contained in this map.ascendingMapWithLimit
(int limit) Returns an unmodifiable snapshotMap
view of the mappings contained in this map.(package private) static int
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
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
(Object key) boolean
containsValue
(Object value) Returns an unmodifiable snapshotSet
view of the keys contained in this map.descendingKeySetWithLimit
(int limit) Returns an unmodifiable snapshotSet
view of the keys contained in this map.Returns an unmodifiable snapshotMap
view of the mappings contained in this map.descendingMapWithLimit
(int limit) Returns an unmodifiable snapshotMap
view of the mappings contained in this map.(package private) void
Drains the buffers up to the amortized threshold and applies the pending operations.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.getQuietly
(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
Determines whether the map has exceeded its capacity.boolean
isEmpty()
keySet()
(package private) int
moveTasksFromBuffer
(ConcurrentLinkedHashMap.Task[] tasks, int bufferIndex) Moves the tasks from the specified buffer into the output array.(package private) int
Moves the tasks from the buffers into the output array.(package private) int
Returns the ordering value to assign to a task.(package private) void
Notifies the listener of entries that were evicted.orderedKeySet
(boolean ascending, int limit) orderedMap
(boolean ascending, int limit) (package private) V
Adds a node to the list and the data store.putIfAbsent
(K key, V value) private void
readObject
(ObjectInputStream stream) boolean
boolean
(package private) void
runTasks
(ConcurrentLinkedHashMap.Task[] tasks, int maxTaskIndex) Runs the pending page replacement policy operations.(package private) void
Runs the pending operations on the linked chain.(package private) boolean
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
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.values()
long
Returns the weighted size of this map.(package private) Object
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.concurrent.ConcurrentMap
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, replaceAll
-
Field Details
-
MAXIMUM_CAPACITY
static final long MAXIMUM_CAPACITYThe maximum weighted capacity of the map.- See Also:
-
MAXIMUM_BUFFER_SIZE
static final int MAXIMUM_BUFFER_SIZEThe maximum number of pending operations per buffer.- See Also:
-
BUFFER_THRESHOLD
static final int BUFFER_THRESHOLDThe number of pending operations per buffer before attempting to drain.- See Also:
-
NUMBER_OF_BUFFERS
static final int NUMBER_OF_BUFFERSThe number of buffers to use. -
BUFFER_MASK
static final int BUFFER_MASKMask value for indexing into the buffers. -
AMORTIZED_DRAIN_THRESHOLD
static final int AMORTIZED_DRAIN_THRESHOLDThe maximum number of operations to perform per amortized drain. -
DISCARDING_QUEUE
A queue that discards all entries. -
data
-
concurrencyLevel
final int concurrencyLevel -
evictionDeque
-
weightedSize
-
capacity
volatile long capacity -
nextOrder
volatile int nextOrder -
drainedOrder
int drainedOrder -
tasks
-
evictionLock
-
buffers
-
bufferLengths
-
drainStatus
-
weigher
-
pendingNotifications
-
listener
-
keySet
-
values
-
entrySet
-
serialVersionUID
static final long serialVersionUID- See Also:
-
-
Constructor Details
-
ConcurrentLinkedHashMap
Creates an instance based on the builder's configuration.
-
-
Method Details
-
ceilingNextPowerOfTwo
static int ceilingNextPowerOfTwo(int x) -
checkNotNull
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:
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
Performs the post-processing work required after the map operation.- Parameters:
task
- the pending operation to be applied
-
schedule
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
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
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
Runs the pending page replacement policy operations.- Parameters:
tasks
- the ordered array of the pending operationsmaxTaskIndex
- the maximum index of the array
-
runTasksInChain
Runs the pending operations on the linked chain.- Parameters:
task
- the first task in the chain of operations
-
updateDrainedOrder
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
- Specified by:
containsKey
in interfaceMap<K,
V> - Overrides:
containsKey
in classAbstractMap<K,
V>
-
containsValue
- Specified by:
containsValue
in interfaceMap<K,
V> - Overrides:
containsValue
in classAbstractMap<K,
V>
-
get
-
getQuietly
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:
NullPointerException
- if the specified key is null
-
put
-
putIfAbsent
- Specified by:
putIfAbsent
in interfaceConcurrentMap<K,
V> - Specified by:
putIfAbsent
in interfaceMap<K,
V>
-
put
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
-
remove
-
replace
-
replace
-
keySet
-
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
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:
IllegalArgumentException
- if the limit is negative
-
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
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:
IllegalArgumentException
- if the limit is negative
-
orderedKeySet
-
values
-
entrySet
-
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
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:
IllegalArgumentException
- if the limit is negative
-
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
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:
IllegalArgumentException
- if the limit is negative
-
orderedMap
-
writeReplace
Object writeReplace() -
readObject
- Throws:
InvalidObjectException
-