文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java集合框架是什么

2023-06-29 13:07

关注

这篇文章主要介绍了Java集合框架是什么,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。

一、简介

1、集合框架介绍

Java集合框架提供了一套性能优良,使用方便的接口和类,他们位于java.util包中。容器主要包括 Collection 和 Map 两种,Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表

Java集合框架是什么

2、相关容器介绍

2.1 Set相关

2.2 List相关

2.3 Queue相关

2.4 Map相关

3、集合重点

二、ArrayList分析

1、ArrayList使用

方法说明
boolean add(Object o)在列表的末尾顺序添加元素,起始索引位置从0开始
void add(int index, Object o)在指定的索引位置添加元素,索引位置必须介于0和列表中元素个数之间
int size()返回列表中的元素个数
Object get(int index)返回指定索引位置处的元素。取出的元素是Object类型,使用前品要进行益制类型转换
boolean contains(Object o)判断列表中是否存在指定元素
boolean remove(Object o)从列表中删除元素
Object remove(int index)从列表中删除指定位置元素,起始索引位量从0开始

2、ArrayList介绍

另外,ArrayList和Vector的区别是:ArrayList是线程不安全的,当多条线程访问同一个ArrayList集合时,程序需要手动保证该集合的同步性,而Vector则是线程安全的。

3、源码分析

3.1 继承结构与层次关系

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Java集合框架是什么
这里简单解释一下几个接口

这里的继承结构可通过IDEA中Navigate>Type Hierarchy查看

Java集合框架是什么

3.2 属性

//版本号private static final long serialVersionUID = 8683452581122892189L;//缺省容量private static final int DEFAULT_CAPACITY = 10;//空对象数组private static final Object[] EMPTY_ELEMENTDATA = {};//缺省空对象数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//存储的数组元素transient Object[] elementData; // non-private to simplify nested class access//实际元素大小,默认为0private int size;//最大数组容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3.3 构造方法

