【计算机基础】java集合常见类，线程不安全

系统管理员 2023-02-25 11:22 10阅读 0赞

# 一、java集合URL #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3htbDE5OTY_size_16_color_FFFFFF_t_70]  
图中 …框是接口；----框是抽象类；——框是类；  
常用的类：ArrayList,LinkedList,HashMap,HashSet

# 二、集合的底层实现 #

## A、 List ##

<table> 
 <thead> 
  <tr> 
   <th>List集合</th> 
   <th>原 理</th> 
   <th>特点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ArraryList</td> 
   <td>数组</td> 
   <td>初始空间10，每次到到达上限扩充1.5倍空间，有序的连续空间数组所以查询快捷，删除添加低效</td> 
  </tr> 
  <tr> 
   <td>LinkedList</td> 
   <td>双向链表</td> 
   <td>不连续的存储空间，查询低效，删除添加高效</td> 
  </tr> 
 </tbody> 
</table>

### ArraryList数组的添加是线程不安全的： ###

报错常见异常：  
java.util.ConcurrentModificationException

### 解决线程不安全的办法： ###

#### 1、 new Vector<>() ####

Vector实现了List接口，重写add方法，源码如下：

public synchronized boolean add(E e) {   
        modCount++;    
        ensureCapacityHelper(elementCount + 1);                             elementData[elementCount++] = e;    
        return true;
    }

#### 2、Collections ####

Collections.synchronizedList(new ArrayList<>())

final Collection<E> c;  // Backing Collection
    
    public boolean add(E e) {    
        synchronized (mutex) {
            return c.add(e);
        }
    }

Collections类下的add方法，c.add 也就是Collection接口下的add

#### 3、new CopyOnWriteArrayList<>() ####

写时复制方法， 实现了List接口，重写了add方法,源码如下：

public boolean add(E e) {    
        final ReentrantLock lock = this.lock;    
        lock.lock();    
        try {        
            Object[] elements = getArray();        
            int len = elements.length;        
            Object[] newElements = 
            Arrays.copyOf(elements, len + 1);        
            newElements[len] = e;        
            setArray(newElements);        
            return true;    
        } 
        finally {        
            lock.unlock();    
        }
    }

写时复制，字面含义，在添加信息的时候，不是直接在上面进行修改，而知复制出一份来，进行修改。有点读写分离的意思。  
使用可重入锁，保证数据的并发安全，获取原数组和数组长度，copyOf到一个新的内存+1的区域，把待插入元素插入数组后返回，释放锁。

## B、Set ##

<table> 
 <thead> 
  <tr> 
   <th>set集合</th> 
   <th>原理</th> 
   <th>特点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashSet</td> 
   <td>底层是hashMap</td> 
   <td>有序不可重复，在add的时候，是根据map的key进行插入的，value是一个Object类型的常量PRESENT.key是不可重复的可为null</td> 
  </tr> 
  <tr> 
   <td>TreeSet</td> 
   <td>自平衡二叉树</td> 
   <td>根据大小排序有序，不可重复</td> 
  </tr> 
  <tr> 
   <td>LinkHashSet</td> 
   <td>链表</td> 
   <td>根据添加顺序，不可重复</td> 
  </tr> 
 </tbody> 
</table>

### HashSet ###

public static void main(String[] args) {    
        Set<Integer> integers = new HashSet<>();    
        integers.add(2);    
        integers.add(1);    
        integers.add(3);    
        integers.add(4);    
        integers.add(3);    
        integers.add(null);    
        System.out.println("integers = " + integers);
    }

> integers = \[null, 1, 2, 3, 4\]

### TreeSet ###

public static void main(String[] args) {    
        TreeSet treeSet = new TreeSet();    
        treeSet.add(2);    
        treeSet.add(1);
        treeSet.add(3); 
        treeSet.add(4);    
        treeSet.add(3);    
        System.out.println("treeSet = " + treeSet);
    }

> treeSet = \[1, 2, 3, 4\]

### LinkHashSet ###

public static void main(String[] args) {    
            LinkedHashSet linkedHashSet = new LinkedHashSet();    
            linkedHashSet.add(2);    
            linkedHashSet.add(1);
            linkedHashSet.add(3); 
            linkedHashSet.add(4);    
            linkedHashSet.add(3);    
            System.out.println("linkedHashSet = " + linkedHashSet);
    }

> linkedHashSet = \[2, 1, 3, 4\]

### HashSet线程不安全 ###

解决办法同上ArrayList

1.  Collections.synchronizedSet(new HashSet<>());
2.  new CopyOnWriteArraySet<>();  
    注意CopyOnWriteArraySet的底层其实还是CopyOnWriteArrayList

public CopyOnWriteArraySet() {   
        al = new CopyOnWriteArrayList<E>();
    }

## C、Map ##

<table> 
 <thead> 
  <tr> 
   <th>map集合</th> 
   <th>原理</th> 
   <th>特点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashMap</td> 
   <td>数组（哈希表）+链表（链表长度&gt;8转化为红黑树）</td> 
   <td>key,value可null,初始容量大小16，加载因子0.75</td> 
  </tr> 
 </tbody> 
</table>

### HashMap线程不安全 ###

解决办法类似HashSet

1.  Collections.synchronizedMap(new HashMap<>());
2.  new ConcurrentHashMap<>();  
    ConcurrentHashMap是在添加的时候，可以通过putVal()添加，源码如下:

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

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;
        }

在重写的putVal()方法中，通过synchronized保证线程的安全  
想要看懂这里源码的意思，先要理解HashMap的底层实现原理，也就是数组+链表

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3htbDE5OTY_size_16_color_FFFFFF_t_70]: /images/20230209/58aec8e6cf9644d0846e23ea28468945.png