java map集合_java遍历map集合

(31) 2024-06-29 09:01:01

多线程环境下的问题

1.8中hashmap的确不会因为多线程put导致死循环(1.7代码中会这样子),但是依然有其他的弊端,比如数据丢失等等。因此多线程情况下还是建议使用ConcurrentHashMap。

 

数据丢失:当多线程put的时候,当index相同而又同时达到链表的末尾时,另一个线程put的数据会把之前线程put的数据覆盖掉,就会产生数据丢失。

if ((e = p.next) == null) {                   p.next = newNode(hash, key, value, null); }

Hashtable

Hashtable同样是基于哈希表实现的,同样每个元素是一个key-value对,其内部也是通过单链表解决冲突问题,容量不足(超过了阈值)时,同样会自动增长。

Hashtable也是JDK1.0引入的类,是线程安全的,能用于多线程环境中。

Hashtable同样实现了Serializable接口,它支持序列化,实现了Cloneable接口,能被克隆。

Hashtable 的容量增加逻辑是乘2+1,保证奇数。

在应用数据分布在等差数据集合(如偶数)上时,如果公差与桶容量有公约数n,则至少有(n-1)/n数量的桶是利用不到的。

hash to index

int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;

取与之后一定是一个非负数

0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111 : all 1 except the sign bit.

 (hash & 0x7FFFFFFF) will result in a positive integer.

 (hash & 0x7FFFFFFF) % tab.length will be in the range of the tab length.

ConcurrentHashMap

(底层是数组+链表/红黑树,基于CAS+synchronized)

JDK1.7前:分段锁

基于currentLevel划分出了多个Segment来对key-value进行存储,从而避免每次put操作都得锁住整个数组。在默认的情况下,最佳情况下可以允许16个线程并发无阻塞地操作集合对象,尽可能地减少并发时的阻塞现象。

put、remove会加锁。get和containsKey不会加锁。

计算size:在不加锁的情况下遍历所有的段,读取其count以及modCount,这两个属性都是volatile类型的,并进行统计,再遍历一次所有的段,比较modCount是否有改变。如有改变,则再尝试两次机上动作。

如执行了三次上述动作,仍然有问题,则遍历所有段,分别进行加锁,然后进行计算,计算完毕后释放所有锁,从而完成计算动作。

 

JDK1.8后:CAS+synchronized

bin是桶 bucket的意思

 

ConcurrentHashMap是延迟初始化的,只有在插入数据时,整个HashMap才被初始化为2的次方大小个桶(bin),每个bin包含哈希值相同的一系列Node(一般含有0或1个Node)。每个bin的第一个Node作为这个bin的锁,Hash值为零或者负的将被忽略;

每个bin的第一个Node插入用到CAS原理,这是在ConcurrentHashMap中最常发生的操作,其余的插入、删除、替换操作对bin中的第一个Node加锁,进行操作

ConcurrentHashMap的size()函数一般比较少用,同时为了提高增删查改的效率,容器并未在内部保存一个size值,而且采用每次调用size()函数时累加各个bin中Node的个数计算得到,而且这一过程不加锁,即得到的size值不一定是最新的。

ConcurrentHashMap#Node

Node是最核心的内部类,它包装了key-value键值对,所有插入ConcurrentHashMap的数据都包装在这里面。它与HashMap中的定义很相似,但是但是有一些差别:它对value和next属性设置了volatile属性;’它不允许调用setValue方法直接改变Node的value域;它增加了find方法辅助map.get()方法。

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; // value和next是volatile的 volatile Node<K,V> next; Node(int hash, K key, V val, Node<K,V> next) { this.hash = hash; this.key = key; this.val = val; this.next = next; } public final K getKey() { return key; } public final V getValue() { return val; } public final int hashCode() { return key.hashCode() ^ val.hashCode(); } public final String toString(){ return key + "=" + val; } public final V setValue(V value) { throw new UnsupportedOperationException(); } public final boolean equals(Object o) { Object k, v, u; Map.Entry<?,?> e; return ((o instanceof Map.Entry) && (k = (e = (Map.Entry<?,?>)o).getKey()) != null && (v = e.getValue()) != null && (k == key || k.equals(key)) && (v == (u = val) || v.equals(u))); } /** * Virtualized support for map.get(); overridden in subclasses. */ Node<K,V> find(int h, Object k) { Node<K,V> e = this; if (k != null) { do { K ek; if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; } while ((e = e.next) != null); } return null; } } 

 

