不断的学习,我们才能不断的前进
一个好的程序员是那种过单行线马路都要往两边看的人

java集合类

1. 简介

javacollection

虚线箭头表示实现接口,实现箭头表示继承基类

1.1 总结

集合类可以分为三种:Map(映射)、Set(集合)、List(列表),其中set 和list 都实现了Collection接口;map 实现了Map接口。

  1. 集合和数组的区别?
    • 集合长度可变;数组长度固定
    • 集合只能存放引用类型;数组既可以存放引用类型,也可以存放基本类型。
    • 集合可以存放不同类型的数据;数组只能存放同一类型的数据。
  2. list 和 set 的区别?
    • list插入的数据是有序的;set不能保证有序性(存取顺序不一致)。
    • list元素可以重复; set里面元素是唯一的。
    • list可以直接通过索引来获取元素;set不可以通过索引获取。
是否有序 是否允许元素重复 是否线程安全 是否为空
LinkedList $\times$
ArrayList $\times$
HashSet $\times$ $\times$ $\times$
TreeSet $\times$ $\times$ $\times$
HashMap $\times$ k唯一, value可以重复 $\times$
TreeMap k唯一, value可以重复 $\times$ k不可以为空, value可以
HashTable $\times$ k唯一, value可以重复 $\times$

TreeMap 是基于红黑树来实现的,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
LinkedHashSet 是继承来HashSet,但是同时又使用了链表结构来保证数据的有序性,所以效率低下。

2. List

LinkedList与ArrayList 都是实现了List接口的容器类,可以用来存储对对象的引用。

2.1 LinkedList

linkedList底层是双向链表,所以对于插入和删除所耗费的时间是一样的。但是对于add和remove需要遍历整个链表,所以比较耗费时间。

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

因为底层是链表所以不支持高效的随机访问。

2.2 ArrayList

ArrayList 是实现了基于动态数组的数据结构,初始容量大小为10,当添加数据时会判断是否需要扩容,每次扩容以1.5倍原数组长度进行扩容。

private static final int DEFAULT_CAPACITY = 10; //初始数组容量
// 扩容
private void grow(int minCapacity) { //minCapacity初始为10
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5 倍扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

底层还是数组来实现的,所以访问和修改数据,get和set方法要好一点
主要空间浪费在保留以一定的数组容量空间。
插入一个元素,该元素后面的所有元素都要后移
Question:

  1. ArrayList可以用来做队列吗?
    队列就是FIFO,先入先出,就需要在尾部添加元素,在头部删除元素,当删除元素时,后后移后面的所有元素,时间耗费比较大,不建议;
    但是数组可以用来做队列,因为数组是定长的,只需要维护两个指针来标记读位置和写位置就行,维护成一个环形数组。
  2. ArrayList是怎样删除和新增数据的?
    当删除时,ArrayList会拷贝删除索引后面的所有元素,然后覆盖到当前索引开始的位置。

注意ArrayList虽然默认容量是10,但是只会在第一次add的时候容量会变成10。之前都是空数组。
ArrayList参考博客

Vector

Vector 与ArrayList 一样,也是通过数组实现的,不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,
访问它比访问ArrayList 慢.

在方法上使用synchronized关键字修饰

2.3. 比较

ArrayList在查询比较多,但是插入和删除比较少的情况使用,
LinkedList在查询比较少而插入删除比较多的情况下使用。
ArrayList的遍历性能比LinkedList块很多,因为ArrayList底层是数组,是连续的内存空间。

3. Set

set保证元素唯一,不可重复,通过hashcode来判断对象是否相等。用于存储无序的元素.

3.1 HashSet

底层数据结构采用哈希表实现,元素无序且唯一,线程不安全,效率高,可以存储null元素,但只能放入一个null,元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的,如果没有重写这两个方法,则无法保证元素的唯一性。
HashSet 首先判断两个元素的哈希值,如果哈希值一样,接着会比较equals 方法, 如果 equls 结果为true ,HashSet 就视为同一个元素。如果equals 为false 就不是同一个元素。

底层使用的是HashMap

3.2 TreeSet

底层数据结构采用二叉树来(红黑树),元素有序(根据比较的返回值是否是0来决定元素是否唯一)实现,元素唯一且已经排好序,不允许放入null值 ;唯一性同样需要重写hashCode()和equals()方法,二叉树结构保证了元素的有序性。根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造),自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法,元素通过比较返回的int值来判断排序序列,返回0说明两个对象相同,不需要存储;比较器排序需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象,或者采用匿名内部类的方式new一个Comparator对象,重写里面的compare()方法;

