深入Java集合Collection

分手后的思念是犯贱 2022-04-22 15:56 309阅读 0赞

# 1. Java集合框架图 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70][]

**更详细版**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 1][]

**Java集合主要有3种重要的类型**：

**List：**是一个有序集合，可以放重复的数据

*  ArrayList：基于可变数组
 *  LinkedList：基于链表数据结构

**Set：**是一个无序集合，不允许放重复的数据

*  HashSet：无序的不可重复的
 *  TreeSet：可以对Set集合进行排序，默认自然排序（即升序）
 *  LinkedHashSet：基于哈希表和链接列表

**Map：**是一个无序集合，集合中包含一个键对象，一个值对象，键对象不允许重复，值对象可以重复（身份证号—姓名）

*  HashMap：
 *  HashTable：
 *  TreeMap：
 *  LinkedHashMap：

# 2 List #

## 2.1 ArrayList ##

![20190114145623415.png][]

### 2.1.1 set ###

/**
         * Replaces the element at the specified position in this list with
         * the specified element.
         * 用指定的元素替代此列表中指定位置上的元素
         */
        public E set(int index, E element) {
            Objects.checkIndex(index, size);//检查index是否合法
            E oldValue = elementData(index);
            elementData[index] = element;//赋值
            return oldValue;
        }

### 2.1.2 add ###

//将指定的元素添加到列表的尾部
    public boolean add(E e){
        ensureCapacity(size+1);确保容量满足
        elementData[size++] = e;
        return true;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 2][]

![20190114175532692.png][]

元素往后移动会出现要扩容的情况

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 3][]

### 2.1.3 remove ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 4][]

## 2.2 LinkedList ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 5][]

### 2.2.1 数据结构 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 6][]

### 2.2.2 根据序号获取Entry对象 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 7][]

### 2.2.3 添加元素 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 9][]

### 2.2.4 删除元素 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 10][]

![2019011511122282.png][]

# 3 Map #

## 3.1 HashMap ##

## ![20190115112734707.png][] ##

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 11][] ##

数组+链表

**hash(key), key, value**

### 3.1.1 数据结构 ###

先初始化数组Node\[\] table

Node是数组中的元素

transient Node<K,V>[] table;     //第一级的数组
    
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
          .......
        }

### 3.1.2 put（修改key对应的value值） ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 12][]

**hash函数**

![20190115143205297.png][]

![20190115143319720.png][]

### 3.1.3 addEntry（插入链表里） ###

![20190115143810462.png][]

HashMap底层数组的长度总是2的N次方，为了减少碰撞现象，元素越来越多时，需要对数组进行扩容，容量变为原来的两倍。

### 3.1.4 get ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 13][]

根据找到对应的HashMap中数组的下标，根据下标得到一个链表，再去匹配链表中的key，然后得到value

## 3.2 HashTable ##

![20190115140436954.png][]

public synchronized V get(Object key) {
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
                if ((e.hash == hash) && e.key.equals(key)) {
                    return (V)e.value;
                }
            }
            return null;
        }
    
    public synchronized V put(K key, V value) {
            // Make sure the value is not null
            if (value == null) {
                throw new NullPointerException();
            }
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
            addEntry(hash, key, value, index);
            return null;
        }

## 3.3 TreeMap ##

### ![20190115150545510.png][] ###

### 3.3.1 数据结构 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 14][]

基于[红黑树][Link 1]

红黑树是自平衡二叉查找树，在进行插入和删除操作时，通过特定的操作，能保持二叉查找树的平衡，从而获得较高的查找性能。

![20190115151517100.png][]

static final class Entry<K,V> implements Map.Entry<K,V> {
            K key;
            V value;
            Entry<K,V> left;
            Entry<K,V> right;
            Entry<K,V> parent;
            boolean color = BLACK;
            ......
    }

### 3.3.2 TreeMap的优势 ###

![20190115151757371.png][]

## 3.4 LinkedHashMap ##

![20190115152426739.png][]

HashMap：第一级结构是一个数组，第二级结构是一个单向链表

LinkedHashMap：第一级结构是一个数组，第二级结构是一个双向链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 15][]

[Map 综述（二）：彻头彻尾理解 LinkedHashMap][Map _ LinkedHashMap]

public V get(Object key) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }

