Java 数据结构与集合

淩亂°似流年 2022-04-16 02:52 251阅读 0赞

# 1. 集合图谱 #

Java 集合图谱：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAzNzY3ODg_size_16_color_FFFFFF_t_70]

## 1.1 List 集合 ##

List 集合是线性数据结构的主要实现，List 集合的遍历结果是稳定的。该体系最常用的是 ***ArrayList*** 和 ***LinkedList***。

**ArrayList** 是容量可以改变的非线程安全集合。内部实现使用数组进行存储，集合扩容时会创建更大的数组空间，把原有数据复制到新数组中。**ArrayList** 支持对元素的快速随机访问，但是插入与删除时速度通常很慢。

**LinkedList** 的本质是双向链表。与 **ArrayList** 相比，**LinkedList** 的插入和删除速度更快，但是随机访问速度则很慢。除了继承 **AbstractList** 抽象类外，**LinkedList** 还实现了另一个接口 **Deque**，即 **double-ended queue**，这个接口同时具有队列和栈的性质。**LinkedList** 的优点在于可以将零散的内存单元通过附加引用的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高。

## 1.2 Queue 集合 ##

Queue（队列）是一种先进先出的数据结构，队列是一种特殊的线性表，它只允许在表的一端进行获取操作，在表的另一端进行插入操作。自从 **BlockingQueue**（阻塞队列）问世以来，在各种高并发编程场景中，由于其本身 FIFO 的特性和阻塞操作的特点，经常被作为 Buffer（数据缓冲区）使用。

## 1.3 Map 集合 ##

Map 集合是以 Key-Value 键值对作为存储元素实现的哈希结构，Key 按某种哈希函数计算后是唯一的，Value 则是可以重复的。Map 类提供三种 Collection 视图，Map 和 Collection 之间有种依赖关系。可以使用 **keySet()** 查看所有的 Key，使用 **value()** 查看所有的 Value，使用 **entrySet()** 查看所有的键值对。在多线程并发场景中，优先推荐使用 **ConcurrentHashMap**，而不是 **HashMap**。**TreeM** 是 Key 有序的 Map 类集合。

## 1.4 Set 集合 ##

Set 是不允许出现重复元素的集合类型。Set 体系最常用的是 HashSet、TreeSet 和 LinkedHashSet 三个集合类。

*  **HashSet** 从源码分析是使用 **HashMap** 来实现的，只是 Value 固定为一个静态对象，使用 Key 保证集合元素的唯一性，但它不保证集合元素的顺序。
 *  **TreeSet** 从源码分析是使用 **TreeMap** 来实现的，底层为树结构，在添加新元素到集合中时，按照某种比较规则将其插入合适的位置，保证插入后的集合仍然是有序的。
 *  **LinkedHashSet** 继承自 **HashSet**，具有 **HashSet** 的优点，内部使用链表维护了元素插入顺序。

# 2. 集合初始化 #

**ArrayList** 使用无参构造时，默认大小是 10，后续的每次扩容都会调用 ***Arrays.copyOf()*** 方法，创建新数组再复制。

**HashMap** 容量并不会在 new 的时候分配，而是在第一次 put 的时候完成创建的。

集合初始化时，指定集合初始值大小。如果暂时无法确定集合大小，那么指定相应的默认值，这要求我们记得各种集合默认值大小，**ArrayList** 默认大小为 10，**HashMap** 默认大小为 16。

# 3. 数组与集合 #

## 数组转集合 ##

以 ***Arrays.asList()*** 为例，它把数组转换成集合时，不能使用其修改集合相关的方法，它的 add、remove、clear 方法会抛出 UnsupportedOperationException 异常。

public void array2List() {
        String[] strArray = new String[3];
        strArray[0] = "one";
        strArray[1] = "two";
        strArray[2] = "three";
    
        List<String> strList = Arrays.asList(strArray);
    
        // 修改转换后的集合元素
        strList.set(1, "TWO");
        System.out.println(strList);
    
        // 抛出UnsupportedOperationException异常
        strList.add("four");
        strList.remove(2);
        strList.clear();
    }

事实证明，可以通过 ***set()*** 方法修改元素的值，原有数组相应位置的值同时也会被修改，但是不能进行修改元素个数的任何操作，否则会抛出 UnsupportedOperationException 异常。***Arrays.asList()*** 体现的是适配器模式，后台的数据仍是原有数组，***set()*** 方法即间接对数组进行值的修改操作。***asList()*** 的返回对象是一个 ***Arrays*** 的内部类，它并没有实现集合个数的相关修改方法，这也正是抛出异常的原因。

虽然 ***Arrays*** 与 ***ArrayList*** 同属于一个包，但是在 ***Arrays*** 类中还定义了一个 ***ArrayList*** 的内部类（或许命名为 InnerArrayList 更容易识别），根据作用域就近原则，此处的 ***ArrayList*** 就是 ***Arrays*** 的内部类 ***ArrayList***。

在使用数组转集合时，需要使用 ***java.util.ArrayList*** 直接创建一个新集合，参数就是 ***Arrays.asList()*** 返回的不可变集合，如下：