LinkHashSet

LinkedHashSet是有序的,保存的是插入的顺序. 它继承与HashSet, 其所有的方法操作上又与HashSet 相同,因此LinkedHashSet 的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类HashSet的构造器,底层是构造一个LinkedHashMap 来实现,在相关操作上与父类HashSet 的操作相同,直接调用父类HashSet 的方法即可。

HashSet 使用LinkedHashMap的构造方法只为子类LinkHashSet使用.

3.3 比较

HashSet是基于Hash算法实现的,其性能通常都优于TreeSet。为快速查找而设计的Set,我们通常都应该使用HashSet,在我们需要排序的功能时,我们才使用TreeSet。

4. Map

4.1 HashMap

在jdk1.7中,HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当链表中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。在jdk1.8新增了红黑树结构,当链表长度大于8时采用红黑树结构,$\color{red}{因为红黑树具有快速增删改查的特点}$,hashMap的默认初始化大小为16,默认的加载因子(扩容因子)为0.75。
JDK 1.8 之所以添加红黑树是因为一旦链表过长,会严重影响 HashMap 的性能,而红黑树具有快速增删改查的特点,这样就可以有效的解决链表过长时操作比较慢的问题。
hashmap

hashMap是线程不安全的,在并发情况下可能会发生死锁。

  1. jdk1.8 HashMap扩容时做了哪些优化?
    • 数组+链表改成了数组+链表或红黑树 (防止hash冲突,链表长度过长时降低时间复杂度)
    • 链表的插入方式从头插法改成了尾插法。(避免多线程加扩容时,产生环的问题)
    • 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置,1.8采用更简单的判断逻辑,位置不变或索引+旧容量大小。
      扩容时,使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置(左移一位);
      所以我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”
  • 在插入时,1.7先判断是否需要扩容,再插入,1.8先进行插入,插入完成再判断是否需要扩容;

oldCap为原表的容量
扩容方式:创建一个新的Entry空数组,长度是原数组的2倍。遍历原Entry数组,把所有的Entry重新Hash到新数组。

  1. 加载因子为什么是0.75?
    当hashMap元素个数达到加载因子*初始容量时就会扩容,设置为0.75是考虑到容量和性能之间的平衡。
  • 当加载因子设置比较大的时候,扩容的门槛就被提高了,扩容发生的频率比较低,占用的空间会比较小,但此时发生Hash冲突的几率就会提升,因此需要更复杂的数据结构来存储元素,这样对元素的操作时间就会增加,运行效率就会降低。
  • 而当加载因子值比较小的时候,扩容的门槛会比较低,因此会占用更多的空间,此时元素的存储就比较稀疏,发生哈希冲突的可能性就比较小,因此操作性能会比较高。
  1. 当有哈希冲突时,HashMap 是如何查找并确认元素的?
    查询元素时,当哈希冲突时通过$\color{red}{判断key值是否相等}$,来确定元素是否是查询的元素。
  2. HashMap 是如何导致死循环的?
    发生死循环的原因是 JDK 1.7 链表插入方式为首部倒序插入,这个问题在 JDK 1.8 得到了改善,变成了尾部正序插入.
    所以在并发的情况,发生扩容时,可能会产生循环链表,在执行get的时候,会触发死循环,引起CPU的100%问题,所以一定要避免在并发环境下使用HashMap。并发操作下建议使用ConcurrentHashMap 替代。
  3. HashMap查找元素?
    在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用hash(int h)方法所计算得到的hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中,(n - 1) & hash用于计算对象应该保存在table数组的哪个索引处。HashMap底层数组的长度总是2的n次方,当数组长度为2的n次幂的时候,(n - 1) & hash 算得的index相同的几率较小,数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
  4. hashMap的插入流程?
    hashmapinsert
  5. hashmap 的哈希函数怎么设计的?
    hash函数是先拿到 key 的hashcode,是一个32位的int值,然后让hashcode的高16位和低16位进行异或操作。
  6. 初始化大小容量为什么是16? 容量大小为什么是2的整次幂?
    在创建hashMap的时候会初始化容量大小为2的整次幂,是为了位运算的方便,位与运算比算数计算的效率高了很多。
  7. 为啥重写equals方法的时候需要重写hashCode方法呢?
    因为在java中,所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode,这两个方法都是用来比较两个对象是否相等的。在未重写equals方法我们是继承了object的equals方法,那里的 equals是比较两个对象的内存地址,显然我们new了2个对象内存地址肯定不一样。

