Java集合框架：List、Set、Map 以及源码解析

Java集合

List、Set、Map都是接口，List和Set类继承Collection接口，Map为独立接口
Iterable

List、Set、Map三者区别

  • List：存储元素有序、可重复
    • ArrayList(Object[]数组)
      • 优点：底层数据结构是数组，查询快，增删慢
      • 缺点：线程不安全，效率低
    • Vector(Object[]数组)
      • 优点：底层数据结构是数组，查询快，增删慢
      • 缺点：线程安全，效率低
    • LinkedList(双向链表，JDK1.6之前是循环链表，JDK1.7取消了循环)
      • 优点：底层数据结构是链表，查询慢，增删快
      • 缺点：线程不安全，效率高
  • Set：无序、不可重复
    • HashSet(基于HashMap实现)
      • 底层数据结构是哈希表。(无序唯一)
      • 保证元素唯一性(hashCode()、equals())
      • 线程不安全，可以存储null值
    • LinkedHashSet(基于LinkedHashMap实现)
      • 底层数据结构是链表和哈希表。(FIFO插入有序，唯一)
      • 链表保证元素有序
      • 哈希表保证元素唯一
      • 能够按照添加的顺序遍历
    • TreeSet(红黑树，自平衡排序二叉树)
      • 底层数据结构是红黑树 (唯一，有序)
      • 元素排序：自然排序，比较器排序
      • 元素唯一性：根据比较的返回值是否为0来决定
      • 能够按照添加元素的顺序进行遍历，排序的方式有自然排序和定制排序
  • Map：使用key-value存储。key无序、不可重复；value无序、可重复。一一对应
    • HashMap：JDK1.8之前由数组+链表组成，数组是主体，链表是为解决哈希冲突；JDK1.8之后，在解决哈希冲突时，如果链表长度大于阈值(默认为8)(将链表转换成红黑树前会判断，如果当前数组长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树)时，将链表转换为红黑树，以减少搜索时间
    • LinkedHashMap：LinkedHashMap继承自HashMap，底层仍然基于数组和链表或红黑树组成，增加了一条双向链表，保持键值对的插入顺序。
    • Hashtable：数组+链表组成，数组是Hashtable的主体，链表则是为了解决哈希冲突而存在的
    • TreeMap：红黑树(自平衡的排序二叉树)

List

ArrayList

ArrayList的底层是数组队列，相当于动态数组。与Java中的数组相比，它的容量可以动态增长。通过ensureCapacity来增加ArrayList实例的容量，可以减少递增式再分配的数量

ArrayList继承于AbstractList，实现了List、RandomAcess、Cloneable、java.io.Serializable这些接口

public class ArrayList<E> extends AbstractList<E> implements List<E>,RandomAcess,Cloneable,java.io.Serializable{
}
  • RandomAcess：表明List集合是支持快速随机访问的。在ArrayList中，即可以通过元素的序号快速获取元素对象。
  • Cloneable：覆盖clone()，能被复制
  • java.io.Serializable：支持序列化，能通过序列化去传输

ArrayList源码解析

详见ArrayList源码

LinkedList源码解析

详见LinkedList源码

HashMap源码分析

详见HashMap源码

ConcurrentHashMap源码分析

详见ConcurrentHashMap

ArrayList 和 Vector 区别

  1. ArrayList 是 List的主要实现类，底层使用 Object[]存储，适用频繁的查找工作，线程不安全,用Collections.synchronizedList包装ArrayList成一个线程安全的数组容器，原理和Vector一样
  2. Vector 是 List的古老实现类，底层使用 Object[]存储。线程安全，对所有方法都加上synchronized

    ArrayList 和 LinkedList 区别

  3. 是否保证线程安全：都是不同步的，都不保证线程安全
  4. 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用 双向链表数据结构(JDK1.6之前为循环链表，JDK1.7取消循环)
  5. 插入和删除是否受元素位置的影响：
    • ArrayList采用数组存储，插入和删除元素的时间复杂度受元素位置影响。add(E e)时，ArrayList 会默认将元素追加到列表的末尾，时间复杂度为O(1).但如果在指定位置插入和删除的话add(int index,E element)时间复杂度为O(n-i).第i位之后的元素都要向后/向前移一位。
    • LinkedList采用链表存储，对于add(E e)插入，删除元素时间复杂度不受元素位置影响，近似O(1)。如果在指定位置插入和删除元素(add(int index,E element))时间复杂度近似为O(n)，需要先移动到指定位置再插入
  6. 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问是通过元素的序号快速获取元素对象
  7. 内存空间占用：ArrayList的空间浪费主要体现在list列表的结尾会预留一定容量空间。LinkedList的空间花费则体现在每一个元素都需要消耗比ArrayList更多的空间。(需要存放直接后继和直接前驱以及数据)