List<Object> newList = new java.util.ArrayList<>(Arrays.asList(数组参数));

## 集合转数组 ##

集合转数组时，不要使用 ***toArray()*** 无参方法把集合转换成数组，这样会导致泛型丢失。使用集合的 ***toArray(T\[\] array)*** 方法，转换为数组时，注意需要传入类型完全一样的数组，并且它的容量大小为 **list.size()**，如下：

String[] newArray = list.toArray(new String[list.size()]);

# 4. 集合与泛型 #

***List<?>*** 是一个泛型，在没有赋值之前，表示它可以接受任何类型的集合赋值，赋值之后就不能随便再添加任何元素了。

public void collectionGeneric() {
        List l1 = new ArrayList();
        l1.add(new Object());
        l1.add(new Integer(1));
        l1.add("hello");
        System.out.println("List: " + l1);
    
        List<Object> l2 = l1;
        l2.add(new Object());
        l2.add(new Integer(2));
        l2.add(new String("world"));
        System.out.println("List<Object>: " + l2);
    
        List<Integer> l3 = l1;
        l3.add(new Integer(3));
    //  l3.add(new Object());
        System.out.println("List<Integer>: " + l3);
    
        List<?> l4 = l1;
        l1.remove(0);
        l4.clear();
        // 编译出错，不允许添加任何元素
    //  l4.add(new Object());
        System.out.println("List<?>: " + l4);
    }
    
    输出：
    List: [java.lang.Object@2503dbd3, 1, hello]
    List<Object>: [java.lang.Object@2503dbd3, 1, hello, java.lang.Object@4b67cf4d, 2, world]
    List<Integer>: [java.lang.Object@2503dbd3, 1, hello, java.lang.Object@4b67cf4d, 2, world, 3]
    List<?>: []

问号在正则表达式中可以匹配任何字符，***List<?>*** 称为通配符集合。它可以接受任何类型的集合引用赋值，不能添加任何元素，但可以 remove 和 clear，并非 immutable 集合。***List<?>*** 一般作为参数来接收外部的集合，或者返回一个不知道具体元素类型的集合。

***List*** 最大的问题是只能放置一种类型，如果随意转换类型的话，就是“破窗理论”，泛型就失去了类型安全的意义。如果需要放置多种受泛型约束的类型，需要实现 ***<? extends T>*** 或 ***<? super T>\*\*\*。简单来说，\*\*\*<? extends T>*** 是 Get First，适用于消费集合元素为主的场景；\*\*\*<? super T>\*\*\* 是 Put First，适用于生产集合元素为主的场景。**extends** 的场景是 put 功能受限；而 **super** 的场景是 get 功能受限。

***<? extends T>*** 可以赋值给任何 T 及 T 子类的集合，上界为 T，取出来的类型带有泛型限制，向上强制转型为 T。**null** 可以表示任何类型，所以除 **null** 外，任何元素都不得添加进 ***<? extends T>*** 集合内。

***<? super T>*** 可以赋值给任何 T 及 T 的父类集合，下界为 T。

# 5. 元素的比较 #

## 5.1 Comparable 和 Comparator ##

Java 中两个对象相比较的方法通常是在元素排序中，常用的两个接口分别是 ***Comparable*** 和 ***Comparator***，前者是自己和自己比，可以看作是自营性质的比较强；后者是第三方比较器，可以看作是平台性质的比较强。***Comparable*** 表示它有自身具备某种能力的性质，表明 ***Comparable*** 对象本身是可以与同类型进行比较的，它的比较方法是 \*\*\*compareTo()\*\*\*；而 ***Comparator*** 表示自身是比较器的实现者，它的比较方法是 \*\*\*compare()\*\*\*。

在 SearchResult 类中自定义排序：

public class SearchResult implements Comparable<SearchResult> {
        private int relativeRatio;
        private long count;
        private int recentOrders;
    
        public SearchResult(int relativeRatio, long count) {
            this.relativeRatio = relativeRatio;
            this.count = count;
        }
    
        @Override
        public int compareTo(SearchResult o) {
            if (this.relativeRatio != o.relativeRatio){
                return this.relativeRatio > o.relativeRatio ? 1 : -1;
            }
            
            if (this.count != o.count){
                return this.count > o.count ? 1 : -1;
            }
            
            return 0;
        }
    }

在 SearchResult 类外定义排序：

public class SearchResultComparator implements Comparator<SearchResult> {
        @Override
        public int compare(SearchResult o1, SearchResult o2) {
            if (o1.getRelativeRatio() != o2.getRelativeRatio()){
                return o1.getRelativeRatio() > o2.getRelativeRatio() ? 1 : -1;
            }
            
            if (o1.getCount() != o2.getCount()){
                return o1.getCount() > o2.getCount() ? 1 : -1;
            }
            
            return 0;
        }
    }

不管是 ***Comparable*** 还是 ***Comparator***，小于的情况返回值是负值，等于的情况返回值是 0，大于的情况返回值是正值。

Java 在 JDK7 中使用 TimeSort 算取代了原来的归并排序。它由两个主要优化：