public ArrayList(int initialCapacity) {    if (initialCapacity > 0) {        this.elementData = new Object[initialCapacity];    } else if (initialCapacity == 0) {        this.elementData = EMPTY_ELEMENTDATA;    } else {        throw new IllegalArgumentException("Illegal Capacity: "+                                           initialCapacity);    }}public ArrayList() {    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(Collection<? extends E> c) {    elementData = c.toArray();    if ((size = elementData.length) != 0) {        // 转换为数组        //每个集合的toarray()的实现方法不一样,所以需要判断一下,如果不是Object[].class类型,那么久需要使用ArrayList中的方法去改造一下。        if (elementData.getClass() != Object[].class)            elementData = Arrays.copyOf(elementData, size, Object[].class);    } else {        // 否则就用空数组代替        this.elementData = EMPTY_ELEMENTDATA;    }}

3.4 自动扩容

每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前,我也可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增式再分配的数量。

数组进行扩容时,会将**老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。**这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造ArrayList实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量

private void ensureCapacityInternal(int minCapacity) {    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {    //判断初始化的elementData是不是空的数组,也就是没有长度    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {        //因为如果是空的话,minCapacity=size+1;其实就是等于1,空的数组没有长度就存放不了        //所以就将minCapacity变成10,也就是默认大小,但是在这里,还没有真正的初始化这个elementData的大小        return Math.max(DEFAULT_CAPACITY, minCapacity);    }    //确认实际的容量,上面只是将minCapacity=10,这个方法就是真正的判断elementData是否够用    return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {    modCount++;    //minCapacity如果大于了实际elementData的长度,那么就说明elementData数组的长度不够用         if (minCapacity - elementData.length > 0)        grow(minCapacity);}//ArrayList核心的方法,能扩展数组大小的真正秘密。private void grow(int minCapacity) {    //将扩充前的elementData大小给oldCapacity    int oldCapacity = elementData.length;    //newCapacity就是1.5倍的oldCapacity    int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    //如果newCapacity超过了最大的容量限制,就调用hugeCapacity,也就是将能给的最大值给newCapacity    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    //新的容量大小已经确定好就copy数组,改变容量大小。    elementData = Arrays.copyOf(elementData, newCapacity);}//用来赋最大值private static int hugeCapacity(int minCapacity) {    if (minCapacity < 0) // overflow        throw new OutOfMemoryError();    //如果minCapacity都大于MAX_ARRAY_SIZE,那么就Integer.MAX_VALUE返回,反之将MAX_ARRAY_SIZE返回。    //相当于给ArrayList上了两层防护    return (minCapacity > MAX_ARRAY_SIZE) ?        Integer.MAX_VALUE :        MAX_ARRAY_SIZE;}

3.5 add()方法

public boolean add(E e) {    ensureCapacityInternal(size + 1);  // Increments modCount!!    elementData[size++] = e;    return true;}public void add(int index, E element) {    //检查index也就是插入的位置是否合理。    rangeCheckForAdd(index);    //检查容量是否够用,不够就自动扩容    ensureCapacityInternal(size + 1);  // Increments modCount!!    //这个方法就是用来在插入元素之后,要将index之后的元素都往后移一位    System.arraycopy(elementData, index, elementData, index + 1,                     size - index);    elementData[index] = element;    size++;}

当调用add()方法时,实际函数调用:

add→ensureCapacityInternal→ensureExplicitCapacity(→grow→hugeCapacity)

例如刚开始初始化一个空数组后add一个值,会首先进行自动扩容
Java集合框架是什么

3.6 trimToSize()

将底层数组的容量调整为当前列表保存的实际元素的大小的功能

public void trimToSize() {    modCount++;    if (size < elementData.length) {        elementData = (size == 0)          ? EMPTY_ELEMENTDATA          : Arrays.copyOf(elementData, size);    }}

3.7 remove()方法

remove()方法也有两个版本,一个是remove(int index)删除指定位置的元素,另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必须显式的为最后一个位置赋null值。

public E remove(int index) {        rangeCheck(index);        modCount++;        E oldValue = elementData(index);        int numMoved = size - index - 1;        if (numMoved > 0)            System.arraycopy(elementData, index+1, elementData, index,                             numMoved);        elementData[--size] = null; //清除该位置的引用,让GC起作用        return oldValue;    }

3.8 其他方法

这里简单介绍了核心方法,其他方法查看源码可以很快了解

3.9 Fail-Fast机制

ArrayList采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败,并抛出ConcurrentModificationException异常,而不是冒着在将来某个不确定时间发生任意不确定行为的风险

4、总结

三、LinkedList分析

1、LinkedList使用

方法名说明
void addFirst(Object o)在列表的首部添加元素
void addLast(Object o)在列表的未尾添加元素
Object getFirst()返回列表中的第一个元素
Object getLast()返回列表中的最后一个元素
Object removeFirst()删除并返回列表中的第一个元素
Object removeLast()删除并返回列表中的最后一个元素

2、LinkedList介绍

LinkedList同时实现了List接口和Deque接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来,LinkedList简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类,更遗憾的是,Java里根本没有一个叫做Queue_的类(它是个接口名字)。关于栈或队列,现在的首选是ArrayDeque,它有着比LinkedList(当作栈或队列使用时)有着更好的性能。

LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间,而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized),如果需要多个线程并发访问,可以先采用Collections.synchronizedList()方法对其进行包装

3、源码分析

3.1 继承结构与层次

public class LinkedList<E>    extends AbstractSequentialList<E>    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Java集合框架是什么
Java集合框架是什么

这里可以发现LinkedList多了一层AbstractSequentialList的抽象类,这是为了减少实现顺序存取(例如LinkedList)这种类的工作。如果自己想实现顺序存取这种特性的类(就是链表形式),那么就继承 这个AbstractSequentialList抽象类,如果想像数组那样的随机存取的类,那么就去实现AbstracList抽象类。

3.2 属性与构造方法

transient关键字修饰,这也意味着在序列化时该域是不会序列化的

//实际元素个数transient int size = 0;//头结点transient Node<E> first;//尾结点transient Node<E> last;
public LinkedList() {}public LinkedList(Collection<? extends E> c) {    this();    //将集合c中的各个元素构建成LinkedList链表    addAll(c);}

3.3 内部类Node

//根据前面介绍双向链表就知道这个代表什么了,linkedList的奥秘就在这里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;    }}

3.4 核心方法add()和addAll()

public boolean add(E e) {    linkLast(e);    return true;}void linkLast(E e) {    //临时节点l(L的小写)保存last,也就是l指向了最后一个节点    final Node<E> l = last;    //将e封装为节点,并且e.prev指向了最后一个节点    final Node<E> newNode = new Node<>(l, e, null);    //newNode成为了最后一个节点,所以last指向了它    last = newNode;    if (l == null)        //判断是不是一开始链表中就什么都没有,如果没有,则new Node就成为了第一个结点,first和last都指向它        first = newNode;    else        //正常的在最后一个节点后追加,那么原先的最后一个节点的next就要指向现在真正的 最后一个节点,原先的最后一个节点就变成了倒数第二个节点        l.next = newNode;    //添加一个节点,size自增    size++;    modCount++;}

addAll()有两个重载函数,addAll(Collection<? extends E>)型和addAll(int,Collection<? extends E>)型,我们平时习惯调用的addAll(Collection<?extends E>)型会转化为addAll(int,Collection<? extends<E>)

public boolean addAll(Collection<? extends E> c) {    return addAll(size, c);}public boolean addAll(int index, Collection<? extends E> c) {    //检查index这个是否为合理    checkPositionIndex(index);    //将集合c转换为Object数组    Object[] a = c.toArray();    //数组a的长度numNew,也就是由多少个元素    int numNew = a.length;    if (numNew == 0)        //如果空的就什么也不做        return false;    Node<E> pred, succ;    //构造方法中传过来的就是index==size    //情况一:构造方法创建的一个空的链表,那么size=0,last、和first都为null。linkedList中是空的。    //什么节点都没有。succ=null、pred=last=null    //情况二:链表中有节点,size就不是为0,first和last都分别指向第一个节点,和最后一个节点,    //在最后一个节点之后追加元素,就得记录一下最后一个节点是什么,所以把last保存到pred临时节点中。    //情况三index!=size,说明不是前面两种情况,而是在链表中间插入元素,那么就得知道index上的节点是谁,    //保存到succ临时节点中,然后将succ的前一个节点保存到pred中,这样保存了这两个节点,就能够准确的插入节点了    if (index == size) {        succ = null;        pred = last;    } else {        succ = node(index);        pred = succ.prev;    }    for (Object o : a) {        @SuppressWarnings("unchecked") E e = (E) o;        Node<E> newNode = new Node<>(pred, e, null);        if (pred == null)            first = newNode;        else            pred.next = newNode;        pred = newNode;    }    if (succ == null) {                last = pred;    } else {        pred.next = succ;        succ.prev = pred;    }    size += numNew;    modCount++;    return true;}//根据引下标找到该结点并返回Node<E> node(int index) {    //判断插入的位置在链表前半段或者是后半段    if (index < (size >> 1)) {        Node<E> x = first;        //从头结点开始正向遍历        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        Node<E> x = last;        //从尾结点开始反向遍历        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

3.5 remove()

public boolean remove(Object o) {    if (o == null) {        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {                unlink(x);                return true;            }        }    } else {        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {                unlink(x);                return true;            }        }    }    return false;}不能传一个null值E unlink(Node<E> x) {    // assert x != null;    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }    //x的前后指向都为null了,也把item为null,让gc回收它    x.item = null;    size--;    modCount++;    return element;}

3.6 其他方法

**get(index)、indexOf(Object o)**等查看源码即可

3.7 LinkedList的迭代器

在LinkedList中除了有一个Node的内部类外,应该还能看到另外两个内部类,那就是ListItr,还有一个是DescendingIterator内部类

Java集合框架是什么

private class DescendingIterator implements Iterator<E> {    private final ListItr itr = new ListItr(size());    public boolean hasNext() {        return itr.hasPrevious();    }    public E next() {        return itr.previous();    }    public void remove() {        itr.remove();    }}

4、总结

四、List总结

1、ArrayList和LinkedList区别

两个都是线程不安全的,在iterator时,会发生fail-fast:快速失效

2、ArrayList和Vector区别

3、fail-fast和fail-safe区别与情况说明

在java.util下的集合都是发生fail-fast,而在java.util.concurrent下的发生的都是fail-safe

4、为什么现在都不提倡使用Vector

总结:Vector在你不需要进行线程安全的时候,也会给你加锁,也就导致了额外开销,所以在jdk1.5之后就被弃用了,现在如果要用到线程安全的集合,都是从java.util.concurrent包下去拿相应的类。

五、HashMap分析

1、HashMap介绍

1.1 Java8以前的HashMap

通过key、value封装成一个entry对象,然后通过key的值来计算该entry的hash值,通过entry的hash 值和数组的长度length来计算出entry放在数组中的哪个位置上面,每次存放都是将entry放在第一个位置。

HashMap实现了Map接口,即允许放入keynull的元素,也允许插入valuenull的元素;除该类未实现同步外,其余跟Hashtable大致相同;跟TreeMap不同,该容器不保证元素顺序,根据需要该容器可能会对元素重新哈希,元素的顺序也会被重新打散,因此不同时间迭代同一个HashMap的顺序可能会不同。 根据对冲突的处理方式不同,哈希表有两种实现方式,一种开放地址方式(Open addressing),另一种是冲突链表方式(Separate chaining with linked lists)。Java7 HashMap采用的是冲突链表方式

Java集合框架是什么

1.2 Java8后的HashMap

Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑树 组成。根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度为 O(n)。为了降低这部分的开销,在 Java8 中,当链表中的元素达到了 8 个时,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)
Java集合框架是什么

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点,Java8 中使用 Node,基本没有区别,都是 key,value,hash 和 next 这四个属性,不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode

2、Java8 HashMap源码分析

2.1 继承结构与层次

public class HashMap<K,V> extends AbstractMap<K,V>    implements Map<K,V>, Cloneable, Serializable

Java集合框架是什么

2.2 属性

//序列号private static final long serialVersionUID = 362498820763181265L;//默认的初始容量static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//默认加载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//当桶(bucket)上的结点数大于这个值时会转成红黑树static final int TREEIFY_THRESHOLD = 8;//当桶(bucket)上的结点数小于这个值时树转链表static final int UNTREEIFY_THRESHOLD = 6;//桶中结构转化为红黑树对应的table的最小大小static final int MIN_TREEIFY_CAPACITY = 64;//存储元素的数组,总是2的幂次倍transient Node<K,V>[] table;//存放具体元素的集transient Set<Map.Entry<K,V>> entrySet;//存放元素的个数,注意这个不等于数组的长度transient int size;//每次扩容和更改map结构的计数器transient int modCount;//临界值,当实际大小(容量*填充因子)超过临界值时,会进行扩容int threshold;//填充因子,计算HashMap的实时装载因子的方法为:size/capacityfinal float loadFactor;

2.3 构造方法

public HashMap(int initialCapacity, float loadFactor) {    // 初始容量不能小于0,否则报错    if (initialCapacity < 0)        throw new IllegalArgumentException("Illegal initial capacity: " +                                           initialCapacity);    // 初始容量不能大于最大值,否则为最大值    if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    //填充因子不能小于或等于0,不能为非数字    if (loadFactor <= 0 || Float.isNaN(loadFactor))        throw new IllegalArgumentException("Illegal load factor: " +         loadFactor);    //初始化填充因子                                           this.loadFactor = loadFactor;    //初始化threshold大小    this.threshold = tableSizeFor(initialCapacity);}//这个方法将传进来的参数转变为2的n次方的数值static final int tableSizeFor(int cap) {    int n = cap - 1;    n |= n >>> 1;    n |= n >>> 2;    n |= n >>> 4;    n |= n >>> 8;    n |= n >>> 16;    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}public HashMap(Map<? extends K, ? extends V> m) {    //初始化填充因子    this.loadFactor = DEFAULT_LOAD_FACTOR;    //将m中的所有元素添加至HashMap中    putMapEntries(m, false);}//将m的所有元素存入该实例final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {    int s = m.size();    if (s > 0) {        //判断table是否已经初始化        if (table == null) { // pre-size            //未初始化,s为m的实际元素个数            float ft = ((float)s / loadFactor) + 1.0F;            int t = ((ft < (float)MAXIMUM_CAPACITY) ?                     (int)ft : MAXIMUM_CAPACITY);            //计算得到的t大于阈值,则初始化阈值            if (t > threshold)                threshold = tableSizeFor(t);        }        else if (s > threshold)            resize();        //将m中的所有元素添加至HashMap中        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {            K key = e.getKey();            V value = e.getValue();            putVal(hash(key), key, value, false, evict);        }    }}

2.4 核心方法

put()方法

先计算key的hash值,然后根据hash值搜索在table数组中的索引位置,如果table数组在该位置处有元素,则查找是否存在相同的key,若存在则覆盖原来key的value,否则将该元素保存在链表尾部,注意JDK1.7中采用的是头插法,即每次都将冲突的键值对放置在链表头,这样最初的那个键值对最终就会成为链尾,而JDK1.8中使用的是尾插法。此外,若table在该处没有元素,则直接保存。

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    //第一次put元素时,table数组为空,先调用resize生成一个指定容量的数组    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    //hash值和n-1的与运算结果为桶的位置,如果该位置空就直接放置一个Node    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    //如果计算出的bucket不空,即发生哈希冲突,就要进一步判断    else {        Node<K,V> e; K k;        //判断当前Node的key与要put的key是否相等        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        //判断当前Node是否是红黑树的节点        else if (p instanceof TreeNode)            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        //以上都不是,说明要new一个Node,加入到链表中        else {            for (int binCount = 0; ; ++binCount) {              //在链表尾部插入新节点,注意jdk1.8是在链表尾部插入新节点                if ((e = p.next) == null) {                    p.next = newNode(hash, key, value, null);                    // 如果当前链表中的元素大于树化的阈值,进行链表转树的操作                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                //在链表中继续判断是否已经存在完全相同的key                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        //走到这里,说明本次put是更新一个已存在的键值对的value        if (e != null) { // existing mapping for key            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;            //在hashMap中,afterNodeAccess方法体为空,交给子类去实现            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    //如果当前size超过临界值,就扩容。注意是先插入节点再扩容    if (++size > threshold)        resize();    //在hashMap中,afterNodeInsertion方法体为空,交给子类去实现    afterNodeInsertion(evict);    return null;}

resize() 数组扩容

用于初始化数组或数组扩容,每次扩容后,容量为原来的 2 倍,并进行数据迁移

final 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; // double threshold    }    else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后,第一次 put 的时候        newCap = oldThr;    else {// 对应使用 new HashMap() 初始化后,第一次 put 的时候        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; // 如果是初始化数组,到这里就结束了,返回 newTab 即可    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;                // 如果是红黑树,具体我们就不展开了                else if (e instanceof TreeNode)                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);                else {                     // 这块是处理链表的情况,                    // 需要将此链表拆成两个链表,放到新的数组中,并且保留原来的先后顺序                    // loHead、loTail 对应一条链表,hiHead、hiTail 对应另一条链表,代码还是比较简单的                    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;                        // 第二条链表的新的位置是 j + oldCap,这个很好理解                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    return newTab;}

get()过程

public V get(Object key) {    Node<K,V> e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}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;}

2.5 其他方法

HashSet是对HashMap的简单包装,其他还有迭代器等

3、总结

关于数组扩容,从putVal源代码中我们可以知道,当插入一个元素的时候size就加1,若size大于threshold的时候,就会进行扩容。假设我们的capacity大小为32,loadFator为0.75,则threshold为24 = 32 * 0.75,此时,插入了25个元素,并且插入的这25个元素都在同一个桶中,桶中的数据结构为红黑树,则还有31个桶是空的,也会进行扩容处理,其实此时,还有31个桶是空的,好像似乎不需要进行扩容处理,但是是需要扩容处理的,因为此时我们的capacity大小可能不适当。我们前面知道,扩容处理会遍历所有的元素,时间复杂度很高;前面我们还知道,经过一次扩容处理后,元素会更加均匀的分布在各个桶中,会提升访问效率。所以说尽量避免进行扩容处理,也就意味着,遍历元素所带来的坏处大于元素在桶中均匀分布所带来的好处。

另外LinkedHashMap是HashMap的直接子类,二者唯一的区别是LinkedHashMap在HashMap的基础上,采用双向链表(doubly-linked list)的形式将所有**entry**连接起来,这样是为保证元素的迭代顺序跟插入顺序相同

六、Collections工具类

1、概述

此类完全由在 collection 上进行操作或返回 collection 的静态方法组成。它包含在 collection 上操作的多态算法,即“包装器”,包装器返回由指定 collection 支持的新 collection,以及少数其他内容。如果为此类的方法所提供的 collection 或类对象为 null,则这些方法都将抛出NullPointerException

2、排序常用方法

//反转列表中元素的顺序static void reverse(List<?> list)//对List集合元素进行随机排序static void shuffle(List<?> list)//根据元素的自然顺序 对指定列表按升序进行排序static void sort(List<T> list)//根据指定比较器产生的顺序对指定列表进行排序static <T> void sort(List<T> list, Comparator<? super T> c)//在指定List的指定位置i,j处交换元素static void swap(List<?> list, int i, int j)//当distance为正数时,将List集合的后distance个元素“整体”移到前面;当distance为负数时,将list集合的前distance个元素“整体”移到后边。该方法不会改变集合的长度static void rotate(List<?> list, int distance)

3、查找、替换操作

//使用二分搜索法搜索指定列表,以获得指定对象在List集合中的索引//注意:此前必须保证List集合中的元素已经处于有序状态static <T> int binarySearch(List<? extends Comparable<? super T>>list, T key)//根据元素的自然顺序,返回给定collection 的最大元素static Object max(Collection coll)//根据指定比较器产生的顺序,返回给定 collection 的最大元素static Object max(Collection coll,Comparator comp)://根据元素的自然顺序,返回给定collection 的最小元素static Object min(Collection coll)://根据指定比较器产生的顺序,返回给定 collection 的最小元素static Object min(Collection coll,Comparator comp)://使用指定元素替换指定列表中的所有元素static <T> void fill(List<? super T> list,T obj)//返回指定co1lection中等于指定对象的出现次数static int frequency(collection<?>c,object o)//返回指定源列表中第一次出现指定目标列表的起始位置;如果没有出现这样的列表,则返回-1static int indexofsubList(List<?>source, List<?>target)//返回指定源列表中最后一次出现指定目标列表的起始位置;如果没有出现这样的列表,则返回-1static int lastIndexofsubList(List<?>source,List<?>target)//使用一个新值替换List对象的所有旧值o1dvalstatic <T> boolean replaceA1l(list<T> list,T oldval,T newval)

4、同步控制

Collectons提供了多个synchronizedXxx()方法,该方法可以将指定集合包装成线程同步的集合,从而解决多线程并发访问集合时的线程安全问题。正如前面介绍的HashSet,TreeSet,arrayList,LinkedList,HashMap,TreeMap都是线程不安全的。Collections提供了多个静态方法可以把他们包装成线程同步的集合。

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

5、Collection设置不可变集合

//返回一个空的、不可变的集合对象,此处的集合既可以是List,也可以是Set,还可以是Map。emptyXxx()//返回一个只包含指定对象(只有一个或一个元素)的不可变的集合对象,此处的集合可以是:List,Set,Map。singletonXxx()://返回指定集合对象的不可变视图,此处的集合可以是:List,Set,MapunmodifiableXxx()

感谢你能够认真阅读完这篇文章,希望小编分享的“Java集合框架是什么”这篇文章对大家有帮助,同时也希望大家多多支持编程网,关注编程网行业资讯频道,更多相关知识等着你来学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