集合底层原理

Collection 单列集合

List 集合

List 集合的三个子类:

   ArrayList:底层是数组,查询快(地址连续)、增删慢、线程非安全。

   LinkedList:底层是链表,查询慢、增删快、无索引、线程非安全。

   Vector:底层是数组,线程安全。

一、ArrayList 原理

1.1 构造方法

集合底层原理_第1张图片

ArrayList 底层是一个数组结构,当指定初始容量为0时返回的是 EMPTY_ELEMENTDATA,不指定容量时返回 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

集合底层原理_第2张图片

1.2 add 方法

集合底层原理_第3张图片

1. 确认list容量,尝试容量加1看有无必要,因为当添加一个元素后,可能对超过集合初始容量,将会引发扩容。如果没有超过初始容量则保存最小容量不变,无需对容量+1。

2. 添加元素

集合底层原理_第4张图片

第一个方法得到数组的最小容量,避免资源浪费,第二个方法判断最小容量是否大于数组长度,大于则调用grow()进行扩容。

grow()扩容的实现

集合底层原理_第5张图片

newCapacity 这里对数组容量扩容1.5倍,扩容完毕后调用 copyOf() ,完成对数组元素的拷贝。

总的来说 add(E e) 的实现: 首先检查数组容量是否足够,够直接添加元素,不够进行扩容。

1.3 get 方法

集合底层原理_第6张图片

检查角标是否越界,然后添加元素。

1.4 set 方法

集合底层原理_第7张图片

检查是否越界,替换元素。

1.5 remove() 方法

集合底层原理_第8张图片

numMoved 是需要移动的元素个数,从 index+1位置开始拷贝 numMoved 个元素 到数组的 index 位置,就等于将被删除元素后面的所有元素往前移动一个位置。因此List集合删除效率低。

二、Vector 和 ArrayList 区别(面试)

Vector 是同步的(线程安全),其内部方法都使用 synchronized 修饰,同样Vector因此效率比较低下。ArrayList 线程非安全。

ArrayList 底层扩容是在原有基础上扩容1.5 倍,Vector是扩容 2 倍。

三、LinkedList 原理

LinkedList 集合特点:

1. 底层是双向链表,查询慢,增删快。 2. 包含大量操作首尾的方法。

3.1 add 方法

集合底层原理_第9张图片

了解过链表底层实现的应该对 LinkedList 的方法并不陌生,无论是添加还是删除方法,都拆分为 对头部和尾部元素的具体操作。

这里 add 方法采用尾插法,同样也有 addFirst addLast 方法。

3.2 remove 方法

集合底层原理_第10张图片

unlink(x) 完成对元素的删除,删除元素调用 equals 方法其实就是判断元素是否存在链表中,unlink 方法中实现了双向链表中删除元素的操作。

集合底层原理_第11张图片

将被删除节点断开,通过①②连接链表。

3.3 get 方法

判断下标是否合法,然后调用node方法获取链表元素。

集合底层原理_第12张图片

3.4 set 方法

与 get 方法类似,根据下标判断从头遍历还是从尾遍历。

Set 集合

Set 集合的使用频率相比 List 集合较低,通常结合 set 集合 元素不可重复的特点进行一些操作,比如寻找只出现一次的数字、或者在实际项目中需要存储不可重复元素可以考虑使用 Set 集合。

一、Set集合常用子类

  • HashSet集合

    • A:底层数据结构是HashMap

    • B:允许null,非同步

  • TreeSet集合

    • A:底层数据结构是红黑树(是一个自平衡的二叉树)

    • B:保证元素的排序方式,不允许null,非同步

  • LinkedHashSet集合

    • A:底层数据结构由HashMap和双向链表组成。

    • B:允许null

二、HashSet集合

java.util.HashSet 集合 implements Set接口

HashSet是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于:hashCode与equals方法。

2.1 HashSet特点:

    1.不允许存储重复元素,允许元素为null

    2.没有索引,没有带索引的方法,也没有for循环遍历

    3.是一个无序的集合,存储元素和取出元素的顺序有可能不一致

    4.底层是HashMap(查询速度非常快)

            Set set = new HashSet<>(); //多态
            //使用add方法往集合中添加元素
            set.add(1);
            set.add(3);
            set.add(2);
            set.add(1);
            //使用迭代器遍历set集合
            Iterator it = set.iterator();
            while(it.hasNext()){
                Integer n = it.next();
                System.out.println(n); //1,2,3 不允许存储重复元素,无序
            }
            //增强for遍历set集合
            for(Integer n:set){
                System.out.print(n);
            }

2.2 HashSet集合存储结构(哈希表)

在JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理哈希冲突,同一hash值的链表都存储在一个链表里。但是当hash值相等的元素较多时,通过key值在链表中依次查找的效率较低。JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过(8)时,将链表转换为红黑树,这样大大减少了查找时间。

