java 集合总结

蔚落 2022-10-16 10:27 148阅读 0赞

### 一、集合类型 ###

（1）集合

List  Queue Set  Map

List  Queue Set 实现Collection接口

（2）Collections工具类

reverse(List list)：反转

shuffle(List list),随机排序

sort(List list, Comparator c);定制排序，由Comparator控制排序逻辑

swap(List list, int i , int j),交换两个索引位置的元素

rotate((List list, int distance),旋转

binarySearch(List list, Object key), 对List进行二分查找，返回索引，注意List必须是有序的

max(Collection coll, Comparator c)，根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)

fill(List list, Object obj),用元素obj填充list中所有元素

frequency(Collection c, Object o)，统计元素出现次数

indexOfSubList(List list, List target), 统计targe在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target).

boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素

emptyXXX(),返回一个空的只读集合（这不知用意何在？）

singleXXX()，返回一个只包含指定对象，只有一个元素，只读的集合。

unmodifiablleXXX()，返回指定集合对象的只读视图。

synchronizedXXX()等方法，来将集合包装成线程安全的集合

### 二、List  ###

<table> 
 <thead> 
  <tr> 
   <th>List&nbsp;</th> 
   <th>存储方式</th> 
   <th>初始容量</th> 
   <th>容量增长</th> 
   <th>同步方式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>ArrayList</td> 
   <td>数组</td> 
   <td>空数组,10</td> 
   <td>oldSize + oldSize/2</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>Vector</td> 
   <td>数组</td> 
   <td>10，增量为0</td> 
   <td>oldSize + oldSize</td> 
   <td>synchronized</td> 
  </tr> 
  <tr> 
   <td>LinkedList</td> 
   <td> <p>jdk6带头结点的双向循环链表</p> <p>jdk7不带头结点的双向链表，增加两个节点指针first、last指向首尾节点</p> </td> 
   <td></td> 
   <td></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>CopyOnWriteArrayList</td> 
   <td>数组</td> 
   <td>0</td> 
   <td></td> 
   <td>ReentrantLock</td> 
  </tr> 
 </tbody> 
</table>

###  ###

### 三、Queue ###

（1）offer，add 区别：

一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。

这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。

（2）poll，remove 区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

（3）peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

<table> 
 <thead> 
  <tr> 
   <th>Queue</th> 
   <th>存储方式</th> 
   <th>初始容量</th> 
   <th>容量增长</th> 
   <th>同步方式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>PriorityQueue</td> 
   <td>数组，comparator</td> 
   <td>11</td> 
   <td>oldCapacity + ((oldCapacity &lt; 64) ? &nbsp;<br> (oldCapacity + 2) : (oldCapacity &gt;&gt; 1))</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>ConcurrentLinkedQueue</td> 
   <td>链表</td> 
   <td> <p></p> </td> 
   <td></td> 
   <td>CAS</td> 
  </tr> 
  <tr> 
   <td>DelayQueue</td> 
   <td>PriorityQueue</td> 
   <td></td> 
   <td></td> 
   <td>ReentrantLock Condition</td> 
  </tr> 
  <tr> 
   <td>ArrayBlockingQueue</td> 
   <td>数组，是否fair</td> 
   <td></td> 
   <td></td> 
   <td>ReentrantLock、Empty和Full Condition</td> 
  </tr> 
  <tr> 
   <td>LinkedBlockingQueue</td> 
   <td>链表</td> 
   <td></td> 
   <td></td> 
   <td>take和put ReentrantLock、Empty和Full&nbsp; Condition</td> 
  </tr> 
  <tr> 
   <td>LinkedTransferQueue</td> 
   <td>链表</td> 
   <td></td> 
   <td></td> 
   <td>LockSupport</td> 
  </tr> 
  <tr> 
   <td>PriorityBlockingQueue</td> 
   <td>数组</td> 
   <td></td> 
   <td>oldCap + ((oldCap &lt; 64) ?<br> &nbsp;(oldCap + 2) :&nbsp;&nbsp;(oldCap &gt;&gt; 1))</td> 
   <td>ReentrantLock、Condition</td> 
  </tr> 
  <tr> 
   <td>SynchronousQueue&nbsp;</td> 
   <td>TransferQueue，TransferStack，是否fair</td> 
   <td></td> 
   <td></td> 
   <td>CAS</td> 
  </tr> 
 </tbody> 
</table>

Deque继承Queue

