个人成长博客

纸上得来终觉浅，绝知此事要躬行

0%

Java集合框架

发表于 更新于 分类于

概述

集合可以看作是一种容器，用来存储对象信息。主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。其中List代表了有序可重复集合，可直接根据元素的索引来访问；Set代表无序不可重复集合，只能根据元素本身来访问；Queue是队列集合；Map代表的是存储key-value对的集合，可根据元素的key来访问value。所有集合类都位于java.util包下，但支持多线程的集合类位于java.util.concurrent包下。

集合框架

Java的集合类主要由两个接口派生而出：Collection和Map，Collection和Map是Java集合框架的根接口。Java 集合的总体框架图如下：

Collection接口

Collection接口是Set、Queue、List的父接口。Collection接口中定义了多种方法可供其子类进行实现，以实现数据操作。Collection中主要实现了，添加元素、删除元素，返回Collection集合的个数以及清空集合等基本方法。简化的关系图如下，图中ArrayList、HashSet、LinkedList、TreeSet是我们经常会有用到的已实现的集合类：

Set集合

Set集合与Collection集合基本相同，没有提供任何额外的方法。实际上Set就是Collection，只是行为略有不同（Set不允许包含重复元素）。Set集合不允许包含相同的元素，如果试图把两个相同的元素加入同一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被加入，允许null的存在但是仅有一个。

HashSet

HashSet是Set接口的典型实现，实现了Set接口中的所有方法，并没有添加额外的方法，大多数时候使用Set集合时就是使用这个实现类。HashSet按Hash算法来存储集合中的元素。因此具有很好的存取和查找性能。

HashSet特点
  1. 不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化
  2. HashSet不是同步的，如果多个线程同时访问一个HashSet，则必须通过代码来保证其同步，即HashSet是线程不安全的
  3. 集合元素值可以是null。
HashSet存储原理

当向HashSet集合存储一个元素时，HashSet会调用该对象的hashCode()方法得到其hashCode值，然后根据hashCode值决定该对象的存储位置。HashSet集合判断两个元素相等的标准是：

  1. 两个对象通过equals()方法比较返回true（equals方法主要给用户调用，主要判断两个对象是否相等）
  2. 两个对象的hashCode()方法返回值相等（hashCode默认返回对象在内存中地址转换成的一个int值，不考虑重写，任何对象hashCode方法都是不相等的）

因此，如果(1)和(2)有一个不满足条件，则认为这两个对象不相等，可以添加成功。

注意：如果两个对象的hashCode()方法返回值相等，但是两个对象通过equals()方法比较返回false，HashSet会以链式结构将两个对象保存在同一位置，HashSet是根据元素的hashCode值来快速定位的，将会导致性能下降。因此在编码时应避免出现这种情况，如果重写类的equals()方法和hashCode()方法时，应尽量保证两个对象通过hashCode()方法返回值相等时，通过equals()方法比较返回true。重写hashCode()方法的基本原则如下：

  • 在程序运行过程中，同一个对象的hashCode()方法返回值应相同
  • 当两个对象通过equals()方法比较返回true时，这两个对象的hashCode()方法返回值应该相等
  • 对象中用作equals()方法比较标准的实例变量，都应该用于计算hashCode值

LinkedHashSet

LinkedHashSet是HashSet的子类，也是根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，使得元素是以插入的顺序来保存的。当遍历LinkedHashSet集合里的元素时，LinkedHashSet将会按元素的添加顺序来访问集合里的元素。但是由于要维护元素的插入顺序，在性能上略低与HashSet，但在迭代访问Set里的全部元素时有很好的性能。
注意：LinkedHashSet依然不允许元素重复，判断重复标准与HashSet一致。

TreeSet

TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。

主要方法
1
2
3
4
5
6
7
8
comparator():返回对此 set 中的元素进行排序的比较器；如果此 set 使用其元素的自然顺序，则返回null。
first():返回此 set 中当前第一个（最低）元素。
last(): 返回此 set 中当前最后一个（最高）元素。
lower(E e):返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。
higher(E e):返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。
subSet(E fromElement, E toElement):返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。
headSet(E toElement):返回此 set 的部分视图，其元素小于toElement。
tailSet(E fromElement):返回此 set 的部分视图，其元素大于等于 fromElement。
排序方式

