• 35648

    文章

  • 23

    评论

  • 20

    友链

  • 最近新加了很多技术文章,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

【一文系列】一文了解java常用集合类(含源码)

欢迎来到阿八个人博客网站。本 阿八个人博客 网站提供最新的站长新闻,各种互联网资讯。 喜欢本站的朋友可以收藏本站,或者加QQ:我们大家一起来交流技术! URL链接:https://www.abboke.com/jsh/2019/0731/103055.html 1190000019930041

一、List

1、ArrayList

① 关键源码

// 默认初始化为空数组
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 添加元素
public boolean add(E e) {
    // 增加modCount, 判断扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 扩容函数
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新的容量等于旧容量的1.5倍,使用位移更高效
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);
}

② 特点

  1. 空集合第一次添加元素时默认初始容量为10
  2. 线程不安全(在单线程中才使用ArrayList,而在多线程中可以选择Vector[方法加了sync关键字]或者CopyOnWriteArrayList[juc包])
  3. 遍历时,使用随机访问(即,通过索引序号访问)效率最高,而使用迭代器的效率最低
  4. fail-fast 机制

    • fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。
    • AbstractList 源码中,每修改一次(添加/删除等操作),将modCount+1
      由于 实现的 Itr 类中, next() 和 remove()都会执行 checkForComodification()
      若 “modCount 不等于expectedModCount”,则抛出ConcurrentModificationException异常,产生fail-fast事件。
      所以当多个线程同时操作时,会抛出ConcurrentModificationException异常

2、LinkedList

① 关键源码

// 初始化空列表
public LinkedList() {
}

// 在列表末尾添加一个节点
public boolean add(E e) {
    linkLast(e);
    return true;
}

// linkLast函数
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        // last为空说明是个空列表,插入的则为第一个节点
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// Node类
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;
    }
}

② 特点

  1. LinkedList的本质是双向链表
  2. LinkedList包含两个重要的成员:Node<E> 和 size
  3. Node是双向链表节点所对应的类的实例。Node中包含成员变量: prev, next, item
  4. prev是该节点的上一个节点,next是该节点的下一个节点,item是该节点所包含的值。size是双向链表中节点的个数。

3、LinkedList和ArrayList使用场景和性能分析

1、ArrayList 是一个数组队列,相当于动态数组。它由数组实现,随机访问效率高,随机插入、随机删除效率低(涉及到复制)。
2、LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低,但随机插入、随机删除效率高。

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

二、Map

1、HashMap

① 关键源码