集合底层原理_第13张图片

要保证HashSet集合元素的唯一,就必须复写hashCode和equals方法建立属于当前对象的比较方式。(面试常考hashCode 和 equals 的联系)

① 重写 hashCode 必须同时重写equals。

② 相等(相同)的对象必须具有相等的哈希码(或者散列码)。

③ 如果两个对象的hashCode相同,它们并不一定相同。

Map 双列集合

 java.util.Map集合 存储的元素是键值对类型,key - value是一一对应的映射关系。

Map集合特点:

key 和 value 数据类型是任意的,一般我们习惯使用key为String类型,value为Object类型。

key 不允许重复,value 可以重复,key只允许存在一个null的情况,value可以存在多个null值。

一、Collection 与 Map的区别(面试)

1. Map 集合存储元素是键值对的方式,键唯一,值可以重复。

2. Collection 集合存储元素是单独出现的,Collection 的子接口Set值是唯一的,List是可重复的。

二、哈希表

List 集合底层是链表或者数组,存储的顺序和取出的顺序是一致的,但同样会带来一个缺点,想要获取某个元素,就要访问所有元素,直到找到为止。

在哈希表中,我们不在意元素的顺序,能够快速查找到元素。哈希表中每个对象按照哈希值保存在对应的位置上。哈希表是由数组+链表实现的,每个列表称为桶,

集合底层原理_第14张图片

JDK1.8 之前 哈希值相同的对象以链表形式存储在一个桶中,这种情况称为哈希冲突,此时需要用该对象与桶上的对象进行比较,看看是否已经存在桶中,如果存在就不添加。(这个过程使用hashCode和equals进行判断,这也是之前我们说过为什么要同时重写hashCode和equals的原因),接下来了解了HashMap的put方法底层原理,应该会对为什么同时重写更加清晰了。

JDK1.8 之后 当链表长度超过8,会从链表转换为红黑树结构当哈希表存储元素太多,需要对其进行扩展,创建一个桶更多的哈希表,那么什么时候需要进行扩容?装填因子(load factor)决定了何时进行扩展,装载因子默认为0.75,表中如果超过75%的位置已经填入元素,将进行双倍的扩展。

三、HashMap 原理

3.1 HashMap 类前注释解读

主要讲了 HashMap 的一些特点:key value 允许为null不保证有序不同步(线程非安全),想实现同步调用Collections.synchronizedMap,装载因子为0.75。使用迭代器进行遍历。当知道要存储的元素个数时,尽可能设置初始容量。

3.2 HashMap 属性

集合底层原理_第15张图片

当链表长度大于8,数组元素超过64 由链表结构转化为红黑树。

JDK1.7 时,在实例化之后,底层创建了长度是16的Entry数组。

JDK1.8 时,底层为Node数组,调用put方法后创建长度为16的数组。虽然长度为16,但是切记,负载因子0.75,因此数组只存放12个元素。

3.3 put 方法

put 方法是HashMap的核心,也是面试常考点。

调用 hash(key) 方法,以key计算哈希值,hash 方法中得到key的hashCode 与 key的hashCode 高16位做异或运算,得到的值可以减少碰撞冲突的可能性。

集合底层原理_第16张图片

1、hash(key),取key的hashcode进行高位运算,返回hash值
2、如果hash数组为空,直接resize()
3、对hash进行取模运算计算,得到key-value在数组中的存储位置i
(1)如果table[i] == null,直接插入Node
(2)如果table[i] != null,判断是否为红黑树p instanceof TreeNode。
(3)如果是红黑树,则判断TreeNode是否已存在,如果存在则直接返回oldnode并更新;不存在则直接插入红黑树,++size,超出threshold容量就扩容
(4)如果是链表,则判断Node是否已存在,如果存在则直接返回oldnode并更新;不存在则直接插入链表尾部,判断链表长度,如果大于8则转为红黑树存储,++size,超出threshold容量就扩容

3.4 get 方法

我们知道HashMap 是通过key找value,获取key的哈希值,调用getNode方法获取对应value。

getNode 的实现比较简单,先判断计算出来的hashCode是否存在哈希表中,然后判断是否在桶的首位,不在则在链表或红黑树中进行遍历。

3.5 remove 方法

类似于put方法,这里就不贴源码,可以在util包下查看源码。

计算key 的hash值,然后去找对应节点,找到后分三种情况进行删除:1. 链表 2. 红黑树 3. 桶的首位

四、HashMap 与 Hashtable 对比

1、继承的父类不同

Hashable继承自Dictionary类,而HashMap继承自AbstractMap类。但二者都实现了Map接口。

2、线程安全性不同

HashTable是线程安全的,HashTable方法都加入了Synchronized,HashMap是非安全的。

3、是否提供contains方法