双向链表和双向循环链表

双向链表：包含两个指针，一个prev指向前一个节点，一个next指向后一个节点

双向循环链表：最后一个节点的next指向head,head的prev指向最后一个节点，构成一个环

Set

comparable 和 Comparator的区别

  • comparable 接口实际上是出自java.lang包，它有一个compareTo(Object obj)方法用来排序
  • Comparator 接口实际上是出自java.util包，它有一个compare(Object obj1,Object obj2)方法用来排序

一般对集合使用自定义排序时，就要重写compareTo()方法或compare()方法。

Comparator 定制排序

public static void main(String[]args){
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(-1);
    arrayList.add(3);
    arrayList.add(3);
    arrayList.add(-5);
    arrayList.add(7);
    arrayList.add(4);
    arrayList.add(-9);
    arrayList.add(-7);
    System.out.println("原始数组");
    System.out.println(arrayList); // [-1,3,3,-5,7,4,-9,-7]

    // 反转
    Collections.reverse(arrayList);
    System.out.println("Collections.reverse 反转数组");
    System.out.println(arrayList); // [-7,-9,4,7,-5,3,3,-1]

    // 升序排序
    Collections.sort(arrayList);
    System.out.println("Collections.sort  升序");
    System.out.println(arrayList); // [-9, -7, -5, -1, 3, 3, 4, 7]

    // 定制排序
    Collections.sort(arrayList, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    System.out.println("定制排序后");
    System.out.println(arrayList); // [7, 4, 3, 3, -1, -5, -7, -9]
}

重写compareTo方法实现按年龄排序

// person对象没有实现Comparable接口，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口，详细可以查看String类的API文档，另外其他
// 像Integer类等都已经实现了Comparable接口，所以不需要另外实现了
public  class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}

测试

public static void main(String[] args) {
    TreeMap<Person, String> pdata = new TreeMap<Person, String>();
    pdata.put(new Person("张三", 30), "zhangsan");
    pdata.put(new Person("李四", 20), "lisi");
    pdata.put(new Person("王五", 10), "wangwu");
    pdata.put(new Person("小红", 5), "xiaohong");
    // 得到key的值的同时得到key所对应的值
    Set<Person> keys = pdata.keySet();
    for (Person key : keys) {
        System.out.println(key.getAge() + "-" + key.getName()); //5-小红   10-王五   20-李四   30-张三
    }
}

无序性和不可重复性

  • 无序性：不等于随机性。无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的
  • 不可重复性：

Map

HashMap 和 Hashtable 的区别

  • 线程是否安全：HashMap是非线程安全的，Hashtable是线程安全的，因为Hashtable内部方法都基本经过synchronized修饰。如果要保证线程安全使用ConcurrentHashMap
  • 效率：因为线程安全问题，HashMap要比Hashtable效率高一点。Hashtable基本被淘汰，不要在代码中使用它
  • 对Null key 和 Null value的支持：HashMap可以存储null的key和value，但null作为键只能有一个，null作为值可以有多个。Hashtable不允许有null键和null值,否则抛出异常
  • 初始容量大小和每次扩充容量大小的不同：
    • 创建时如果不指定容量初始值，HashMap默认初始化大小为16.之后每次扩充，容量变为原来的2倍；Hashtable默认初始大小为11，之后每次扩充，容量变为原来的2n+1.
    • 创建时如果给定了容量初始值，那么Hashtable会直接使用给定大小；HashMap会将其扩充为2的幂次方。
  • 底层数据结构：JDK1.8之后HashMap在解决哈希冲突时有了较大变化，当链表长度大于阈值(默认为8)(将链表转换为红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树)时，将链表转化为红黑树，以减少搜索时间。Hashtable没有这样的机制

HashMap 和 HashSet 区别

  • HashMap
    • 实现了Map接口
    • 存储键值对
    • 调用put()向map中添加元素
    • HashMap使用键(key)计算hashCode
  • HashSet
    • 实现set接口
    • 存储对象
    • 调用add()方法向Set中添加元素
    • HashSet使用成员对象来计算hashcode,对于两个对象来说，hashcode可能相同，所以equals()方法用来判断对象的相等性

