集合的线程安全setmap

朱雀 2022-09-11 09:16 113阅读 0赞

# set #

## HashSet ##

package com.dongguo.threadsafe;
    
    import java.util.HashSet;
    import java.util.Set;
    import java.util.UUID;
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:28 * @description: Set集合线程不安全演示 */
    public class ThreadDemo2 { 
        public static void main(String[] args) { 
            Set<String> set = new HashSet<>();
    
            for (int i = 0; i < 30; i++) { 
                new Thread(()->{ 
                    set.add(UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(set);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210903182643509][]

HashSet的add方法

public boolean add(E var1) { 
        return this.map.put(var1, PRESENT) == null;
    }

其实调用的是HashMap的put()方法

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

HashSet的底层使用的就是HashMap，具体可转到HashMap的put()方法

## Collections.synchronizedSet() ##

package com.dongguo.threadsafe;
    
    
    import java.util.Collections;
    import java.util.HashSet;
    import java.util.Set;
    import java.util.UUID;
    import java.util.concurrent.CopyOnWriteArraySet;
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:28 * @description: Set集合线程安全演示 */
    public class ThreadDemo4 { 
        public static void main(String[] args) { 
            Set<String> set = Collections.synchronizedSet(new HashSet<>());
            for (int i = 0; i < 30; i++) { 
                new Thread(()->{ 
                    set.add(UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(set);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210910133050438][]

线程安全

public boolean add(E e) { 
                synchronized (mutex) { return c.add(e);}
            }

使用synchronized同步代码块来保证线程安全

## CopyOnWriteArraySet ##

package com.dongguo.threadsafe;
    
    import java.util.HashSet;
    import java.util.Set;
    import java.util.UUID;
    import java.util.concurrent.CopyOnWriteArraySet;
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:28 * @description: Set集合线程安全演示 */
    public class ThreadDemo2 { 
        public static void main(String[] args) { 
    // Set<String> set = new HashSet<>();
            Set<String> set = new CopyOnWriteArraySet<>();
            for (int i = 0; i < 30; i++) { 
                new Thread(()->{ 
                    set.add(UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(set);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210903182900243][]

线程安全

public boolean add(E e) { 
        return al.addIfAbsent(e);
    }

调用CopyOnWriteArrayList的addIfAbsent方法

public boolean addIfAbsent(E e) { 
        Object[] snapshot = getArray();
        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
    }
    
    ...
        private boolean addIfAbsent(E e, Object[] snapshot) { 
            final ReentrantLock lock = this.lock;
            lock.lock();
            try { 
                Object[] current = getArray();
                int len = current.length;
                if (snapshot != current) { 
                    // Optimize for lost race to another addXXX operation
                    int common = Math.min(snapshot.length, len);
                    for (int i = 0; i < common; i++)
                        if (current[i] != snapshot[i] && eq(e, current[i]))
                            return false;
                    if (indexOf(e, current, common, len) >= 0)
                            return false;
                }
                Object[] newElements = Arrays.copyOf(current, len + 1);
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally { 
                lock.unlock();
            }
        }

使用ReentrantLock保证线程安全

# map #

## **HashMap** ##

package com.dongguo.threadsafe;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.UUID;
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:43 * @description: Map集合线程不安全演示 */
    public class ThreadDemo3 { 
        public static void main(String[] args) { 
            Map<String,String> map = new HashMap<>();
            for (int i = 0; i < 30; i++) { 
                String key = String.valueOf(i);
                new Thread(()->{ 
                    map.put(key,UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(map);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210903183053756][]

HashMap并没有进行同步操作

public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { 
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else { 
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { 
                for (int binCount = 0; ; ++binCount) { 
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {  // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。

## HashTable ##

package com.dongguo.threadsafe;
    
    
    import java.util.Hashtable;
    import java.util.Map;
    import java.util.UUID;
    
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:43 * @description: Map集合线程安全演示 */
    public class ThreadDemo6 { 
        public static void main(String[] args) { 
            Map<String,String> map = new Hashtable<>();
     
            for (int i = 0; i < 30; i++) { 
                String key = String.valueOf(i);
                new Thread(()->{ 
                    map.put(key,UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(map);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210910135939209][]

public synchronized V put(K key, V value) { 
        // Make sure the value is not null
        if (value == null) { 
            throw new NullPointerException();
        }
    
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) { 
            if ((entry.hash == hash) && entry.key.equals(key)) { 
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
    
        addEntry(hash, key, value, index);
        return null;
    }

synchronized同步方法

## Collections.synchronizedMap() ##

package com.dongguo.threadsafe;
    
    
    import java.util.*;
    import java.util.concurrent.ConcurrentHashMap;
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:43 * @description: Map集合线程安全演示 */
    public class ThreadDemo5 { 
        public static void main(String[] args) { 
            Map<String,String> map = Collections.synchronizedMap(new HashMap<>());
            for (int i = 0; i < 30; i++) { 
                String key = String.valueOf(i);
                new Thread(()->{ 
                    map.put(key,UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(map);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210910134547692][]

线程安全

public V put(K key, V value) { 
        synchronized (mutex) { return m.put(key, value);}
    }

使用synchronized同步代码块实现线程安全

## **ConcurrentHashMap** ##

在并发编程中使用HashMap可能导致程序死循环，而使用线程安全的HashTable效率又非常低，基于这两个原因，ConcurrentHashMap出现了。

package com.dongguo.threadsafe;
    
    
    import java.util.Map;
    import java.util.UUID;
    import java.util.concurrent.ConcurrentHashMap;
    
    
    /** * @author Dongguo * @date 2021/8/24 0024-10:43 * @description: Map集合线程不安全演示 */
    public class ThreadDemo3 { 
        public static void main(String[] args) { 
    // Map<String,String> map = new HashMap<>();
            Map<String,String> map = new ConcurrentHashMap<>();
            for (int i = 0; i < 30; i++) { 
                String key = String.valueOf(i);
                new Thread(()->{ 
                    map.put(key,UUID.randomUUID().toString().substring(0, 8));
                    System.out.println(map);
                }, "t" + i).start();
            }
        }
    }

运行结果

![image-20210903183246394][]

没有线程安全问题

ConcurrentHashMap的put()使用synchronized

ConcurrentHashMap通过CAS+Synchronized 来保证线程安全问题，

ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段地存

储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数

据也能被其他线程访问。

synchronized只锁定当前链表或红黑树的首节点

public V put(K key, V value) { 
        return putVal(key, value, false);
    }
    
    /** 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)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else { 
                V oldVal = null;
                synchronized (f) { 
                    if (tabAt(tab, i) == f) { 
                        if (fh >= 0) { 
                            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;
                                }
                            }
                        }
                        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;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

[image-20210903182643509]: /images/20220828/ff9a77cfc9714128b79ff44b905efd84.png
[image-20210910133050438]: /images/20220828/3760169b738846da8908d77252ef35d7.png
[image-20210903182900243]: /images/20220828/fd4b131b4acc4ebeaa0608d9c1b6c0d2.png
[image-20210903183053756]: /images/20220828/0aad1c3e32714ee195577d5bbac2fde0.png
[image-20210910135939209]: /images/20220828/b6cabf4a17a6455490e0d467fd14b339.png
[image-20210910134547692]: /images/20220828/6737d9e7ada34b99b2e019bee7148749.png
[image-20210903183246394]: /images/20220828/a35f829d6a0447f3a3a80be29ce5e16b.png