HashMap把contains方法去掉了,改成containsValue和containsKey,因为contains方法容易让人引起误解。

Hashtable则保留了contains,containsValue和containsKey三个方法,其中contains和containsValue功能相同。

4、key和value是否允许null值

其中key和value都是对象,并且不能包含重复key,但可以包含重复的value。

HashMap允许空值,键key最多只能1个null值,value允许多个null,HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。

Hashtable中,key和value都不允许出现null值。

5、两个集合遍历方式的内部实现上不同

Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式

6、hash值不同

哈希值的使用不同,HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

7、内部实现使用的数组初始化和扩容方式不同

HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

集合底层原理_第17张图片

图文并茂,对比很细,加粗部分可作为面试主答点。

五、LinkedHashMap 原理

5.1 LinkedHashMap 类前注释解读

底层是哈希表+链表,允许为null,线程不同步,插入元素有序

5.2 总结

这里没有对LinkedHashMap具体方法进行解析,因为它继承自HashMap,在很多操作上使用的是HashMap的方法。而HashMap的方法我们上面已经进行了分析。

六、TreeMap 原理

6.1 TreeMap 类前注释解读

底层是红黑树,实现NavigableMap 接口,可以根据key自然排序,也可以在构造方法上传递Camparator实现Map的排序。不同步

TreeMap 实现NavigableMap 接口,而NavigableMap接口继承着SortedMap接口,致使我们的TreeMap是有序的。

key不能为null。

6.2 构造方法

