Please enable JavaScript.
Coggle requires JavaScript to display documents.
Collections (Map (ConcurrentHashMap (Node Type (TreeBin (holds the root…
Collections
Map
-
-
-
ConcurrentHashMap
Get actions do NOT lock at all. volatile is used in HashEntry.next/value to ensure happens-before ordering
-
Iterators, Spliterators, Enumerations return elements
reflecting the state of the hash table at the point the iterator was created
:!: iterators are designed to be used by only one thread at a time
-
-
Node Type
Node
contains hash value (final), key (final), value (volatile), link to next Node (volatile)
TreeBin
-
do not hold normal key-value, has negative hash and null key/value, identified during searching the table
requires additional locking because tree structure may change due to rebalancing during traversal
When root lock is held, traverse via the linked "next" pointers, until lock released or linkedlist is done
TreeNode
-
Also maintain the same linked order before turned into a balanced tree, so still can be traversed in the same order
ForwardingNode
-
do not hold normal key-value, has negative hash and null key/value, identified during searching the table
ReservationNode
-
do not hold normal key-value, has negative hash and null key/value, identified during searching the table
lazily initialised to a power-of-2 sized table upon first insertion.
:question: Why power of 2?
- To allow efficient modulo action in hash function and best evenly utilise bins
- When resizing, only 1/6 of entries on avg. need be relocated
Nodes with negative hash values are specially handled, or ignored in map methods
Use head node of the list/tree as lock on each bin.
BUT when a node is locked, any update MUST VALIDATE its still the head node after locking it,
and retry if not (means this node is deleted or the bin is resizing).
Nodes are always appended, so the head node is always head until deleted or the bin is invalidated upon resizing
TableStack
when first encounter a ForwardingNode during a traversal, create a stack to maintain its place in the old table if later processing the current, old table
Heap/PriorityQueue
heapify
for each node, node.val > or < node.left.val and node.right.val
-
-
-
application
-
find median using 2 heaps, keep size diff within 1
Queue/List
ArrayList
-
-
modCount
track times modified, to avoid concurrent modifications
O(1) read/write, O(N) insert/delete
LinkedList
O(N) read/write, O(1) insert/delete
-
-
Deque
-
-
ArrayDeque
-
loop array, use head & tail to track data
Concurrent Collections
ConcurrentLinkedQueue
Unbounded thread-safe linked list, null value not allowed
uses CAS to enqueue/dequeue. CASing a Node's item reference to null auto-remove the element from the queue
-
When constructing a Node before enqueueing, use Unsafe.putObject instead of normal write to safe cost to one-and-a-half CAS
size() is O(N), no count maintained, need a traverse to get size and may not be accurate upon concurrent updates
use volatile item, next references to ensure memory visibility
dequeued Node set next to point to itself, indicating the node is out of queue
-