// 加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 初始的加载因子默认为0.75,此时还没有初始化容量,在put的时候会进行resize()将容量初始化为16
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
* key 的 hash值的计算是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16)
* 这么做可以在数组table的length比较小的时候
* 也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 重点的putVal逻辑
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为null或者0,则进行resize()操作  resize()方法在下面再说
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 确定插入table的位置,算法是(n - 1) & hash,在n为2的幂时,相当于除模取余操作。(这也是为什么长度要取2的幂次方的原因之一)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
        
    // 在table的i位置发生hash碰撞或者除模取余后相同结果,有两种情况:
    // 1、key值是一样的,就替换成value值
    // 2、key值不一样的有两种处理方式:a、存储在i位置的链表(链表长度达到8时转成红黑树); b、存储在红黑树中
    else {
        Node<K,V> e; K k;
        // key值是一样的,替换value值
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 是红黑树结构就putTreeVal
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 不是TreeNode,即为链表,遍历链表并且去跟链表的每一个key做比较
            for (int binCount = 0; ; ++binCount) {
                // 直到链表的下一个节点为null,就进去新建个节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 根据binCount去记录链表的长度,超过8就转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node<K,V>[] resize() {
    // 保存当前table
    Node<K,V>[] oldTab = table;
    // 保存当前table的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存当前阈值
    int oldThr = threshold;
    // 初始化新的table容量和阈值 
    int newCap, newThr = 0;
    /*
      1. resize()函数在size > threshold时被调用。oldCap大于 0 代表原来的 table 表非空,
      oldCap 为原表的大小,oldThr(threshold) 为 oldCap × load_factor
   */
    if (oldCap > 0) {
        // 若旧table容量已超过最大容量,更新阈值为Integer.MAX_VALUE(最大整形值),这样以后就不会自动扩容了。
        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
    }
    /*
       2. resize()函数在table为空被调用。oldCap 小于等于 0 且 oldThr 大于0,代表用户创建了一个 HashMap,但是使用的构造函数为      
       HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
       或 HashMap(Map<? extends K, ? extends V> m),导致 oldTab 为 null,oldCap 为0, oldThr 为用户指定的 HashMap的初始容量。
    */
    else if (oldThr > 0) // initial capacity was placed in threshold
        //当table没初始化时,threshold持有初始容量。还记得threshold = tableSizeFor(t)么;
        newCap = oldThr;
    /*
        3. resize()函数在table为空被调用。oldCap 小于等于 0 且 oldThr 等于0,用户调用 HashMap()构造函数创建的 HashMap,所有值均采用默认值,oldTab(Table)表为空,oldCap为0,oldThr等于0,
    */
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新阈值为0
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 初始化table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把 oldTab 中的节点 reHash 到 newTab 中去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 若节点是单个节点,直接在 newTab 中进行重定位
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 若节点是 TreeNode 节点,要进行 红黑树的 rehash 操作
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 若是链表,进行链表的 rehash 操作
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割(代码后有图解,可以回过头再来看),分成两个不同的链表,完成rehash
                    do {
                        next = e.next;
                        // 根据算法 e.hash & oldCap 判断节点位置rehash 后是否发生改变
                        // 最高位==0,这是索引不变的链表。
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //最高位==1 (这是索引发生改变的链表)
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原bucket位置的尾指针不为空(即还有node)
                    if (loTail != null) {
                        // 链表最后得有个null
                        loTail.next = null;
                        // 链表头指针放在新桶的相同下标(j)处
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // rehash 后节点新的位置一定为原来基础上加上 oldCap,具体解释看下图
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

② 特点

  1. HashMap 的实现不是线程安全的。它的key、value都可以为null
  2. 初始化时加载因子为0.75,有put操作时将容量初始化为16(哈希表的桶数,即entry的数量)
  3. 当哈希表中的条目数超出了加载因子与容量的乘积时(如0.75 * 16),则要对该哈希表进行resize操作(同时会进行rehash操作,重建内部数据结构),从而哈希表将具有两倍的容量。
  4. HashMap是通过拉链法实现的散列表。本质上是数组 + 单向链表 + 红黑树的数据结构(如下图)。
  5. HashMap使用链表法避免哈希冲突(相同hash值),当链表长度大于TREEIFY_THRESHOLD(默认为8,设为8是因为达到8的概率为0.00000006,概率低)时,将链表转换为红黑树(在转红黑树之前会再进行一次判断map的容量是否小于64,是的话不会进行转红黑树,而是先resize()扩容),如果之后小于UNTREEIFY_THRESHOLD(默认为6)时,又会转回链表以达到性能均衡。


图1 HashMap的数据结构

2、LinkedHashMap

① 关键源码

// LinkedHashMap继承了HashMap,实现Map接口
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

// 初始化是默认容量16,加载因子0.75.并且设定了 accessOrder = false,表示默认按照插入顺序进行遍历
public LinkedHashMap() {
    super();
    accessOrder = false;
}

② 特点

  1. LinkedHashMap 是基于 HashMap 实现的一种集合,具有 HashMap 集合上面所说的所有特点
  2. 除了 HashMap 无序的特点,LinkedHashMap 是有序的
  3. LinkedHashMap 在 HashMap 的基础上单独维护了一个具有所有数据的双向链表,该链表保证了元素迭代的顺序
  4. 数据结构图

三、Set

1、HashSet

① 关键源码

// HashSet 实现了 Cloneable 接口和 Serializable 接口,分别用来支持克隆以及支持序列化。还实现了 Set 接口,该接口定义了 Set 集合类型的一套规范
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
    
// HashSet集合中的内容是通过 HashMap 数据结构来存储的
private transient HashMap<E,Object> map;
// 向HashSet中添加数据,数据在上面的 map 结构是作为 key 存在的,而value统一都是 PRESENT
private static final Object PRESENT = new Object();

// 初始化时就是new一个HashMap
public HashSet() {
    map = new HashMap<>();
}

// 将 e 作为 key,PRESENT 作为 value 插入到 map 集合中,如果 e 不存在,则插入成功返回 true;如果存在,则返回false
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

② 特点

  1. HashSet 是一个没有重复元素的集合。
  2. 它是由HashMap实现的,不保证元素的顺序,而且HashSet允许使用 null 元素。

相关文章

暂住......别动,不想说点什么吗?
  • 全部评论(0
    还没有评论,快来抢沙发吧!