集合底层原理_第18张图片

    //comparator 维护的变量为null,使用自然排序
    public TreeMap() {
        comparator = null;
    }
    //设置一个维护变量传入
    public TreeMap(Comparator comparator) {
        this.comparator = comparator;
    }
    //调用putAll将Map转为TreeMap
    public TreeMap(Map m) {
        comparator = null;
        putAll(m);
    }
    //使用buildFromSorted转TreeMap
    public TreeMap(SortedMap m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

6.3 put 方法

集合底层原理_第19张图片

6.4 get 方法

get 方法由getEntry进行具体实习

集合底层原理_第20张图片

getEntry

集合底层原理_第21张图片

当 comparator 不为null时,getEntryUsingComparator(Object key) 调用Comparator 自己实现的方法获取相应的值。

6.5 总结

TreeMap底层是红黑树,能够实现该Map集合有序

如果在构造方法中传递了Comparator对象,那么就会以Comparator对象的方法进行比较。否则,则使用Comparable的compareTo(T o)方法来比较。(自然排序)

  • 值得说明的是:如果使用的是compareTo(T o)方法来比较,key一定是不能为null,并且得实现了Comparable接口的。

  • 即使是传入了Comparator对象,不用compareTo(T o)方法来比较,key也是不能为null的。

 七、ConcurrentHashMap

重头戏来了~~~~

7.1 JDK1.7和JDK1.8 不同

1. JDK1.7 底层实现是:segments+HashEntry数组

集合底层原理_第22张图片

ConcurrentHashMap使用分段锁技术,Segment继承了ReentrantLock,每个片段都有了一个锁,叫做“锁分段

我们知道Map中Hashtable是线程安全的,为什么要用ConCurrentHashMap?

Hashtable 是在每个方法上都加上了Synchronized 完成同步,效率极其低下,而ConcurrentHashMap通过部分加锁利用CAS算法来实现同步。

2. JDK 1.8底层实现是:哈希表+红黑树

检索操作不用加锁,get方法是非阻塞的,key和value都不允许为空。

取消了1.7的 segments 分段锁机制,采用CAS + volatile 乐观锁机制保证线程同步。

7.2 CAS算法和volatile简单介绍

1. CAS(Compare and swap,比较与交换)

CAS 是一种基于乐观锁的操作。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住,等一个之前获得锁的线程释放锁之后,下一个线程才可以访问。而乐观锁采取了一种宽泛的态度,通过某种方式不加锁来处理资源,比如通过给记录加version来获取数据,性能较悲观锁有很大的提高。

CAS有3个操作数

  • 内存值V

  • 旧的预期值A

  • 要修改的新值B

当且仅当预期值A和内存值V相同时,将内存值V修改为B。CAS是通过无限循环来获取数据的,若果在第一轮循环中,a线程获取地址里面的值被b线程修改了,那么a线程需要自旋,到下次循环才有可能机会执行。

2. volatile 关键字

volatile仅仅用来保证该变量对所有线程的可见性,但不保证原子性

可见性:在多线程环境下,当被volatile修饰的变量修改时,所有的线程都可以知道该变量被修改了

不保证原子性:修改变量(赋值)实质上是分为好几步操作,在这几步操作中是不安全的。

7.2 put 方法

集合底层原理_第23张图片

put操作采用CAS+synchronized 实现并发插入或更新操作。

  • 如果没有初始化就先调用initTable()方法来进行初始化过程
  • 如果没有hash冲突就直接CAS插入
  • 如果还在进行扩容操作就先进行扩容
  • 如果存在hash冲突,就加 synchronized 锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入,
  • 最后一个如果Hash冲突时会形成Node链表,在链表长度超过8,Node数组超过64时会将链表结构转换为红黑树的结构,break再一次进入循环
  • 如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容

 initTable 方法的实现

当要初始化时会通过CAS操作将sizeCtl置为-1,而sizeCtl由volatile修饰,保证修改对后面线程可见。
这之后如果再有线程执行到此方法时检测到sizeCtl为负数,说明已经有线程在给扩容了,这个线程就会调用Thread.yield()让出一次CPU执行时间。

集合底层原理_第24张图片

7.3 get 方法

我们之前说到 get 操作不用加锁,是非阻塞的,因为 Node 节点被重写了,设置了volatile关键字修饰,致使它每次获取的都是最新设置的值。

集合底层原理_第25张图片

八、CopyOnWriteArrayList 原理

CopyOnWriteArrayList是线程安全容器(相对于ArrayList),底层通过复制数组的方式来实现。

CopyOnWriteArrayList在遍历的使用不会抛出ConcurrentModificationException异常,并且遍历的时候就不用额外加锁。

8.1 CopyOnWriteArrayList 基本结构

CopyOnWriteArrayList底层是数组,加锁交由ReentrantLock来完成

    //可重入锁对象
    final transient ReentrantLock lock = new ReentrantLock();

    //CopyOnWriteArrayList底层由数组实现,volatile修饰
    private transient volatile Object[] array;

    //得到数组
    final Object[] getArray() {
        return array;
    }
    //设置数组
    final void setArray(Object[] a) {
        array = a;
    }

    //初始化数组
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

8.2 add 方法

    public boolean add(E e) {
        //加锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //得到原数组长度和元素
            Object[] elements = getArray();
            int len = elements.length;
            //复制一个新数组
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            //将元素添加到新数组
            newElements[len] = e;
            //将volatile Object[] array 的指向替换成新数组
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

在添加的时候上锁,并复制一个新数组,添加操作在新数组上完成,将array指向到新数组中,最后解锁。

8.3 set 方法

    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            //得到原数组旧值
            Object[] elements = getArray();
            E oldValue = get(elements, index);
            //判断新值和旧值是否相等
            if (oldValue != element) {
                int len = elements.length;
                //复制新数组,在新数组中完成修改
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                //array引用指向新数组
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }
  • 在修改时,复制出一个新数组,修改的操作在新数组中完成,最后将新数组交由array变量指向

  • 写加锁,读不加锁,读取数据是在原数组,因此保证了多线程下的数据一致性。

  • 类似于读写分离的思想,读和写分别在不同的容器完成,写时进行读操作并不会读到脏数据。

8.4 CopyOnWriteArrayList缺点

占用内存:如果CopyOnWriteArrayList经常要增删改里面的数据,经常要执行add()、set()、remove()进行新数组创建,那是比较耗费内存的。

数据一致性:CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性

面试题总结

上面标注(面试)的这里就不再阐述。。。

List 和 Map的区别

存储结构不同:List 是存储单列的集合,Map是存储key-value键值对的集合

元素是否可重复:List 允许重复元素,Map不允许key重复

是否有序:List集合是有序的(存储有序),Map集合是无序的。

Collection和Collections的区别

Collection是集合的上级接口,继承它的有Set和List接口

Collections是集合的工具类,提供了一系列的静态方法对集合的搜索、查找、同步等操作

ArrayList,Vector,LinkedList的存储性能和特征?

ArrayList和Vector都是使用数组方式存储元素,可以直接按照索引查找元素、访问快、增删慢(相对的,极端情况不考虑)。

LinkedList使用双向链表存储数据、查找慢、增删快(相对的,极端情况不考虑)。

Vector使用了synchronized方法,线程安全,性能上较ArrayList差。LinkedList也是线程不安全的,LinkedList提供了一些方法,使得它可以被当作堆栈或者队列来使用。

Java中HashMap的key值要是为类对象则该类需要满足什么条件?

需要同时重写该类的hashCode()方法和equals方法。

原因:

插入元素时先计算hashCode值,相等则调用 equals() 方法,两个key相同替换元素值,两个key不相同,说明 hashCode 值是碰巧相同,则将新增元素放在桶里。

我们一般认为,只要两个对象的成员变量的值是相等的,那么我们就认为这两个对象是相等的,因此要重写equals()f方法,重写了equals(),就必须重写hashCode()方法,因为equals()认定了这两个对象相同,而同一个对象调用hashCode()方法时,是应该返回相同的值的!

你可能感兴趣的