1.  归并排序的分段不再从单个元素开始，而是每次先查找当前最大的排序好的数组片段，然后对该数组片段进行扩展并利用二分排序，之后将该数组片段与其他已经排序好的数组片段进行归并，产生排序好的更大的数组片段。
2.  引入二分排序，即 binarySort。二分排序是对插入排序的优化，在插入排序中不再是从后向前逐个元素对比，而是引入二分查找的思想，将一次查找新元素合适位置的时间复杂度由 O(n) 降低到 O(logn)。

## 5.2 hashCode 和 equals ##

对象通过调用 ***Object.hashCode()*** 生成哈希值；由于不可避免地会存在哈希值冲突的情况，因此当 hashCode 相同时，还需要调用 equals 进行一次值的比较；但是，若 hashCode 不同，将直接判定 Object 不同，跳过 equals，这加快了冲突处理效率。Object 类定义中对 hashCode 和 equals 的要求如下：

1.  如果两个对象的 equals 的结果是相等的，则两个对象的 hashCode 的返回结果也必须是相同的。
2.  任何时候覆写 equals，都必须同时覆写 hashCode。

# 6. fail-fast 机制 #

**fail-fast 机制**，是一种对集合遍历操作时的错误检测机制，在遍历中途出现意料之外的修改时，通过 unchecked 异常暴力的反馈出来。java.util 下的所有集合类都是 **fail-fast**，而 java.util.concurrent 包中的集合类都是 **fail-safe**。

public static void subListFailFast(){
        List masterList = new ArrayList();
        masterList.add("one");
        masterList.add("two");
        masterList.add("three");
        masterList.add("four");
        masterList.add("five");
    
        List branchList = masterList.subList(0, 3);
    
        // 如果不注释掉，会导致branchList操作抛出ConcurrentModificationException异常
    //    masterList.remove(0);
    //    masterList.add("ten");
    //    masterList.clear();
    
        branchList.clear();
        branchList.add("six");
        branchList.add("seven");
        branchList.remove(0);
    
        branchList.forEach(System.out::println);
    
        System.out.println(masterList);
    }

**fail-safe 机制**，是在安全的副本（或者没有修改操作的正本）上进行遍历，集合修改与副本的遍历是没有任何关系的，但是缺点也很明显，就是读取不到最新的数据。这也是 CAP 理论中，C（Consistency）和 A（Availability）的矛盾，即一致性与可用性的矛盾。

**COW（奶牛）家族，即 Copy-On-Write**。它是并发的一种新思路，实行读写分离，如果是写操作，则复制一个新集合，在新集合内添加或删除元素。待一切修改完成之后，再将原集合的引用指向新的集合。这样做的好处是可以高并发地对 COW 进行读和遍历操作，而不需要加锁，因为当前集合不会添加任何元素。使用 COW 时应注意两点：第一，尽量设置合理的容量初始值，它扩容的代价比较大；第二，使用批量添加或删除方法，如 addAll 或 removeAll 操作，在高并发请求下，可以攒一下要添加或者删除的元素，避免增加一个元素复制整个集合。COW 是 fail-safe 机制的。

# 7 Map 类集合 #

Map 类的特有方法，即返回所有的 Key，返回所有的 Value，返回所有的键值对。

// 返回所有的 Key
    Set<K> keySet();
    
    // 返回所有的 Value
    Collection<V> values();
    
    // 返回所有的键值对
    Set<Map.Entry<K, V>> entrySet();

通常这些返回的视图是支持清楚操作的，但是修改和增加元素会抛出异常，因为 **AbstractCollection** 没有实现 add 操作，但实现了 remove、clear 等相关操作。所以在使用这些视图返回集合时，注意不要操作此类相关方法。

<table> 
 <thead> 
  <tr> 
   <th>Map 集合类</th> 
   <th>Key</th> 
   <th>Value</th> 
   <th>Super</th> 
   <th>JDK</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HashTable</td> 
   <td>不允许为 null</td> 
   <td>不允许为 null</td> 
   <td>Dictionary</td> 
   <td>1.0</td> 
   <td>线程安全（过时）</td> 
  </tr> 
  <tr> 
   <td>ConcurrentHashMap</td> 
   <td>不允许为 null</td> 
   <td>不允许为 null</td> 
   <td>AbstractMap</td> 
   <td>1.5</td> 
   <td>锁分段技术或 CAS（JDK8 及以上）</td> 
  </tr> 
  <tr> 
   <td>TreeMap</td> 
   <td>不允许为 null</td> 
   <td>允许为 null</td> 
   <td>AbstractMap</td> 
   <td>1.2</td> 
   <td>线程不安全（有序）</td> 
  </tr> 
  <tr> 
   <td>HashMap</td> 
   <td>允许为 null</td> 
   <td>允许为 null</td> 
   <td>AbstractMap</td> 
   <td>1.2</td> 
   <td>线程不安全（resize 死链问题）</td> 
  </tr> 
 </tbody> 
</table>

参考文献

*  《码出高效》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAzNzY3ODg_size_16_color_FFFFFF_t_70]: /images/20220416/8e34375f70454960a7acb8c3e1b6519a.png