Java常用集合实现原理

向右看齐 2024-02-19 17:24 72阅读 0赞

### 1. JDK常用集合类型 ###

1.  列表：List
2.  栈：Stack，链表的扩展
3.  队列：Queue
4.  集合：Set
5.  字典：Map

### 2. List ###

#### 列表，List接口，常用实现原理及特点 ####

1.  ArrayList：命名已经很明显体现了其特点，Array：数组，其底层实现原理就是数组，达到容量时会自动扩展的动态数组；支持随机访问（根据下标指哪打哪666），读取复杂度为O(1)，插入复杂度O(N)
2.  LinkedList：Linked：链表，底层实现原理就是链表；不支持随机访问，访问指定下标的数据要不断next直到指定index为止，连续读复杂度为O(1)，常规读取复杂度为O(N)，插入复杂度O(1)，特点与数组对应的很明显
3.  Stack：栈结构特点是FILO，先进后出，底层结构也是动态数组

### 3. Queue ###

#### 队列，Queue接口，常用实现原理及特点 ####

1.  LinkedBlockingQueue：链表阻塞队列，队列的最大特点是FIFO，先进先出
2.  ArrayBlockingQueue：数组阻塞队列

### 4. Set ###

#### 集合，Set接口，常用实现原理及特点 ####

1.  HashSet：底层实现是一个Hash表，其实就是一个特殊的HashMap，key就是add的元素，value是一个固定的静态对象Object。无序，不重复
2.  TreeSet：树结构的Map

> 不重复如何保证？新增一个元素与每个元素进行equals比较？性能会很差，使用hash值作为index下标存储数据，如果hash值下标对应的数据为空则不存在相同元素，如果hash值下标处存在数据即hash值相同再校验equals是否是同一个元素，因为存在hash冲突情况

### 5. Map ###

#### 字典，Map接口，常用实现原理及特点 ####

1.  HashMap：底层实现是hash表，一个单向链表类型的数组，根据key的hashcode计算出hash值作为下标放入数组；在hash值出现冲突时校验链表中key是否已经存在（通过key的equals方法判断是否相同），不存在则新建next节点，冲突数量超过阈值时会将单向链表转换为红黑树存储，减少大量hash冲突带来的性能损耗。特点无序、不重复、线程不安全
2.  ConcurrentHashMap：特点在于使用cas算法与volatile特性优化集合的并发
3.  HashTable：线程安全

#### 思考hashcode与equals的关系 ####

##### 设计原则是hashcode相等，equals一定要相等 #####

1.  如果hashcode相等，equals不相等，会有什么问题呢？
2.  前面我们讲到HashMap的实现中，put元素时，会根据key的hashcode计算hash值来决定key的下标位置，如果hashcode相等，出现hash冲突时，会根据key的equals方法判断key是否已经存在。所以会出现下面这些问题
3.  如果hashcode相等，equals不相等；则可能出现，相同的两个元素被重复存储，出现资源的浪费，因为hash值相同被分配至同一个下标，再根据key的equals方法判断是否已存在，若不相等则新建node节点，出现资源浪费

import java.util.HashMap;
    
    /**
     * @author 会灰翔的灰机
     * @date 2019/2/18
     */
    public class MyKey {
    
        private Integer key;
    
        public MyKey(Integer key) {
            this.key = key;
        }
    
        @Override
        public int hashCode() {
            return 1;
        }
    
        @Override
        public boolean equals(Object obj) {
            return false;
        }
    
        @Override
        public String toString() {
            return key+"";
        }
    
        public static void main(String[] args) {
            HashMap<MyKey, Integer> map = new HashMap<>(10);
    //        两个key都是1，相同的key，最终存储了两份数据
            MyKey myKey = new MyKey(1);
            MyKey myKey1 = new MyKey(1);
            map.put(myKey, 10);
            map.put(myKey1, 11);
            System.out.println(map);
        }
    }

![image.png][]

1.  如果hashcode不相等，equals相等；则可能出现，不相同的第二个元素存储失败或者覆盖原有元素，因为hash冲突时在根据key的equals判断时发现元素已经存在了，则存储失败或者覆盖原有元素

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/3edb7702c25847dcb3b3f38206e5d396.png