不同于之前所讲的插入顺序，TreeSet是通过集合中元素属性进行排序方式来实现的。它采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方法：自然排序和定制排序，默认采用自然排序。

自然排序

TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素的大小关系，然后将元素按照升序排列，这就是自然排序。如果试图将一个对象添加到TreeSet集合中，则该对象必须实现Comparable接口，否则会抛出异常。当一个对象调用方法与另一个对象比较时，例如obj1.compareTo(obj2)，如果该方法返回0，则两个对象相等；如果返回一个正数，则obj1大于obj2；如果返回一个负数，则obj1小于obj2。

Java常用类中已经实现了Comparable接口的类有以下几个：

  • BigDecimal、BigDecimal以及所有数值型对应的包装类：按照它们对应的数值大小进行比较
  • Charchter：按照字符的unicode值进行比较
  • Boolean：true对应的包装类实例大于false对应的包装类实例
  • String：按照字符串中的字符的unicode值进行比较
  • Date、Time：后面的时间、日期比前面的时间、日期大

注意：TreeSet中只能添加同一种类型的对象，否则无法比较，会出现异常。对于TreeSet集合而言，判断两个对象是否相等的唯一标准是：两个对象通过compareTo(Object obj)方法比较是否返回0——如果通过compareTo(Object obj)方法比较返回0，TreeSet则会认为它们相等，不予添加入集合内；否则就认为它们不相等，添加到集合内。

定制排序

而定制排序是通过Comparator接口的帮助。该接口包含一个int compare(T o1,T o2)方法，该方法用于比较o1,o2的大小：如果该方法返回正整数，则表明o1大于o2；如果该方法返回0，则表明o1等于o2;如果该方法返回负整数，则表明o1小于o2。 如果要实现定制排序，则需要在创建TreeSet时，调用一个带参构造器，传入Comparator对象。并有该Comparator对象负责集合元素的排序逻辑，集合元素可以不必实现Comparable接口。下面具体演示一下这种用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void main(String[] args){
        Person p1 = new Person();
        p1.age =20;
        Person p2 =new Person();
        p2.age = 30;
        Comparator<Person> comparator = new Comparator<Person>() {

            @Override
            public int compare(Person o1, Person o2) {
                //年龄越小的排在越后面
                if(o1.age<o2.age){
                    return 1;
                }else if(o1.age>o2.age){
                    return -1;
                }else{
                    return 0;
                }
                
            }
        };
        TreeSet<Person> set = new TreeSet<Person>(comparator);
        set.add(p1);
        set.add(p2);
        System.out.println(set);
    }

总结：无论使用自然排序还是定制排序，都可以通过自定义比较逻辑实现各种各样的排序方式。

注意：如果向TreeSet中添加了一个可变对象后，并且后面程序修改了该可变对象的实例变量，这将导致它与其他对象的大小顺序发生了改变，但TreeSet不会再次调整它们。建议不要修改放入TreeSet集合中元素的关键实例变量。TreeSet也是非线程安全的。

EnumSet

EnumSet是一个专为枚举类设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显示或隐式地指定。EnumSet的集合元素也是有序的，EnumSet以枚举值在EnumSet类内的定义顺序来决定集合元素的顺序。EnumSet 也是非线程安全的

EnumSet特点

  1. EnumSet集合不允许加入null元素。EnumSet中的所有元素都必须是指定枚举类型的枚举值
  2. EnumSet类没有暴露任何构造器来创建该类的实例，程序应该通过它提供的类方法来创建EnumSet对象

HashSet、TreeSet和EnumSet的性能对比

EnumSet内部以位向量的形式存储，结构紧凑、高效，且只存储枚举类的枚举值，所以最高效。HashSet以hash算法进行位置存储，特别适合用于添加、查询操作。LinkedHashSet由于要维护链表，性能比HashSet差点，但是有了链表，LinkedHashSet更适合于插入、删除以及遍历操作。而TreeSet需要额外的红黑树算法来维护集合的次序，性能最次。但是具体使用要考虑具体的使用场景：

  1. 当需要一个特定排序的集合时，使用TreeSet集合
  2. 当需要保存枚举类的枚举值时，使用EnumSet集合
  3. 当经常使用添加、查询操作时，使用HashSet
  4. 当经常插入排序或使用删除、插入及遍历操作时，使用LinkedHashSet