ConcurrentHashMap#TreeNode

当链表长度过长的时候,会转换为TreeNode。但是与HashMap不相同的是,它并不是直接转换为红黑树,而是把这些结点包装成TreeNode放在TreeBin对象中,由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap继承自Node类,而并非HashMap中的继承自LinkedHashMap.Entry<K,V>类,也就是说TreeNode带有next指针,这样做的目的是方便基于TreeBin的访问。

ConcurrentHashMap#TreeBin

这个类并不负责包装用户的key、value信息,而是包装的很多TreeNode节点。它代替了TreeNode的根节点,也就是说在实际的ConcurrentHashMap“数组”中,存放的是TreeBin对象,而不是TreeNode对象,这是与HashMap的区别。另外这个类还带有了读写锁。

 

可以看到在构造TreeBin节点时,仅仅指定了它的hash值为TREEBIN常量,这也就是个标识位;同时也看到我们熟悉的红黑树构造方法。

/**  * TreeNodes used at the heads of bins. TreeBins do not hold user  * keys or values, but instead point to list of TreeNodes and  * their root. They also maintain a parasitic read-write lock  * forcing writers (who hold bin lock) to wait for readers (who do  * not) to complete before tree restructuring operations.  */ static final class TreeBin<K,V> extends Node<K,V> {     TreeNode<K,V> root;     volatile TreeNode<K,V> first;     volatile Thread waiter;     volatile int lockState;     // values for lockState     static final int WRITER = 1; // set while holding write lock     static final int WAITER = 2; // set when waiting for write lock     static final int READER = 4; // increment value for setting read lock     /**      * Tie-breaking utility for ordering insertions when equal      * hashCodes and non-comparable. We don't require a total      * order, just a consistent insertion rule to maintain      * equivalence across rebalancings. Tie-breaking further than      * necessary simplifies testing a bit.      */     static int tieBreakOrder(Object a, Object b) {         int d;         if (a == null || b == null ||             (d = a.getClass().getName().              compareTo(b.getClass().getName())) == 0)             d = (System.identityHashCode(a) <= System.identityHashCode(b) ?                  -1 : 1);         return d;     }     /**      * Creates bin with initial set of nodes headed by b.      */     TreeBin(TreeNode<K,V> b) {         super(TREEBIN, null, null, null);         this.first = b;         TreeNode<K,V> r = null;         for (TreeNode<K,V> x = b, next; x != null; x = next) {             next = (TreeNode<K,V>)x.next;             x.left = x.right = null;             if (r == null) {                 x.parent = null;                 x.red = false;                 r = x;             }             else {                 K k = x.key;                 int h = x.hash;                 Class<?> kc = null;                 for (TreeNode<K,V> p = r;;) {                     int dir, ph;                     K pk = p.key;                     if ((ph = p.hash) > h)                         dir = -1;                     else if (ph < h)                         dir = 1;                     else if ((kc == null &&                               (kc = comparableClassFor(k)) == null) ||                              (dir = compareComparables(kc, k, pk)) == 0)                         dir = tieBreakOrder(k, pk);                         TreeNode<K,V> xp = p;                     if ((p = (dir <= 0) ? p.left : p.right) == null) {                         x.parent = xp;                         if (dir <= 0)                             xp.left = x;                         else                             xp.right = x;                         r = balanceInsertion(r, x);                         break;                     }                 }             }         }         this.root = r;         assert checkInvariants(root);     } }

节点类型

hash值大于等于0,则是链表节点,Node

hash值为-1   MOVED,则是forwarding nodes,存储nextTable的引用。只有table发生扩容的时候,ForwardingNode才会发挥作用,作为一个占位符放在table中表示当前节点为null或则已经被移动。

hash值为-2   TREEBIN,则是红黑树根,TreeBin类型

hash值为-3   RESERVED,则是reservation nodes,

static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations

重要属性

/**  * Table initialization and resizing control.  When negative, the  * table is being initialized or resized: -1 for initialization,  * else -(1 + the number of active resizing threads).  Otherwise,  * when table is null, holds the initial table size to use upon  * creation, or 0 for default. After initialization, holds the  * next element count value upon which to resize the table. 负数代表正在进行初始化或扩容操作 -1代表正在初始化 -N 表示有N-1个线程正在进行扩容操作 正数或0代表hash表还没有被初始化,这个数值表示初始化或下一次进行扩容的大小,这一点类似于扩容阈值的概念。还后面可以看到,它的值始终是当前ConcurrentHashMap容量的0.75倍,这与loadfactor是对应的。  */ private transient volatile int sizeCtl;

 

CAS

private static final sun.misc.Unsafe U;

Unsafe类的几个CAS方法,可以原子性地修改对象的某个属性值

/**  * Atomically update Java variable to <tt>x</tt> if it is currently  * holding <tt>expected</tt>.  * @return <tt>true</tt> if successful  */ public final native boolean compareAndSwapObject(Object o, long offset,                                                  Object expected,                                                  Object x); /**  * Atomically update Java variable to <tt>x</tt> if it is currently  * holding <tt>expected</tt>.  * @return <tt>true</tt> if successful  */ public final native boolean compareAndSwapInt(Object o, long offset,                                               int expected,                                               int x); /**  * Atomically update Java variable to <tt>x</tt> if it is currently  * holding <tt>expected</tt>.  * @return <tt>true</tt> if successful  */ public final native boolean compareAndSwapLong(Object o, long offset,                                                long expected,                                                long x); /**  * Fetches a reference value from a given Java variable, with volatile  * load semantics. Otherwise identical to {@link #getObject(Object, long)}  */ public native Object getObjectVolatile(Object o, long offset); /**  * Stores a reference value into a given Java variable, with  * volatile store semantics. Otherwise identical to {@link #putObject(Object, long, Object)}  */ public native void    putObjectVolatile(Object o, long offset, Object x);

 Unsafe.getObjectVolatile可以直接获取指定内存的数据,保证了每次拿到数据都是最新的。

三个核心方法

ConcurrentHashMap定义了三个原子操作,用于对指定位置的节点进行操作。正是这些原子操作保证了ConcurrentHashMap的线程安全。    

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {     return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); } static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,                                     Node<K,V> c, Node<K,V> v) {     return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); } static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {     U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); }

