常见数据结构浅析

电玩女神 2024-02-05 18:04 24阅读 0赞

### 常见数据结构浅析 ###

#### 1.ArrayList和CopyOnWriteArrayList ####

`ArrayList`

> `特点`
> 
> 1.  线程不安全
> 2.  底层数据结构是数组（查询快，增删慢，支持快速随机访问）
> 3.  内存占用会存在部分浪费，末尾会预留一部分容量空间

`容量`

> 当创建一个ArrayList对象时，它会分配一定的初始容量，通常为10  
> private static final int DEFAULT\_CAPACITY = 10;

`添加元素：`

> `1.判断需要的容量是不是大于数组长度`  
> if (minCapacity - elementData.length > 0)  
> grow(minCapacity);  
> `2.扩容 扩为原来的1.5倍`  
> int newCapacity = oldCapacity + (oldCapacity >> 1);
> 
> `3.复制原数据到新数组`  
> elementData = Arrays.copyOf(elementData, newCapacity);
> 
> `4.把新元素添加到数组末尾`  
> elementData\[size++\] = e;

`移除元素：`

> `1.计算一个元素得位置`  
> int numMoved = size - index - 1;  
> `2.复制`  
> 把原数组的第index+1后面的数据复制到原数组的index位置复制长度为size - index - 1  
> if (numMoved > 0)  
> System.arraycopy(elementData, index+1, elementData, index,  
> numMoved);  
> `3.把数组最后一个元素置空`  
> elementData\[–size\] = null;

`解决ArraryList线程不安全`

> 1.vector  
> 2.Collections.synchronizedList(new ArrayList<>());  
> 3.CopyOnWriteArrayList

`CopyOnWriteArrayList`

> `写时复制：` CopyOnWrite 容器即写时复制容器。往一个容器添加元素时，不直接往Object\[\]添加，而是先将当前容器Object\[\]进行copy 复制出一个新得容器，Object\[\] newElements，然后往新的容器newElements里添加元素，添加完元素后再将原容器的引用指向新得容器setArray(newElements)。这样做的好处是可以对CopyOnWrite容器进行并发读，而不需要加锁，因为当前容器不添加任何元素。所以CopyOnWrite是一种读写分离思想，即读和写用的不同容器

`写的时候使用了ReentrantLock枷锁`

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

`数组array本身使用了volatile，保证多线程可见性`

private transient volatile Object[] array;

#### 2.HashSet和CopyOnWriteArraySet ####

> HashSet线程不安全其底层就是一个HashMap<E,Object> HashSet的add方法

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

> PRESENT是（常量）：

private static final Object PRESENT = new Object();

`CopyOnWriteArraySet`

> 底层依然是CopyOnWriteArrayList，线程安全

#### 3.HashMap与ConcurrentHashMap（jdk1.8） ####

<table> 
 <thead> 
  <tr> 
   <th>hashMap</th> 
   <th>concurrentHashMap</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>线程不安全的</td> 
   <td>线程安全</td> 
  </tr> 
  <tr> 
   <td>数组 + 链表 + 红黑树</td> 
   <td>分段数组 + 链表 + 红黑树</td> 
  </tr> 
  <tr> 
   <td>高并发情况下，put、remove 成员变量时可能产生线程安全问题，需加锁</td> 
   <td>线程安全，因为底层代码在操作每一个Node时都会对Node加锁synchronized，保证线程安全</td> 
  </tr> 
  <tr> 
   <td>读取不加锁</td> 
   <td>读取数据时不加锁，高效，且因为map中的value值是添加volatile关键字修饰的，可保证读取到最新值，降低CPU负载</td> 
  </tr> 
  <tr> 
   <td>元素插入后判断数组长度是否超阈，默认阈值0.75，若超阈则进行扩容，扩容大小为原数组的2的幂次方(原数组长度往左位移1)，若原数组所在内存上没有连续的可用空间，则申请新的可用连续空间，将旧数组复制到新的地址，再将旧数组置为null，等待GC回收</td> 
   <td>同hashMap</td> 
  </tr> 
 </tbody> 
</table>

hashMap结构：  
![在这里插入图片描述][61da8ee2a99d43d89a10115d1f36d95c.png]

> `hash冲突：`当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。  
> 开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法.(链表/红黑树就是为了解决hash冲突而存在的)  
> HashMap即是采用了链地址法.  
> JDK7 使用了数组+链表的方式  
> JDK8 使用了数组+链表+红黑树的方式

**扩容：**

> 1.先把原数组的大小扩为原来的一倍，比如现在是16，扩容后就是32
> 
> `java newCap = oldCap << 1`  
> 2.把旧数组的元素赋值给新得数组  
> `newTab[e.hash & (newCap - 1)] = e;`

**触发扩容的条件：**

> 扩容的方法叫`resize`  
> 1.进入的时候判断Node的长度为0

if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;

> 2.当数组长度达到 加载因子\*数字最大长度

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

threshold = newThr;

if (++size > threshold)
                resize();

#### 4 队列 ####

> `ArrayBlockingQueue:`是一个基于数组结构的有界队列按FIFO原则对元素排序  
> `LinkedBlockingQueue：`一个基于链表的阻塞队列按FIFO原则对元素排序，吞吐量高于ArrayBlockingQueue  
> `SynchronousQueue：`一个不存储元素得队列，每个插入操作必须等到另一个线程的调用移除，否则插入操作一直处于阻塞状态，吞吐量要高于LinkedBlockingQueue

**队列常用API：**  
![在这里插入图片描述][a5b7c5517256422da5c126c86c3d37bc.png]  
**依次对应上面的每一列API**  
![在这里插入图片描述][5f8aa7f3f3f9453da68128a1ce211bfe.png]

> Executors.newCachedThreadPool() 底层是SynchronousQueue  
> 其他方式创建的是LinkedBlockingQueue

[61da8ee2a99d43d89a10115d1f36d95c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f41589578e374a92b5d294c7e792c7aa.png
[a5b7c5517256422da5c126c86c3d37bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c3fabe1ba89a41ae9479a15cba4ecbda.png
[5f8aa7f3f3f9453da68128a1ce211bfe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/06601db28b3f46bdb4eb0142b738ad70.png