List集合

List集合代表一个有序、可重复集合，集合中每个元素都有其对应的顺序索引。List集合默认按照元素的添加顺序设置元素的索引，可以通过索引（类似数组的下标）来访问指定位置的集合元素。List判断两个对象相等，只要通过equals()方法比较返回true即可。

ArrayList和Vector

ArrayList和Vector作为List类的两个典型实现，完全支持之前介绍的List接口的全部功能。允许任何符合规则的元素插入甚至包括null。ArrayList和Vector类都是基于数组实现的List类，所以ArrayList和Vector类封装了一个动态的、允许再分配的Object[]数组。ArrayList或Vector对象使用initalCapacity参数来设置该数组的长度，当向ArrayList或Vector中添加元素超过了该数组的长度时，它们的initalCapacity会自动增加。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

ArrayList和Vector的区别：

  1. ArrayList是线程不安全的，Vector是线程安全的
  2. Vector的性能比ArrayList差

LinkedList

LinkedList是List接口的另一个实现，除了可以根据索引访问集合元素外，LinkedList还实现了Deque接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用。LinkedList的实现机制与ArrayList的实现机制完全不同，ArrayLiat内部以数组的形式保存集合的元素，所以随机访问集合元素有较好的性能；LinkedList内部以链表的形式保存集合中的元素，所以随机访问集合中的元素性能较差，但在插入删除元素时有较好的性能。

Stack

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

ArrayList与LinkedList性能对比

ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。ArrayList应使用随机访问(即，通过索引序号访问)遍历集合元素。LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。LinkedList应使用采用逐个遍历的方式遍历集合元素。
如果涉及到“动态数组”、“栈”、“队列”、“链表”等结构，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍：

  1. 对于需要快速插入，删除元素，应该使用LinkedList
  2. 对于需要快速随机访问元素，应该使用ArrayList
  3. 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)

Queue集合

Queue用于模拟队列这种数据结构，队列通常是指“先进先出”（FIFO）的容器。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。

PriorityQueue

PriorityQueue和TreeSet类似，保存队列元素的顺序不是按加入队列的顺序，而是按队列元素的大小进行重新排序。因此当调用peek()或pool()方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列中的最小的元素。

PriorityQueue的排序方式

PriorityQueue中的元素可以默认自然排序（也就是数字默认是小的在队列头，字符串则按字典序排列）或者通过提供的Comparator（比较器）在队列实例化时指定的排序方式。关于自然排序与Comparator（比较器）和上面所讲的TreeSet一致。

注意：队列的头是按指定排序方式的最小元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。当PriorityQueue中没有指定Comparator时，加入PriorityQueue的元素必须实现了Comparable接口（即元素是可比较的），否则会导致 ClassCastException。

下面具体写个例子来展示PriorityQueue中的排序方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
PriorityQueue<Integer> qi = new PriorityQueue<Integer>();
qi.add(5);
qi.add(2);
qi.add(1);
qi.add(10);
qi.add(3);
while (!qi.isEmpty()){
    System.out.print(qi.poll() + ",");
}
System.out.println();
//采用降序排列的方式，越小的越排在队尾
Comparator<Integer> cmp = new Comparator<Integer>() {
    public int compare(Integer e1, Integer e2) {
        return e2 - e1;
    }
};
PriorityQueue<Integer> q2 = new PriorityQueue<Integer>(5,cmp);
q2.add(2);
q2.add(8);
q2.add(9);
q2.add(1);
while (!q2.isEmpty()){
    System.out.print(q2.poll() + ",");
}

输出结果：

1
2
1,2,3,5,10,
9,8,2,1,
PriorityQueue的本质

PriorityQueue 本质也是一个动态数组。当添加元素到集合时，会先检查数组是否还有余量，有余量则把新元素加入集合，没余量则调用 grow()方法增加容量，然后调用siftUp将新加入的元素排序插入对应位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean offer(E e) {
      if (e == null)
          throw new NullPointerException();
      modCount++;
      int i = size;
      if (i >= queue.length)
          grow(i + 1);
      size = i + 1;
      if (i == 0)
          queue[0] = e;
      else
          siftUp(i, e);
      return true;
  }