<table> 
 <thead> 
  <tr> 
   <th style="width:394px;">Deque</th> 
   <th style="width:288px;">存储方式</th> 
   <th style="width:262px;">初始容量</th> 
   <th style="width:270px;">容量增长</th> 
   <th style="width:304px;">同步方式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>LinkedList</td> 
   <td> <p>链表</p> </td> 
   <td style="width:262px;"></td> 
   <td style="width:270px;"></td> 
   <td style="width:304px;"></td> 
  </tr> 
  <tr> 
   <td style="width:394px;">ArrayDeque</td> 
   <td style="width:288px;">数组</td> 
   <td style="width:262px;">8</td> 
   <td style="width:270px;">n &lt;&lt; 1</td> 
   <td style="width:304px;"></td> 
  </tr> 
  <tr> 
   <td style="width:394px;">ConcurrentLinkedDeque</td> 
   <td style="width:288px;">链表</td> 
   <td style="width:262px;"></td> 
   <td style="width:270px;"></td> 
   <td style="width:304px;">CAS</td> 
  </tr> 
  <tr> 
   <td style="width:394px;">LinkedBlockingDeque</td> 
   <td style="width:288px;">链表</td> 
   <td style="width:262px;">Integer.MAX_VALUE</td> 
   <td style="width:270px;"></td> 
   <td style="width:304px;">ReentrantLock、Empty和Full Condition</td> 
  </tr> 
 </tbody> 
</table>

### 四、Map ###

<table> 
 <thead> 
  <tr> 
   <th>Map</th> 
   <th>存储方式</th> 
   <th>初始容量</th> 
   <th>容量增长</th> 
   <th>同步方式</th> 
   <th>特性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashMap</td> 
   <td> <p>&nbsp;jdk7 entry数组 + 链表</p> <p>jdk8 Node数组 + 链表/红黑树</p> </td> 
   <td>16</td> 
   <td>table.size*2</td> 
   <td></td> 
   <td>key、value可空</td> 
  </tr> 
  <tr> 
   <td>Hashtable</td> 
   <td>数组</td> 
   <td>11</td> 
   <td>table.size*2 + 1&nbsp;</td> 
   <td>synchronized</td> 
   <td>key、value不可空</td> 
  </tr> 
  <tr> 
   <td>LinkedHashMap</td> 
   <td>链表</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td>记录添加顺序</td> 
  </tr> 
  <tr> 
   <td>TreeMap</td> 
   <td>红黑树，comparator</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td>默认key不可空，排序&nbsp;</td> 
  </tr> 
  <tr> 
   <td>EnumMap</td> 
   <td>key数组 value数组 enum.ordinal下标</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td>key不可空 &nbsp;value为空使用NULLObject填充</td> 
  </tr> 
  <tr> 
   <td>ConcurrentHashMap</td> 
   <td> <p>JDK7:Segment数组 + HashEntry数组 + 链表</p> <p>JDK8:Node数组 + 链表 + 红黑树&nbsp;</p> </td> 
   <td></td> 
   <td></td> 
   <td> <p>分段锁 ReentranLock、</p> <p>synchronized和CAS</p> </td> 
   <td>key、value不可空</td> 
  </tr> 
  <tr> 
   <td>ConcurrentSkipListMap</td> 
   <td>跳跃链表</td> 
   <td></td> 
   <td></td> 
   <td></td> 
   <td>key、value不可空</td> 
  </tr> 
 </tbody> 
</table>

### 五、Set ###

<table> 
 <thead> 
  <tr> 
   <th>Set</th> 
   <th>存储方式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashSet</td> 
   <td>HashMap</td> 
  </tr> 
  <tr> 
   <td>LinkedHashSet</td> 
   <td>LinkedHashMap</td> 
  </tr> 
  <tr> 
   <td>TreeSet</td> 
   <td>TreeMap</td> 
  </tr> 
  <tr> 
   <td>ConcurrentSkipListSet</td> 
   <td>ConcurrentSkipListMap</td> 
  </tr> 
  <tr> 
   <td>CopyOnWriteArraySet</td> 
   <td>CopyOnWriteArrayList</td> 
  </tr> 
 </tbody> 
</table>

### 六、常见题目 ###

（1）说说List,Set,Map三者的区别  
（2）Arraylist 与 LinkedList 区别  
RandomAccess接口、双向链表和双向循环链表  
（3）ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢  
（4）说一说 ArrayList 的扩容机制吧  
（5）HashMap 和 Hashtable 的区别  
（6）HashMap 和 HashSet区别  
（7）HashSet如何检查重复  
（8）HashMap的底层实现  
JDK1.8之前  
JDK1.8之后  
（9）HashMap 的长度为什么是2的幂次方  
（10）HashMap 多线程操作导致死循环问题  
（11）ConcurrentHashMap 和 Hashtable 的区别  
（12）ConcurrentHashMap线程安全的具体实现方式/底层具体实现  
JDK1.7、JDK1.8   
（13）comparable 和 Comparator的区别  
Comparator定制排序、重写compareTo方法实现排序  
（14）集合框架底层数据结构总结  
Collection  
1. List  
2. Set  
Map