集合Collection和Map结构原理

偏执的太偏执、 2022-03-19 13:54 261阅读 0赞

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th colspan="3" style="text-align:center;">List</th> 
   <th colspan="3" style="text-align:center;">Set</th> 
   <th colspan="4" style="text-align:center;">Map</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>AttributeofAll</td> 
   <td>ArratList</td> 
   <td>LinkedList</td> 
   <td>Vector</td> 
   <td>HashSet</td> 
   <td>TreeSet</td> 
   <td>LinkedHashSet</td> 
   <td>HashMap</td> 
   <td>HashTable</td> 
   <td>LinkedHashMap</td> 
   <td>TreeMap</td> 
  </tr> 
  <tr> 
   <td>数据结构</td> 
   <td>动态数组</td> 
   <td>链表结构，地址任意</td> 
   <td>动态数组</td> 
   <td>哈希表</td> 
   <td>二叉树</td> 
   <td>链表+哈希表</td> 
   <td>散列</td> 
   <td>散列</td> 
   <td>哈希表+链表</td> 
   <td>二叉树</td> 
  </tr> 
  <tr> 
   <td>优点</td> 
   <td>地址连续，索引速度快</td> 
   <td>新增删除新能好</td> 
   <td>实现同步，并发性好</td> 
   <td><strong>add</strong>、<strong>remove</strong>、<strong>contains</strong>方法 的时间复杂度为常量O(1)</td> 
   <td>元素是可排序</td> 
   <td>保留了元素插入顺序，时间复杂度为O(1)</td> 
   <td>定位元素时间复杂度平均能达到O(1)</td> 
   <td>同步</td> 
   <td>可预知迭代顺序</td> 
   <td>根据其键的自然顺序进行排序</td> 
  </tr> 
  <tr> 
   <td>缺点</td> 
   <td>新增||删除性能差</td> 
   <td>索引设计指针移动性能较差</td> 
   <td>同步会损失部分性能</td> 
   <td>元素是无序的</td> 
   <td>但<strong>add</strong>、<strong>remove</strong>和<strong>contains</strong>方法的时间复杂度为O(log(n))</td> 
   <td>性能相对低</td> 
   <td>非同步</td> 
   <td>性能低</td> 
   <td>&nbsp;</td> 
   <td>时间复杂度平均能达到O(log n)</td> 
  </tr> 
  <tr> 
   <td>是否同步</td> 
   <td>no</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>可否重复</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>可否为null</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>初始大小</td> 
   <td>10</td> 
   <td>无</td> 
   <td>10</td> 
   <td>16</td> 
   <td>16</td> 
   <td>16</td> 
   <td>16</td> 
   <td>11</td> 
   <td>16</td> 
   <td>16</td> 
  </tr> 
  <tr> 
   <td>扩容因子</td> 
   <td>0.5</td> 
   <td>无（链表结构直接往后面添加）</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1</td> 
   <td>1+1</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>加载因子</td> 
   <td>1</td> 
   <td>无</td> 
   <td>1</td> 
   <td>0.75</td> 
   <td>0.75</td> 
   <td>0.75</td> 
   <td>0.75</td> 
   <td>0.75</td> 
   <td>0.75</td> 
   <td>0.75</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
  </tr> 
 </tbody> 
</table>