除此之外，还要注意：

  1. PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表， 则这些线程不应同时访问 PriorityQueue 实例，这时请使用线程安全的PriorityBlockingQueue 类
  2. 不允许插入 null 元素
  3. PriorityQueue实现插入方法（offer、poll、remove() 和 add 方法） 的时间复杂度是O(log(n)) ；实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ；实现检索方法（peek、element 和 size）的时间复杂度是O(1)。所以在遍历时，若不需要删除元素，则以peek的方式遍历每个元素
  4. 方法iterator()中提供的迭代器并不保证以有序的方式遍历优PriorityQueue中的元素

Deque

Deque接口是Queue接口的子接口，它代表一个双端队列。LinkedList也实现了Deque接口，所以也可以被当作双端队列使用。

主要方法

Deque接口增加了一些关于双端队列操作的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void addFirst(E e):将指定元素插入此列表的开头。
void addLast(E e): 将指定元素添加到此列表的结尾。
E getFirst(E e): 返回此列表的第一个元素。
E getLast(E e): 返回此列表的最后一个元素。
boolean offerFirst(E e): 在此列表的开头插入指定的元素。
boolean offerLast(E e): 在此列表末尾插入指定的元素。
E peekFirst(E e): 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。
E peekLast(E e): 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。
E pollFirst(E e): 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。
E pollLast(E e): 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。
E removeFirst(E e): 移除并返回此列表的第一个元素。
boolean removeFirstOccurrence(Objcet o): 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
E removeLast(E e): 移除并返回此列表的最后一个元素。
boolean removeLastOccurrence(Objcet o): 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。

从上面方法中可以看出，Deque不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类里还包含了pop(出栈)、push(入栈)两个方法

Deque与Queue、Stack的关系

当 Deque 当做 Queue队列使用时（FIFO），添加元素是添加到队尾，删除时删除的是头部元素。从 Queue 接口继承的方法对应Deque 的方法如图所示：

Deque 也能当Stack栈用（LIFO）。这时入栈、出栈元素都是在 双端队列的头部 进行。Deque 中和Stack对应的方法如图所示：

注意：Stack过于古老，并且实现地非常不好，因此现在基本已经不用了，可以直接用Deque来代替Stack进行栈操作。

ArrayDeque

顾名思义，就是用数组实现的Deque。既然是底层是数组那肯定也可以指定其capacity，也可以不指定，默认长度是16，然后根据添加的元素的个数，动态扩展。ArrayDeque由于是两端队列，所以其顺序是按照元素插入数组中对应位置产生的。由于本身数据结构的限制，ArrayDeque没有像ArrayList中的trimToSize方法可以为自己瘦身。ArrayDeque的使用方法就是上面的Deque的使用方法，基本没有对Deque拓展什么方法。

ArrayDeque的本质

循环数组

ArrayDeque为了满足可以同时在数组两端插入或删除元素的需求，其内部的动态数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque维护了两个变量，表示ArrayDeque的头（head）和尾（tail）。

head当前对头第一个元素索引值，当向头部插入元素时，head下标减一然后插入元素。而 tail表示的索引为当前末尾元素表示的索引值加一。若当向尾部插入元素时，直接向tail表示的位置插入，然后tail再减一。

下面再说说扩容函数doubleCapacity()，其逻辑是申请一个更大的数组（原数组的两倍），然后将原数组复制过去。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n << 1;//原空间的2倍
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);//复制右半部分，对应上图中绿色部分
    System.arraycopy(elements, 0, a, r, p);//复制左半部分，对应上图中灰色部分
    elements = (E[])a;
    head = 0;
    tail = n;
}

过程如下图所示：

图中我们看到，复制分两次进行，第一次复制head右边的元素，第二次复制head左边的元素。

注意：ArrayDeque不是线程安全的。 当作为栈使用时，性能比Stack好；当作为队列使用时，性能比LinkedList好。

Map接口

Map用户保存具有映射关系的数据，因此Map集合里保存着两组数，一组值用户保存Map里的key，另一组值用户保存Map里的value，key和value都可以是任何引用类型的数据。Map的key值不允许重复。即同一个Map对象的任何两个key通过equals方法比较总是返回false。简化关系图如下：

