【java】java集合框架

水深无声 2023-09-23 19:59 13阅读 0赞

### 目录 ###

*  一.集合类型
 *  二.集合的不同
 *  三.List解析
 *   *  1.ArrayList
     *  2.LinkedList
     *  3.Vector
 *  四.Set解析
 *   *  1.HashSet
     *  2.TreeSet
     *  3.LinkedHashSet
 *  五.Map解析
 *   *  1.HashMap
     *  2.TreeMap
     *  3.HashTable
     *  4.ConcurrentHashMap

# 一.集合类型 #

> 集合类型和关系(我画的比较简略，其中有很多继承实现关系都没有画),如下图

![在这里插入图片描述][9a4cf894a8c94b8aaa76b026c87e6637.png]

# 二.集合的不同 #

<table> 
 <thead> 
  <tr> 
   <th>集合类型</th> 
   <th>元素是否重复</th> 
   <th>元素是否有序</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>List(单列集合)</td> 
   <td>可重复</td> 
   <td>有序</td> 
  </tr> 
  <tr> 
   <td>Set(单列集合)</td> 
   <td>不可重复</td> 
   <td>无序</td> 
  </tr> 
  <tr> 
   <td>Map(双列集合)</td> 
   <td>K不可重复，V可重复</td> 
   <td>有序</td> 
  </tr> 
 </tbody> 
</table>

# 三.List解析 #

## 1.ArrayList ##

> ArrayList底层是数组。  
> 查询：因为数组结构是连续的空间，可以迅速根据数组下标找到元素，所以ArrayList查询比较快。  
> 增删：因为增加一个新元素，数组会复制一个新数组，把新增元素和之前元素放进去，删除也是数组元素会移动，所以速度比较慢。  
> 线程异步。

//默认初始容量为10
    private static final int DEFAULT_CAPACITY = 10;
    //指定ArrayList容量为0时，返回该空数组
    private static final Object[] EMPTY_ELEMENTDATA = {
        };
    //没有指定容量时，默认返回该空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    //该数组保存添加到ArrayList里的元素
    transient Object[] elementData;
    
    /**
     * ArrayList有参构造器
     */
    public ArrayList(int initialCapacity) {
        
        //指定容量则创建对应容量数组
        if (initialCapacity > 0) {
        
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        
            //指定容量为0返回 EMPTY_ELEMENTDATA
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        }
     }
    
    /**
     * ArrayList无参构造器
     */
    public ArrayList() {
        
        //未指定容量返回 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

## 2.LinkedList ##

> LinkedList底层是双向链表(一条记录数据，一条记录位置，所以是有序的)。  
> 查询：因为链表不是连续的地址，是一个节点和一个节点连接到一起，所以查询比较慢，因为每次都需要重头开始查找，所以查询速度比较慢。  
> 增删：因为增删会直接让节点相连或者断掉节点，对整体没有影响，所以增删速度比较快。  
> 线程异步。

transient int size = 0;   //LinkedList中存放的元素个数
    
        transient Node<E> first;  //头节点
        
        transient Node<E> last;   //尾节点
    
    	 //构造方法，创建一个空的列表
        public LinkedList() {
        
        }
    
        //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作
        public LinkedList(Collection<? extends E> c) {
        
            this();
            addAll(c);
        }

## 3.Vector ##

> Vector底层是数组。因为是线程同步的，某一时刻只能有一个线程访问Vector，所以速度比较慢，ArrayList就是用来替代Vector集合的。  
> 线程同步(方法加了synchronized关键字保证线程同步)。

# 四.Set解析 #

## 1.HashSet ##

> HashSet底层是哈希表,就是实现了HashMap。  
> 初始：哈希表 = 数组 + 链表  
> 当长度大于8并且表的长度大于64，哈希表 = 数组 + 红黑树  
> 当长度大于8并且表的长度小于64，哈希表会扩容  
> 当红黑树的节点等于小于6的时候 ，哈希表 = 数组 + 链表

> 存取元素：HashSet 首先判断两个元素的哈希值，如果哈希值一样，接着会比较equals 方法 如果 equls 结果为 true ，HashSet 就视为同一个元素。如果 equals 为 false 就不是同一个元素。

//初始化一个HashMap，实现HashSet。
        private transient HashMap<E,Object> map;
        
        //new一个不可变对象
        private static final Object PRESENT = new Object();
    
        //构造方法就是new一个HashMap
        public HashSet() {
        
            map = new HashMap<>();
        }
        
        //新增的时候就是把元素放到K中，所以不能重复，而V中放的是不可变的对象
        public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
        }

## 2.TreeSet ##

> TreeSet底层是红黑树(是一种特殊的二叉树)，就是实现了TreeMap。

> 新增原理：  
> 1.TreeSet()是使用二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。  
> 2. Integer 和 String 对象都可以进行默认的 TreeSet 排序，而自定义类的对象是不可以的，自 己定义的类必须实现 Comparable 接口，并且覆写相应的 compareTo()函数，才可以正常使用。

## 3.LinkedHashSet ##

> LinkedHashSet是HashSet的子类，它是有序的，因为包含了两个链表，一个链表记录数据，一个链表记录元素的位置，所以是有序的。

# 五.Map解析 #

[HashMap底层实现原理及面试题][HashMap] **键值对(Key-Value)结构**。

## 1.HashMap ##

> 线程异步(线程不安全)，底层是哈希表。  
> K不能重复，V可重复。  
> K和V都可以为Null。

## 2.TreeMap ##

> 底层是红黑树。  
> K不能重复，V可重复。

## 3.HashTable ##

> 线程同步(线程安全)，底层是哈希表。  
> K不能重复，V可重复。  
> K和V都不能为Null。

## 4.ConcurrentHashMap ##

> 线程同步(线程安全)，底层是哈希表。  
> ConcurrentHashMap本质上是一个HashMap，因此功能和HashMap是一样的，但是ConcurrentHashMap在HashMap的基础上提供了并发安全的一个实现。并发安全的主要实现主要通过对于Node节点去加锁，来保证数据更新的安全性。

[9a4cf894a8c94b8aaa76b026c87e6637.png]: https://img-blog.csdnimg.cn/9a4cf894a8c94b8aaa76b026c87e6637.png
[HashMap]: https://blog.csdn.net/twotwo22222/article/details/128426417?spm=1001.2014.3001.5501