## 3.5 ConcurrentHashMap ##

##  ##

## 3.6 Map的适用范围 ##

![20190115154718169.png][]

# 4 Set #

## 4.1 HashSet ##

![20190115155205250.png][]

//底层使用HashMap来保存HashSet中所有元素
     private transient HashMap<E,Object> map;
    
    //定义一个虚拟的Object对象作为HashMap的value
     private static final Object PRESENT = new Object();
    
    //借助HashMap的put方法来添加
     public boolean add(E e) {
       return map.put(e, PRESENT)==null;
     }
    //借助HashMap的方法来查找
     public boolean contains(Object o) {
       return map.containsKey(o);
     }

![20190115160714527.png][]

好累，喝一杯香芋波波补补元气。

![20190115161133118.png][]

--------------------

**本文学习自**

[学堂在线-清华大学-许斌《JAVA程序设计进阶》][-_-_JAVA]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70]: /images/20220327/bb2ab16655324362921a405d97bc5814.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 1]: /images/20220327/37554b0a4e3e4f4b86bdbe39e8d2335b.png
[20190114145623415.png]: /images/20220327/f3d8c392bc30433488fc6306813065a3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 2]: /images/20220327/c265e4d225584075b7180e79dcbd5b20.png
[20190114175532692.png]: /images/20220327/549f9db5e9d84b509fc29769ef07ca3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 3]: /images/20220327/77bb8485600145c689d14b70cdcdb827.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 4]: /images/20220327/61ad262a39924ce6ab2202bf2c8a741d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 5]: /images/20220327/5d05d08f3a85446a9db736f2b98c30bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 6]: /images/20220327/108bd3bce4db42468a5a4aacb306e57d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 7]: /images/20220327/aa590ac0e71e41129fb418d4230a9ec4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 8]: /images/20220327/a524a10639604f58b5825ed44c6f3719.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 9]: /images/20220327/ff5599130f27467897edcb4165c37cf4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 10]: /images/20220327/13536525a5604a45aa473178c7f7235b.png
[2019011511122282.png]: /images/20220327/12ea77e2c8ad4942b94533c108b3e6e0.png
[20190115112734707.png]: /images/20220327/babfc7e2d6d74b83a64b5b3447bc3754.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 11]: /images/20220327/9bb0af22bc4c429da633a477962070c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 12]: /images/20220327/83e4462fd84a4cc9a57af843012a6974.png
[20190115143205297.png]: /images/20220327/bee5ad0e5acb4c619472170bf93e23a3.png
[20190115143319720.png]: /images/20220327/df245294cd1a46a9979906e3bd4f0e52.png
[20190115143810462.png]: /images/20220327/c6b43744112b4c03964c4a54eb85ef76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 13]: /images/20220327/a20dec62edf74b3389d9ec986c204f98.png
[20190115140436954.png]: /images/20220327/36e241b376834b22a35c3c659f659ef6.png
[20190115150545510.png]: /images/20220327/6f0bc8af12e040d5838f087ae0b67391.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 14]: /images/20220327/4329c86eee43403cbfcc5fd0226f9ded.png
[Link 1]: https://blog.csdn.net/wydyd110/article/details/82012960#5%C2%A0%20%E7%BA%A2%E9%BB%91%E6%A0%91
[20190115151517100.png]: /images/20220327/d48abe8e2d294257aae75dbb7a16c688.png
[20190115151757371.png]: /images/20220327/229c23c2e12846a38808fd19373b5a3f.png
[20190115152426739.png]: /images/20220327/2a2d37d33a0f4af88c7d984ef3dc86fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 15]: /images/20220327/c4f698a93967419bb86b4746baf3560b.png
[Map _ LinkedHashMap]: https://blog.csdn.net/justloveyou_/article/details/71713781
[20190115154718169.png]: /images/20220327/565cb57409d64517a66fc321f26ff8a6.png
[20190115155205250.png]: /images/20220327/ac6bb7343d6e4f09b91501c0dbee07ab.png
[20190115160714527.png]: /images/20220327/90e1cc50ac7c41168a5294999b330b7f.png
[20190115161133118.png]: /images/20220327/1ea03812982a4ac094778f469d2a022d.png
[-_-_JAVA]: http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240332+sp/courseware/5c85e04e82ca4af3aff9bd73f43e62f9/