HashMap与Hashtable

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。HashMap和Hashtable都是Map接口的经典实现类，它们之间的关系完全类似于之前介绍的ArrayList和Vector的关系。Hashtable是个古老的Map实现类，方法比较繁琐，不符合Map接口的规范。但是Hashtable也具有HashMap不具有的优点。下面我们进行两者之间的比对：

  1. Hashtable是一个线程安全的Map实现，涉及修改Hashtable的方法，使用了synchronized修饰，但HashMap是线程不安全的实现。Hashtable是串行化的方式运行，所以HashMap比Hashtable的性能好一些；但如果有多个线程访问同一个Map对象时，Hashtable实现类会更好
  2. Hashtable不允许使用null作为key和value，如果试图把null值放进Hashtable中，将会引发NullPointerException异常；但是HashMap可以使用null作为key或value

HashMap判断key与value相等的标准

key判断相等的标准：类似于HashSet，HashMap与Hashtable判断两个key相等的标准是：两个key通过equals()方法比较返回true,两个key的hashCode值也相等，则认为两个key是相等的。

value判断相等的标准：HashMap与Hashtable判断两个value相等的标准是：只要两个对象通过equals()方法比较返回true即可。

HashMap实现

数组+链表

Java8 以前HashMap的底层实现主要是通过数组+链表的实现拉链式的哈希表，如图：

一般情況是通过hash(key)获得，也就是元素的key的哈希值。如果hash(key)值相等，则都存入该hash值所对应的链表中。当HashMap的所有key都hash值都相同时，则会造成查找性能恶化，从O(1)变成O(n)，Java 8之后对HashMap做了优化。

数组+链表+红黑树

Java 8开始，HashMap采用数组+链表+红黑树来实现，以解决上述哈希表集中在一个链表中的所造成的性能问题，如图：

put方法