HashMap 和 TreeMap 区别

TreeMap 和 HashMap都继承 AbstractMap，但需要注意的是 TreeMap还实现了 NavigableMap接口和 SortedMap接口
TreeMap继承结构

实现NavigableMap接口，让TreeMap有了对集合内元素的搜索的能力

实现SortedMap接口，让TreeMap有了对集合元素根据键排序的能力，默认是按key的升序排序。也可以指定自定义排序器排序

public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        //        TreeMap<TreemapTest,String> treeMap = new TreeMap(new Comparator<TreemapTest>() {
//            @Override
//            public int compare(TreemapTest o1, TreemapTest o2) {
//                int num = o1.getAge() - o2.getAge();
//                return Integer.compare(num,0);
//            }
//        });
        //将代码替换成 Lambda 表达式实现的方式：
        TreeMap<TreemapTest,String> treeMap = new TreeMap<>((o1,o2) -> {
            int num = o1.getAge() - o2.getAge();
            return Integer.compare(num, 0);
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());   //person1 person4 person2 person3
        });
    }
}

HashSet如何检查重复

  1. 当你把对象加入HashSet时，HashSet会先计算对象的hashCode值来判断对象加入的位置
  2. 并且和其他加入对象的hashCode值做比较，如果没有相符的hashCode，直接插入
  3. 如果发现有相同的hashcode值的对象，调用equals()方法检查hashcode值相等的对象是否相同，如果相同，HashSet就不会加入

**hashCode() 与 equals()**：

  1. 如果两个对象相等，则hashCode一定相同
  2. 如果两个对象相等，对两个equals()返回true
  3. 如果两个对象有相同的hashCode值，它们不一定是相等的
  4. equals()方法被覆盖过，则hashCode()方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等。(即使两个对象指向相同的数据)

== 和 equals() 区别

  • 对于基本类型来说， == 比较的是值是否相等
  • 对于引用类型来说，==比较的是两个引用是否指向同一个对象地址。两者在内存中存放的地址(堆内地址)是否指向同一个地方
  • 对于引用类型(包括包装类型)来说，equals如果没有被重写，对比它们的地址是否相等；如果equals()方法被重写(例如String),比较的是地址里的内容

HashMap 多线程操作导致死循环问题

jdk1.7版本主要原因在于并发下的Rehash会造成元素之间形成一个循环链表。jdk1.8版本解决了这个问题，但在多线程下使用HashMap会存在数据丢失等问题。并发下推荐使用ConcurrentHashMap.

ConcurrentHashMap 和 Hashtable的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同

  • 底层数组结构：JDK1.7的ConcurrentHashMap底层采用分段的数组Segment+链表实现,JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑树；Hashtable和JDK1.8之前的HashMap一样采用 数组+链表的形式，数组是Hashtable的主体，链表则是为了解决哈希冲突
  • 实现线程安全的方法：
    • 在JDK1.7，ConcurrentHashMap(分段锁)对整个桶数组进行分割分段(Segment),每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了JDK1.8时，摒弃Segment的概念，直接使用Node数组+链表+红黑树的数据结构，并发控制使用synchronized和CAS来操作。
    • Hashtable(同一把锁)：使用synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能进入阻塞或轮询状态，如使用put添加元素，另一个线程不能使用put添加元素，也不能使用get，竞争会越来越激烈，效率越低

Hashtable
HashTable全表锁.png

JDK1.7的ConcurrentHashMap
ConcurrentHashMap分段锁.jpg

JDK1.8的ConcurrentHashMap
java8_concurrenthashmap.png

Collections 工具类

Collections工具类常用方法：

  1. 排序
  2. 查找，替换操作
  3. 同步控制(不推荐，需要线程安全的集合类型时，请考虑使用JUC包下的并发集合)

排序

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面

查找，替换操作

int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

同步控制

Collections提供了多个synchronizedXxx()方法，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题

HashSet,TreeSet,ArrayList,LinkedList,HashMap,TreeMap都是线程不安全的。Collections提供了多个静态方法可以把它们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

synchronizedCollection(Collection<T> c) //返回指定 collection支持的同步（线程安全的）collection
synchronizedList(List<T> list) //返回指定列表支持的同步（线程安全的）List
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

参考