先根据key的hashCode方法获取到数组的index,然后在根据equals方法找到该index上的链表或者红黑树对应的对象。

HashMap参考博客

4.2 ConcurrentHashMap

ConcurrentHashMap 和 HashMap 的结构是类似的,在jdk1.8采用的是数组+链表+红黑树,但是因为它支持并发操作,所以额外采取了加锁的机制,在jdk1.7采用的是分段锁+HashEntry, jdk1.8使用的是CAS、synchronized+Node.

jdk1.8的ConcurrentHashMap

数据结构采用的是红黑树+Node, 加锁的机制改为CAS和synchronized. 比如put一个元素的时候:

  1. 根据key计算出hashcode,如果表为空,则进行初始化,
  2. 然后通过&运算判断该位置是否为空,为空则CAS尝试写入,失败则自旋保存成功;
  3. 如果不为空,则判断是否需要进行扩容,否则进行扩容;
  4. 如果都不满足,则加synchronized锁,然后尝试插入结点, 遍历链表如果key和hash都相等,则更新旧值; 否则插入都末尾结点.
  5. 如果插入后达到链表达到阈值,则转换成红黑树.

初始化过程

  1. while循环判断表是否为空,为空则进入while循环,
  2. 判断sizeCtl(volatile关键字修饰)变量是否为-1,-1表示正在进行初始化,为-1则线程退出.
  3. CAS操作把sizeCtl变量设置为-1,并进行初始化,
  4. 最后设置sizeCtl 为表的大小.

sizeCtl为0 表示初始容量为空; 大于0 表示初始容量; -1表示其他线程正在执行初始化, 小于0 表示有其他线程正在执行扩容; (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2 表示只有一个线程在执行扩容.

扩容过程

jdk1.7的ConcurrentHashMap

ConcurrentHashMap 是一个 Segment 数组,Segment 通过继承ReentrantLock 来进行加锁,所以每次需要加锁的操作锁住的是一个 segment,这样只要保证每个Segment 是线程安全的,也就实现了全局的线程安全.
Segment是ConcurrentHashMap的内部类,继承于ReentrantLock.

4.3 HashTable

HashTable 跟HashMap 类似, 但是继承与Dictionary, 在每个方法上面使用synchronized关键字修饰, 加锁的粒度比较大. 任何时候只允许一个线程访问.

hashMap key和value都可以为空, HashTable和ConcurrentHashMap key 和value 都不可以为null.
hashMap 计算hash值的时候做了特殊处理,如果key为null,就赋值为0,否则进行hashCode计算.

4.4 LinkedHashMap

LinkedHashMap 是有序的HashMap, 以元素的插入顺序为序. 继承于HashMap类. 内部构建了一个内部类Entry 继承于HashMap 的Node 类. Entry 是一个双向的链表结构,保证了插入的Entry中的顺序. 所以LinkedHashMap 就是HashMap + 双向链表的结构.

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

通过afterNodeRemoval,afterNodeInsertion,afterNodeAccess 来修改指针维护Entry链表.
使用场景: LRU(最近最少使用):通过继承LinkedHashMap类,并重写removeEldestEntry方法

@Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }

使用方式
默认的构造方法使用的是插入顺序, get不会修改元素的访问顺序;
设置accessOrder为true的构造方法使用的是访问顺序, 当没有get的时候还是插入顺序, 如果发生类get操作,当前访问的元素插入到链表末尾,变成最后一个访问.

4.5 TreeMap

TreeMap 也是有序的Map类, 对于传入的类型,必须实现Comparable接口. 比如传入Integer、String类默认就是按照自然排序. 也可以通过构造方法传入Comparable的实现类.
TreeMap的底层是有序的二叉树, 也就是红黑树. 插入过程就是从跟节点开始, 与插入结点进行比较,如果小于则插入左孩子, 大于则插入右孩子, 等于则更新旧的值. 最后修改二叉树,使其满足红黑树的要求.

在插入的过程会判比较器(Comparable) 是否为空, 为空则使用key的比较器. 如果key没有实现Comparable接口则会抛出异常.


目录