HashMap中put方法源码修改为如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果 table 还未被初始化，那么初始化它
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据键的 hash 值找到该键对应到数组中存储的索引
    //如果为 null，那么说明此索引位置并没有被占用
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //不为 null，说明此处已经被占用，只需要将构建一个节点插入到这个链表的尾部即可
    else {
        Node<K,V> e; K k;
        //当前结点和将要插入的结点的 hash 和 key 相同，说明这是一次修改操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果 p 这个头结点是红黑树结点的话，以红黑树的插入形式进行插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //遍历此条链表，将构建一个节点插入到该链表的尾部
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果插入后链表长度大于等于 8 ，将链表裂变成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                //遍历的过程中，如果发现与某个结点的 hash和key，这依然是一次修改操作 
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //e 不是 null，说明当前的 put 操作是一次修改操作并且e指向的就是需要被修改的结点
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果添加后，数组容量达到阈值，进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

归纳上面源码主要流程如下：

  1. 若HashMap未被初始化，则进行初始化操作
  2. 对Key求Hash值，依据Hash值计算下标
  3. 若未发生碰撞，则直接放入桶中
  4. 若发生碰撞，则以链表的方式链接到后面
  5. 若链表长度大于TREEIFY_THRESHOLD（默认8），并且hashmap容量大于MIN_TREEIFY_CAPACITY（默认64），则将链表转成红黑树
  6. 若节点已经存在，则用新值替换旧值
  7. 若桶满了（默认容量16*扩容因子0.75），就需要resize（扩容2倍后重排）
哈希算法
1
2
3
4
static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

首先计算得到hash值，根据hash值取模得到数组的下标。

get方法

HashMap中get方法的主要实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

主要就是根据哈希算法算出哈希值，然后计算下标，最后根据key在链表或者红黑树中查找相应的元素

扩容

HashMap触发扩容的主要时机：

  1. 当HashMap的使用的桶数达到总桶数*加载因子的时候会触发扩容
  2. 当某个桶中的链表长度达到8进行链表扭转为红黑树的时候，会检查总桶数是否小于64，如果总桶数小于64也会进行扩容
  3. 当new完HashMap之后，第一次往HashMap进行put操作的时候，首先会进行扩容

HashMap的扩容方法主要实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
1final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //拿到旧数组的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //说明旧数组已经被初始化完成了，此处需要给旧数组扩容
        if (oldCap > 0) {
            //极限的限定，达到容量限定的极限将不再扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //未达到极限，将数组容量扩大两倍，阈值也扩大两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; 
        }
        //数组未初始化，但阈值不为 0，为什么不为 0 ？
        //上述提到 jdk 大神偷懒的事情就指的这，构造函数根据传入的容量打造了一个合适的数组容量暂存在阈值中
        //这里直接使用
        else if (oldThr > 0) 
            newCap = oldThr;
        //数组未初始化并且阈值也为0，说明一切都以默认值进行构造
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        //根据新的容量初始化一个数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //旧数组不为 null，这次的 resize 是一次扩容行为
        if (oldTab != null) {
            //将旧数组中的每个节点位置相对静止地拷贝值新数组中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //获取头结点
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //说明链表或者红黑树只有一个头结点，转移至新表
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果 e 是红黑树结点，红黑树分裂，转移至新表
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //这部分是将链表中的各个节点原序地转移至新表中，我们后续会详细说明
                    else { 
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //不论你是扩容还是初始化，都可以返回 newTab
        return newTab;
}

介绍一下其中的重要的局部变量吧：

  • oldTab：为数组类型，代表扩容之前HashMap中的数组，也就是所有的桶；
  • oldCap：为int类型代表扩容之前总桶数量；
  • oldThr：为int类型代表扩容之前下次扩容的阈值；
  • newCap：为int类型代表这次扩容之后总桶数量；
  • newThr：为int类型代表这次扩容之后下次扩容的阈值；
  • newTab：为数组类型，代表扩容之后HashMap中的数组。

主要涉及的过程就是将oldTab转化为newTab，最复杂的就是rehashing的过程，扩容的时候容易有以下问题：

  1. 多线程环境下，调整大小存在条件竞争，容易造成死锁
  2. rehashing是一个比较耗时的过程

LinkedHashMap

LinkedHashMap使用双向链表来维护key-value对的次序（其实只需要考虑key的次序即可），该链表负责维护Map的迭代顺序，与插入顺序一致，因此性能比HashMap低，但在迭代访问Map里的全部元素时有较好的性能。

Properties

Properties类时Hashtable类的子类，它相当于一个key、value都是String类型的Map，主要用于读取配置文件。

TreeMap

TreeMap是SortedMap的实现类，是一个红黑树的数据结构，每个key-value对作为红黑树的一个节点。TreeMap存储key-value对时，需要根据key对节点进行排序。TreeMap也有两种排序方式：

  1. 自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则会抛出ClassCastException
  2. 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序

ConccurentHashMap

ConcurrentHashMap是一个经常被使用的数据结构，相比于Hashtable以及Collections.synchronizedMap()，ConcurrentHashMap在线程安全的基础上提供了更好的写并发能力，但同时降低了对读一致性的要求。ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。

早期版本

目前版本

ConccurentHashMap的put方法，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

简化流程为：

  • 根据 key 计算出 hashcode
  • 判断是否需要进行初始化
  • f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功
  • 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
  • 如果都不满足，则利用 synchronized 锁写入数据
  • 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树

Map实现类的性能分析及适用场景

HashMap与Hashtable实现机制几乎一样，但是HashMap比Hashtable性能更好些。
LinkedHashMap比HashMap慢一点，因为它需要维护一个双向链表。
TreeMap比HashMap与Hashtable慢（尤其在插入、删除key-value时更慢），因为TreeMap底层采用红黑树来管理键值对。
适用场景：
一般的应用场景，尽可能多考虑使用HashMap，因为其为快速查询设计的。
如果需要特定的排序时，考虑使用TreeMap。
如果仅仅需要插入的顺序时，考虑使用LinkedHashMap。

集合框架之间的区别

数组与集合的区别

  1. 数组长度不可变化而且无法保存具有映射关系的数据；集合类用于保存数量不确定的数据，以及保存具有映射关系的数据
  2. 数组元素既可以是基本类型的值，也可以是对象；集合只能保存对

Set和List的区别

  1. Set 接口实例存储的是无序的，不重复的数据。List 接口实例存储的是有序的，可以重复的元素
  2. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>
  3. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变 <实现类有ArrayList,LinkedList,Vector>