1.List/Map/Set(Java 8)

发布于 2022年 01月 11日 00:12

1.List系列


ArrayList 

初始容量10,扩容策略为size * 1.5,线程不安全,底层结构为动态数组,for循环遍历效率高,修改,查找速度快。

LinkedList 

初始容量0, 无需扩容,线程不安全,底层数据结构为链表,使用Iterator遍历效率高,插入删除效率高。实现了Deque接口,所以是双向链表。

Vector 

初始容量10,扩容策略为size * 1.5,线程安全,数组结构。基本等同ArrayList,使用Synchorized 进行同步,保证线程安全。

CopyOnWriteArrayList

以CopyOnWrite为框架实现的一个 写入线程安全的List容器,本身维护一个Object数组(因为每次修改都会重新修改容量,所以初始容量为0),每次增删改都复制出一个新的数组容器,组装完成后再将之前的数组重新定向到新容器中,add(),set(),remove(),方法皆是如此,使用ReentrantLock(重入锁), 写操作线程安全,get()方法,是拿的旧指向的Object[]对象。CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性。不推荐使用。优缺点:写操作性能较差,而多线程的读操作性能较好,在大数据量时写占用大量内存。

Collections.synchronizedList(ArrayList)

将线程不安全的list 转变为线程安全的list,实现原理是在对list 的操作上加上Synchorized代码块(SynchronizedRandomAccessList<>(list) ,SynchronizedList<>(list)))。

区别List是否数组和链表的方法可以用

 List instanceof RandomAccess

RandomAccess接口是标致性接口, 与Serializable一样作为标志使用。

实现RandomAccess接口为数组(因为支持随机访问),否则为链表,数组 for 遍历快,链表  Iterator 快.

2.Map系列

HashMap 

默认容量16,每次扩容 2*N,扩容时需要重新计算hash,浪费容量,所以初始化的时候要设计好容量,减少或者避免resize()出现。初始数据结构是桶(数组)+链表的结构,当桶中元素数量达到一定条件时则变为桶(数组)+红黑树结构(总元素个数>= 64, 桶内元素阈值>=8-1个的时候 链表 -> 红黑树),桶中元素减少时,也会由红黑树转为链表结构(桶内元素阈值<=6 红黑树 -> 链表),其中 桶 是通过 key 的散列获得的,计算方法为 hash&(table.length-1)。线程不安全,允许KV都为null,使用 Iterator 迭代.

HashMap使用key的hashCode()和equals()方法来将值划分到不同的桶里,如果自定义对象重写了hashcode 但没有重写equals 也不会判定是同一个对象,遵守规范编码就不会出问题。

LinkedHashMap

继承HashMap,维护了一个双向链表,保证顺序。

HashTable 

初始容量11,使用 synchronized 做同步设置,线程安全,不推荐使用。Enumeration 遍历。

TreeMap

本质上就是一个红黑树结构;该映射根据其Key的自然顺序进行排序(升序),或者根据创建映射时提供Comparator 进行排序,具体取决于使用的构造方法。线程不安全,使用 Iterator 的fail-fast迭代器迭代.实现了NavigableMap接口,支持一系列的导航方法。比如返回有序的key集合,firstKey()、lastKey()、lowerKey()、higherKey()等。通过Iterator迭代器遍历。

WeakHashMap

弱键HashMap,Entry继承WeakReference。当key被gc回收后,也会清除Map中的key。线程不安全,Iterator迭代器遍历。

expungeStaleEntries()清除弱引用key。当gc回收弱引用key后,会添加到ReferenceQueue队列中,每次size(),getTable()方法调用时,都会遍历队列中的弱引用key。

public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
      testWeakHashMapAPIs();
    Map weakHashMap = new WeakHashMap();
    String a = new String("1");
    String b = new String("2");
    weakHashMap.put(a, "aa");
    weakHashMap.put(b, "bb");

    a = null;
    System.gc();

    Iterator iter = weakHashMap.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry en = (Map.Entry)iter.next();
        System.out.printf("next : %s - %s\n",en.getKey(),en.getValue());
    }
    // 打印WeakHashMap的实际大小
    System.out.printf(" after gc WeakHashMap size:%s\n", weakHashMap.size());
}

打印:
next : 2 - bb
after gc WeakHashMap size:1

IdentityHashMap

默认大小32,最小4,put达到数组长度的1/3的时候扩容,用数组维护KV,(索引处存的全是元素的key,而奇数位置存的是元素的value),通常的Hashmap通过hashcode 和 equals 判断是否为同一个对象,而IdentityHashMap只判断==是否为同一个对象。key和value都为null。线程不安全。很有意思的一个HashMap,全都没用按照HashMap 的规范做。

hash:

private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

put():

tab[i] = k;
tab[i + 1] = value;

ConcurrentHashMap 

1.7使用分段锁设计,1.8取消分段锁,改用Unsafe类的CAS进行写操作,读操作和size()弱一致,未加锁。是线程安全的HashMap。

Collections.synchronizedMap(Map)

将线程不安全的Map 转变为线程安全的Map

3.Set

HashSet

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

LinkedHashSet

继承HashSet。。里面竟然包含一个私有的构造LinkedHashMap。。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

TreeSet

public TreeSet() {
    this(new TreeMap<E,Object>());
}


总结下。。Set是Map生下来的。。Set是没有Value 的Map


推荐文章