初始化

对于ConcurrentHashMap来说,调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候,调用时机是检查table==null。

初始化方法主要应用了关键属性sizeCtl 如果这个值<0,表示其他线程正在进行初始化,就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限,就用CAS方法将sizeCtl置为-1,防止其他线程进入。初始化数组后,将sizeCtl的值改为0.75*n。

private final Node<K,V>[] initTable() {     Node<K,V>[] tab; int sc;     while ((tab = table) == null || tab.length == 0) {         if ((sc = sizeCtl) < 0)             Thread.yield(); // lost initialization race; just spin // 利用CAS方法把sizectl的值置为-1 表示本线程正在进行初始化          else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {             try {                 if ((tab = table) == null || tab.length == 0) {                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                     @SuppressWarnings("unchecked")                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                     table = tab = nt; // 相当于0.75*n 设置一个扩容的阈值                      sc = n - (n >>> 2);                 }             } finally {                 sizeCtl = sc;             }             break;         }     }     return tab; }

spread(hash)

h是某个对象的hashCode返回值

static final int spread(int h) {     return (h ^ (h >>> 16)) & HASH_BITS; } static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

类似于Hashtable+HashMap的hash实现,Hashtable中也是和一个魔法值取与,保证结果一定为正数;HashMap中也是将hashCode与其移动低n位的结果再取异或,保证了对象的hashCode的高16位的变化能反应到低16位中,

成员变量

@sun.misc.Contended static final class CounterCell {     volatile long value;     CounterCell(long x) { value = x; } } /**  * Base counter value, used mainly when there is no contention,  * but also as a fallback during table initialization  * races. Updated via CAS.  */ private transient volatile long baseCount; /**  * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.  */ private transient volatile int cellsBusy; /**  * Table of counter cells. When non-null, size is a power of 2.  */ private transient volatile CounterCell[] counterCells;

每个CounterCell都对应一个bucket,CounterCell中的long值就是对应bucket的binCount。

计算总大小就是将所有bucket的binCount求和,而每个binCount都存储在CounterCell#value中,每当put或者remove时都会更新节点所在bucket对应的CounterCell#value。

size()

没有直接返回baseCount 而是统计一次这个值,而这个值其实也是一个大概的数值,因此可能在统计的时候有其他线程正在执行插入或删除操作。

public int size() {     long n = sumCount();     return ((n < 0L) ? 0 :             (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :             (int)n); }

在baseCount基础上再加上所有counterCell的值求和。

 

而在addCount时,会先尝试CAS更新baseCount,如果有冲突,则再尝试CAS更新随机的一个counterCell中的value,这样求和就是正确的size了。

final long sumCount() {     CounterCell[] as = counterCells; CounterCell a;     long sum = baseCount;     if (as != null) {         for (int i = 0; i < as.length; ++i) {             if ((a = as[i]) != null) // 所有counter的值求和                  sum += a.value;         }     }     return sum; }

put

(若bucket第一个结点插入则使用CAS,否则加锁)

public V put(K key, V value) {     return putVal(key, value, false); }

整体流程就是首先定义不允许key或value为null的情况放入 。对于每一个放入的值,首先利用spread方法对key的hashcode进行一次hash计算,由此来确定这个值在table中的位置。

1)如果这个位置是空的,那么直接放入,而且不需要加锁操作。

2)如果这个位置存在结点,说明发生了hash碰撞,首先判断这个节点的类型。

a)如果是MOVED节点,则表示正在扩容,帮助进行扩容

b)如果是链表节点(hash >=0),则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况,则只需要更新value值即可。否则依次向后遍历,直到链表尾插入这个结点。 如果加入这个节点以后链表长度大于8,就把这个链表转换成红黑树。

c)如果这个节点的类型已经是树节点的话,直接调用树节点的插入方法进行插入新的值。

3)addCount 增加计数值

/** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) {     if (key == null || value == null) throw new NullPointerException();     int hash = spread(key.hashCode());     int binCount = 0; // 死循环,只有插入成功时才会跳出     for (Node<K,V>[] tab = table;;) {         Node<K,V> f; int n, i, fh;         if (tab == null || (n = tab.length) == 0) // table为空则初始化(延迟初始化)             tab = initTable();         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // hash to index后正好为空,则CAS放入;如果失败那么进入下次循环继续尝试             if (casTabAt(tab, i, null,                          new Node<K,V>(hash, key, value, null)))                 break;                   // no lock when adding to empty bin         } // 如果index处非空,且hash为MOVED(表示该节点是ForwardingNode),则表示有其它线程正在扩容,则一起进行扩容操作。        else if ((fh = f.hash) == MOVED)             tab = helpTransfer(tab, f); // 如果index处非空,且为链表节点或树节点         else {             V oldVal = null; // 对某个bucket上执行添加操作仅需要锁住第一个Node即可(可以保证不会多线程同时对某个bucket进行写入)             synchronized (f) {                 if (tabAt(tab, i) == f) { // 1) 如果是链表节点,那么插入到链表中                     if (fh >= 0) { // binCount是该bucket中元素个数                         binCount = 1;                         for (Node<K,V> e = f;; ++binCount) {                             K ek;                             if (e.hash == hash &&                                 ((ek = e.key) == key ||                                  (ek != null && key.equals(ek)))) {                                 oldVal = e.val;                                 if (!onlyIfAbsent)                                     e.val = value;                                 break;                             }                             Node<K,V> pred = e;                             if ((e = e.next) == null) {                                 pred.next = new Node<K,V>(hash, key,                                                           value, null);                                 break;                             }                         }                     } // 2)如果是红黑树树根,那么插入到红黑树中                     else if (f instanceof TreeBin) {                         Node<K,V> p;                         binCount = 2;                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                                        value)) != null) {                             oldVal = p.val;                             if (!onlyIfAbsent)                                 p.val = value;                         }                     }                 }             } // 插入节点/释放锁之后,如果大小合适调整为红黑树,那么将链表转为红黑树             if (binCount != 0) {                 if (binCount >= TREEIFY_THRESHOLD)                     treeifyBin(tab, i);                 if (oldVal != null)                     return oldVal;                 break;             }         }     } // 将当前ConcurrentHashMap的元素数量+1 ,如果超过阈值,那么进行扩容     addCount(1L, binCount);     return null; }

 treeifyBin

(有锁,数组较小则扩容,较大则转为红黑树

扩容

tryPresize

tryPresize在putAll以及treeifyBin中调用

addCount

x=1,check=bucketCount

private final void addCount(long x, int check) { // 计数值加x // 利用CAS方法更新baseCount的值       CounterCell[] as; long b, s;     if ((as = counterCells) != null ||         !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { // 如果CAS更新baseCount失败或者counterCells不为空,那么尝试CAS更新当前线程的hashCode对应的bucket的value         CounterCell a; long v; int m;         boolean uncontended = true;  if (as == null || (m = as.length - 1) < 0 ||             (a = as[ThreadLocalRandom.getProbe() & m]) == null ||             !(uncontended =               U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { // 如果两次CAS都失败了,那么调用fullAddCount方法             fullAddCount(x, uncontended);             return;         }         if (check <= 1)             return;         s = sumCount();     } // 以上与扩容无关,如果check值大于等于0 则需要检查是否需要进行扩容操作      if (check >= 0) {         Node<K,V>[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&                (n = tab.length) < MAXIMUM_CAPACITY) {             int rs = resizeStamp(n); // 如果sizeCtl是小于0的,说明有其他线程正在执行扩容操作,nextTable一定不为空             if (sc < 0) {                 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||                     sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||                     transferIndex <= 0)                     break;     // 协助扩容 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))                     transfer(tab, nt);             } // 当前线程是唯一的或是第一个发起扩容的线程  此时nextTable=null             else if (U.compareAndSwapInt(this, SIZECTL, sc,                                          (rs << RESIZE_STAMP_SHIFT) + 2)) // 发起扩容                 transfer(tab, null);             s = sumCount();         }     } }

 

transfer

当table容量不足的时候,即table的元素数量达到容量阈值sizeCtl,需要对table进行扩容。 整个扩容分为两部分:

1)构建一个nextTable,大小为table的两倍。

2)把table的数据复制到nextTable中。

java map集合_java遍历map集合 (https://mushiming.com/)  第1张

这两个过程在单线程下实现很简单,但是ConcurrentHashMap是支持并发插入的,扩容操作自然也会有并发的出现,这种情况下,第二步可以支持节点的并发复制,这样性能自然提升不少,但实现的复杂度也上升了一个台阶。

先看第一步,构建nextTable,毫无疑问,这个过程只能有单个线程进行nextTable的初始化。

通过Unsafe.compareAndSwapInt修改sizeCtl值,保证只有一个线程能够初始化nextTable,扩容后的数组长度为原来的两倍。

节点从table移动到nextTable,大体思想是遍历、复制的过程。

1)首先根据运算得到需要遍历的次数i,然后利用tabAt方法获得i位置的元素f,初始化一个ForwardingNode实例fwd。

2)如果f==null,则在table中的i位置放入fwd,这个过程是采用

Unsafe.compareAndSwapObjectf方法实现的,很巧妙的实现了节点的并发移动。

3)如果f是链表的头节点,就构造一个反序链表,把他们分别放在nextTable的i和i+n的位置上,移动完成,采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。

4)如果f是TreeBin节点,也做一个反序处理,并判断是否需要untreeify,把处理的结果分别放在nextTable的i和i+n的位置上,移动完成,同样采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。

5)遍历过所有的节点以后就完成了复制工作,把table指向nextTable,并更新sizeCtl为新数组大小的0.75倍 ,扩容完成。

 

在多线程环境下,ConcurrentHashMap用两点来保证正确性:ForwardingNode和synchronized。当一个线程遍历到的节点如果是ForwardingNode,则继续往后遍历,如果不是,则将该节点加锁,防止其他线程进入,完成后设置ForwardingNode节点,以便要其他线程可以看到该节点已经处理过了,如此交叉进行,高效而又安全。

 

get(无锁)

public V get(Object key) {     Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;     int h = spread(key.hashCode());     if ((tab = table) != null && (n = tab.length) > 0 &&         (e = tabAt(tab, (n - 1) & h)) != null) {         if ((eh = e.hash) == h) { // bucket中第一个结点就是我们要找的,直接返回             if ((ek = e.key) == key || (ek != null && key.equals(ek)))                 return e.val;         }         else if (eh < 0)            // bucket中第一个结点是红黑树根,则调用find方法去找             return (p = e.find(h, key)) != null ? p.val : null; // bucket中第一个结点是链表,则遍历链表查找         while ((e = e.next) != null) {             if (e.hash == h &&                 ((ek = e.key) == key || (ek != null && key.equals(ek))))                 return e.val;         }     }     return null; }

untreeify(无锁)

remove(有锁)

分段锁实现

采用 Segment + HashEntry的方式进行实现

java map集合_java遍历map集合 (https://mushiming.com/)  第2张

put

当执行 put方法插入数据时,根据key的hash值,在 Segment数组中找到相应的位置,如果相应位置的 Segment还未初始化,则通过CAS进行赋值,接着执行 Segment对象的 put方法通过加锁机制插入数据,实现如下:

场景:线程A和线程B同时执行相同 Segment对象的 put方法

1、线程A执行 tryLock()方法成功获取锁,则把 HashEntry对象插入到相应的位置;

2、线程B获取锁失败,则执行 scanAndLockForPut()方法,在 scanAndLockForPut方法中,会通过重复执行 tryLock()方法尝试获取锁,在多处理器环境下,重复次数为64,单处理器重复次数为1,当执行 tryLock()方法的次数超过上限时,则执行 lock()方法挂起线程B;

3、当线程A执行完插入操作时,会通过 unlock()方法释放锁,接着唤醒线程B继续执行;

size

因为 ConcurrentHashMap是可以并发插入数据的,所以在准确计算元素时存在一定的难度,一般的思路是统计每个 Segment对象中的元素个数,然后进行累加,但是这种方式计算出来的结果并不一样的准确的,因为在计算后面几个 Segment的元素个数时,已经计算过的 Segment同时可能有数据的插入或则删除。

先采用不加锁的方式,连续计算元素的个数,最多计算3次: 1、如果前后两次计算结果相同,则说明计算出来的元素个数是准确的; 2、如果前后两次计算结果都不同,则给每个 Segment进行加锁,再计算一次元素的个数;

ConcurrentSkipListMap

ConcurrentSkipListMap有几个ConcurrentHashMap 不能比拟的优点:

  1、ConcurrentSkipListMap 的key是有序的。

2、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是log(N),和线程数几乎无关。也就是说在数据量一定的情况下,并发的线程越多,ConcurrentSkipListMap越能体现出他的优势。

 

SkipList 跳表:

跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。

下面来研究一下跳表的核心思想:

先从链表开始,如果是一个简单的链表,那么我们知道在链表中查找一个元素I的话,需要将整个链表遍历一次。

java map集合_java遍历map集合 (https://mushiming.com/)  第3张  

 如果是说链表是排序的,并且节点中还存储了指向前面第二个节点的指针的话,那么在查找一个节点时,仅仅需要遍历N/2个节点即可。

java map集合_java遍历map集合 (https://mushiming.com/)  第4张

这基本上就是跳表的核心思想,其实也是一种通过“空间来换取时间”的一个算法,通过在每个节点中增加了向前的指针,从而提升查找的效率。

Map实现类之间的区别

HashMap与ConcurrentHashMap区别

1)前者允许key或value为null,后者不允许

2)前者不是线程安全的,后者是

HashMap、TreeMap与LinkedHashMap区别

1)HashMap遍历时,取得数据的顺序是完全随机的;

TreeMap可以按照自然顺序或Comparator排序;

LinkedHashMap可以按照插入顺序或访问顺序排序,且get的效率(O(1))比TreeMap(O(logn))更高。

2)HashMap底层基于哈希表,数组+链表/红黑树;

TreeMap底层基于红黑树

LinkedHashMap底层基于HashMap与环形双向链表

3)就get和put效率而言,HashMap是最高的,LinkedHashMap次之,TreeMap最次。

HashMap与Hashtable区别

1. 扩容策略:Hashtable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂(*2+1),而HashMap则要求一定为2的整数次幂(*2)。

2. 允许null:Hashtable中key和value都不允许为null,而HashMap中key和value都允许为null(key只能有一个为null,而value则可以有多个为null)。

3. 线程安全:前者不是线程安全的,后者是;

ConcurrentHashMap、Collections.synchronizedMap与Hashtable的异同

它们都是同步Map,但三者实现同步的机制不同;后两者都是简单地在方法上加synchronized实现的,锁的粒度较大;前者是基于CAS和synchronized实现的,锁的粒度较小,大部分都是lock-free无锁实现同步的。

ConcurrentHashMap还提供了putIfAbsent同步方法。

THE END

发表回复