Java 集合

简介: java集合fail-fast机制在java集合类中,使用modCount来检查数组的状态.当在迭代集合的时候,(通常会实现 iterator()方法来获取迭代对象,或者 foreach),集合里面的数据,在其他地方被修改了,这个时候 modCount就会被修改,与迭代过程的modCount不一致.
img_a74d00b5f19c2ad3616c1d04e7a6b20e.png
java集合

fail-fast机制

在java集合类中,使用modCount来检查数组的状态.
当在迭代集合的时候,(通常会实现 iterator()方法来获取迭代对象,或者 foreach),
集合里面的数据,在其他地方被修改了,这个时候 modCount就会被修改,与迭代过程的modCount不一致.将抛出ConcurrentModificationException异常,这个过程就叫 fail-fast

List 篇

主要介绍 ArrayList,VectorLinkedList,CopyOnWriteArrayList


ArrayList

是一个数组长度可自增长的线程不安全的列表.内部使用数组实现. Object[] elementData.

  1. 默认的长度为 10.
  2. fail-fast
  3. 自动扩容(每次扩容为原来的1.5倍)
  4. 线程不安全
  5. 使用连续控件存储
  6. 继承自 List,RandomAccess等.
  7. 允许添加 null

时间复杂度 :

根据索引查询,复杂度为 O(1).
根据元素查询,复杂度为 O(N).
插入和删除,如果在列首复杂度为 O(N);在列尾复杂度为 O(1);平均复杂为 O(N)

插入和删除非列尾数据, 将会导致数组移动数据.

RandomAccess 接口

RandomAccess 是一个标记接口(没有任何方法).
如果实现了 RandomAccess 接口,表示该集合可以进行随机快速访问(通常底层是 数组形式的集合),如 ArrayList.
可以快速访问的集合,使用

for (int i=0, n<size; i++)
    list.get(i);

未实现 RandomAccess接口的集合,如LinkedList,使用迭代器效率更高.

for (Iterator i=list.iterator(); i.hasNext(); )
    i.next();

使用 instanceof RandomAccess来判断是否 支持随机快速访问.

Vector

是一个数组长度可自增长的线程安全的列表,内部使用数组实现.

  1. 默认的长度为 10.
  2. fail-fast
  3. 自动扩容(可设置每次扩容的增量值,默认扩容为原来的2倍.)
  4. 线程安全(synchronized)
  5. 使用连续控件存储
  6. 继承自 RandomAccess,List
  7. 允许添加 null

线程安全的vector,照样可以触发 fail-fast.
时间复杂度与 arraylist 一样.

在不涉及线程安全的前提下,arraylist效率更高.

fun main(args: Array<String>) {
    val vector = Vector(listOf(1, 2, 3, 4, 5))

    singleThread(vector)
    multiThread(vector)
    multiThreadSynchronized(vector)
}

/**
 * 单线程下,迭代抛出 ConcurrentModificationException
 */
fun singleThread(vector: Vector<Int>) {
    val it = vector.iterator()
    while (it.hasNext()) {
        println(it.next())
        vector.add(1)
    }
}

/**
 * 多线程下,迭代抛出 ConcurrentModificationException
 */
fun multiThread(vector: Vector<Int>) {
    thread {
        repeat(10000) {
            vector.add(it)
        }
    }

    thread {
        vector.forEach { println(it) }
    }
}

/**
 * 多线程下,修改vector是添加同步锁,避免同时迭代同时修改
 */
fun multiThreadSynchronized(vector: Vector<Int>) {
    thread {
        synchronized(vector) {
            repeat(10000) {
                vector.add(it)
            }
        }
    }

    thread {
        vector.forEach { println(it) }
    }
}

Stack

继承自 vector,线程安全,栈结构,先进后出.

LinkedList

是以双向链表方式实现的非线程安全的集合.

  1. 一个元素节点包含 上一个节点和下一个节点的引用,以及自身的值.
  2. 内存空间可不连续
  3. 线程不安全
  4. fail-fast
  5. 继承自 List,Deque等.
  6. 允许添加 null

时间复杂度:

删除和插入元素,复杂度为 O(1).
查询时,由于采用双向链表,判断离哪头近,从哪头开始找.
最糟糕的情况是O(N/2),所以它的复杂度为 O(N).

CopyOnWriteArrayList

CopyOnWriteArrayList是并发包中的实现.使用 ReenterLockSystem.arraycopy来实现数组读写的线程安全.

在读取的时不加锁,所以可以支持多线程同时读取数据,并且同时读取数不受限制.

在写入(add,set,remove等操作)的时候,使用 ReenterLock锁住方法,然后操作数据时先将原数组拷贝一份,对拷贝数据进行操作,操作完后将拷贝的原来的数据引用指向拷贝的数组引用,实现数据的更新操作,更新完后释放锁. 和其名字操作一致(写时拷贝).

没有设置初始长度的方法和扩容的策略. 因为该数组在每次 添加数据是, 都会使用 System.arraycopy拷贝一份比当前数据 +1 的数组.

    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;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

ArrayList,Vector和LinkedList的区别

ArrayListVector内部都是使用数组实现的.它们的主要区别在于

  1. ArrayList 是线程不安全的,Vector是线程安全的.
  2. ArrayList 自动扩容时固定增长为原来的1.5倍,不可指定增量值. Vector可指定每次的增量值,如果没指定,则扩容为原来的2倍.

在不考虑线程安全的情况下,优先使用 ArrayList,如果在使用前,能够预估大概有元素,创建时指定个数,效果更好.

LinkedList 使用双向链表实现,也是线程不安全的.与ArrayList的区别在于

  1. 实现方式不同.ArrayList使用数组,Vector使用双向链表.
  2. 内存空间管理不同,LinkedList可以是不连续的空间,ArrayList需要连续的内存空间.
  3. LinkedList 在删除和插入上的性能较好, ArrayList在查询上的效率更好.
  4. ArrayList 一个item只存自己的值,比较省空间, LinkedList一个item除了自己的值,还需要存放上一个和下一个元素的引用,比较费空间.

如果主要需要对列表进行遍历,以及增删操作,使用LinkedList其他情况使用ArrayList.

如果需要用到线程安全的列表,请使用 CopyOnWriteArrayList

Map篇

Map 是以键值对形式存储的集合.

主要介绍 HashMap,TreeMapHashtable,ConcurrentHashMap


HashMap

HashMap 内部混合使用数组,链表,红黑树的结构来构建的键值对集合.

HashMap的本质基础是基于数组的. 数组的各个元素,使用单向链表的结构.(Node(int hash, K key, V value, Node<K,V> next)).

HashMap通过哈希函数(hash())来完成keyindex的映射.

当出现hash后index冲突(index位置已经存在不同的key的键值对)时,数据将在index位置,使用单向链表或红黑树(当链表长度大于等8个时,链表中的所有元素改用红黑树存放)来存放元素.

当使用掉的索引 占用了 数组长度的一定比例时(填装因子),HashMap将进行扩容(扩容为原来的两倍,key与index重新映射).

HashMap的性能瓶颈:

  1. 优良的 哈希函数.

理想的状态是,每一个键值对的存放,能够比较均匀适当的分布在数组的索引上,尽量避免过多的hash值冲突.

    // java 8 中的实现
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
// index = (n - 1) & hash , 2的次方来说就是取余操作.
// 由于 (n -1)的二进制 高位都是0,地位都是1.
// hashcode 与 它进行 & 操作的话, hashcode的高位变化低位不变,则计算出来的index值讲不变.
// 为了消除高位变化 不影响 index 的值, 于是将 hashcode 的 高16位 移动到低16位,再和 hashcode进行 ^ 操作.
// 这样高位的变化,也能影响index值, 降低了冲突的概率.
  1. 填装因子

过低的填装因子,如填装因子=0.5,容量剩余一半的时候就扩容,可能导致空间上的浪费.
过高的填装因子,可能导致为了命中未使用的索引,而频繁出现 冲突.
HashMap实现中,填装因子默认使用 0.75的值.

特点 :

  1. 默认的长度为 16,默认填装因子为 0.75.
  2. fail-fast
  3. 自动扩容(默认扩容为原来的2倍.)
  4. 线程不安全
  5. 混合使用数组,链表和红黑树
  6. 继承自Map
  7. keyvalue都可以添加 null
  8. 插入和遍历顺序不一致

时间复杂度 :

查询,插入和删除操作的平均时间复杂度为 O(1).
极端情况下(全部发生冲突),若长度小于8,使用单项链表,复杂度为 O(n),如果长度大于等于8,使用红黑树,复杂度为O(logn)

LinkedHashMap

继承自 HashMap, 底层使用哈希表与双向链表来保存元素,与HashMap的差异就在于 访问顺序上.
构造中,accessOrder 默认为 false,代表按照插入顺序进行迭代;为 true,代表以访问顺序进行迭代(最常访问的在前,最不经常访问的在后LRU)。

TreeMap

TreeMap内部使用 红黑树来实现的键值对集合.与HashMap相比,TreeMap是一个能比较元素大小的Map集合,会对传入的key进行了大小排序。其中,可以使用元素的自然顺序,也可以使用集合中自定义的比较器来进行排序.

特点 :

  1. fail-fast
  2. 线程不安全
  3. 使用红黑树实现
  4. keyvalue都可以添加 null
  5. 插入和遍历顺序不一致
  6. 支持对key排序
  7. 继承自NavigableMap,拥有强大的搜索功能.

时间复杂度 :

红黑树是自平衡的二叉搜索树, 查询,添加删除 效率都是 O(logn).

HashTable

HashTable 内部使用数组和单项链表实现的键值对集合.

HashTable的哈希函数 (hash & 0x7FFFFFFF) % tab.length,只是对key的hashcod进行取整和取余操作.

HashTable默认的初始大小为11,之后每次扩充为原来的2n+1。
也就是说,HashTable的链表数组的默认大小是一个素数、奇数。之后的每次扩充结果也都是奇数。
由于HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时,简单的取模哈希的结果会更加均匀。(这个是可以证明出来 的,可参考:http://zhaox.github.io/algorithm/2015/06/29/hash

特点 :

  1. 默认的长度为 11,默认填装因子为 0.75.
  2. fail-fast
  3. 自动扩容(扩容为原来的2n+1)
  4. 线程安全
  5. 混合使用数组,链表
  6. 继承自Map
  7. keyvalue都不能使用null值,否则抛出空指针异常.
  8. 插入和遍历顺序不一致

时间复杂度 :

HashMap一致

ConcurrentHashMap (java.util.concurrent)

HashMap一样,是内部使用数组,链表,红黑树的结构来构建的键值对集合,因为需要保证线程安全,所以内部实现更加复杂.

哈希函数 (h ^ (h >>> 16)) & HASH_BITS , 和HashMap类似,与高位进行异或操作的方式,来消除高位数据变化导致索引不变的情况,多加了一步正数的操作.

当冲突的链表中个数超过8个, 如果数组长度小于64,则扩容,否则,将链表数据转化为 红黑树结构存储.

ConcurrentHashMap 采用 CAS(Compare and Swap)原子类型操作,来保证线程的安全性. 较 jdk1.7 的分段锁机制性能更好.

特点 :

  1. 默认长度为16,无默认的装填因子

构造函数为 : ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)
没有默认的装填因子,传入 初始容量和装填因子后,会被算法调整为 2次方,最小容量为 16.
并发级别,表示 可以同时对数据进行写操作的线程数, 最大可达16. 读取不受限制.

  1. 没有 fail-fast, 将保证线程安全.
  2. 自动扩容为原来的 2 倍.
  3. 线程安全
  4. 混合使用数组,链表和红黑树
  5. 继承自ConcurrentMap
  6. keyvalue可以添加 null
  7. 插入和遍历顺序不一致

时间复杂度 :

HashMap一致

HashMapHashTable , ConcurrentHashMap对比

HashMap 线程不安全 , HashTable线程安全,但还是存在fail-fast问题 , ConcurrentHashMap线程安全,不存在fail-fast问题.

HashMapConcurrentHashMap 内部都是用 数组,链表 加红黑树来构建.(较高效) HashTable 使用数组加链表.

HashMapConcurrentHashMap 都是用 高位异或的哈希算法. HashTable 采用 数组长度为素数,直接取余的哈希算法.

HashMap 允许插入 null键值对, HashTable , ConcurrentHashMap 不允许.

结论 : 不考虑线程安全的情况下使用 HashMap, 线程安全则使用 ConcurrentHashMap.
如果知道 大概会存多少数据,指定 初始容量 会更高效, 避免扩容和重新hash映射产生的效率问题.

Set篇

Set 是没有重复元素的单元素集合.

TreeSet 内部使用 TreeMap实现.

HashSet 内部使用 HashMap实现. 当构造参数为三个时 LinkedHashMap实现.

LinkedHashSet 继承自 HashSet,但是都是调用 HashSet中有三个构造参数的LinkedHashMap来实现.

目录
相关文章
|
2月前
|
消息中间件 算法 安全
JUC并发—1.Java集合包底层源码剖析
本文主要对JDK中的集合包源码进行了剖析。
|
8天前
|
存储 安全 算法
Java 集合面试题 PDF 下载及高频考点解析
本文围绕Java集合面试题展开,详细解析了集合框架的基本概念、常见集合类的特点与应用场景。内容涵盖`ArrayList`与`LinkedList`的区别、`HashSet`与`TreeSet`的对比、`HashMap`与`ConcurrentHashMap`的线程安全性分析等。通过技术方案与应用实例,帮助读者深入理解集合类的特性和使用场景,提升解决实际开发问题的能力。文末附带资源链接,供进一步学习参考。
20 4
|
11天前
|
存储 安全 Java
现代应用场景中 Java 集合框架的核心技术与实践要点
本内容聚焦Java 17及最新技术趋势,通过实例解析Java集合框架的高级用法与性能优化。涵盖Record类简化数据模型、集合工厂方法创建不可变集合、HashMap初始容量调优、ConcurrentHashMap高效并发处理、Stream API复杂数据操作与并行流、TreeMap自定义排序等核心知识点。同时引入JMH微基准测试与VisualVM工具分析性能,总结现代集合框架最佳实践,如泛型使用、合适集合类型选择及线程安全策略。结合实际案例,助你深入掌握Java集合框架的高效应用与优化技巧。
36 4
|
11天前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
67 3
|
6月前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
109 3
|
2月前
|
Java
Java LinkedList集合的深度剖析
总的来说,我希望像说故事一样讲解Java LinkedList集合的使用和实现原理,让有些许枯燥的编程知识变得趣味盎然。在这个“公交车”故事中,你不仅熟悉了LinkedList集合的实现和使用,而且还更深入地理解了数据结构中的链表。链表可能会因为插入和删除的便利性而被选用,虽然它的查找效率并不高,但是在很多场景中仍然十分有效。这就像公交车,虽然它速度不快,但却是城市出行的重要工具。
65 8
|
8月前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
97 3
|
2月前
|
存储 安全 Java
Java 集合框架详解:系统化分析与高级应用
本文深入解析Java集合框架,涵盖List、Set、Map等核心接口及其常见实现类,如ArrayList、HashSet、HashMap等。通过对比不同集合类型的特性与应用场景,帮助开发者选择最优方案。同时介绍Iterator迭代机制、Collections工具类及Stream API等高级功能,提升代码效率与可维护性。适合初学者与进阶开发者系统学习与实践。
75 0
|
3月前
|
Java
java常见的集合类有哪些
Map接口和Collection接口是所有集合框架的父接口: 1. Collection接口的子接口包括:Set接口和List接口 2. Map接口的实现类主要有:HashMap、TreeMap、Hashtable、ConcurrentHashMap以及 Properties等 3. Set接口的实现类主要有:HashSet、TreeSet、LinkedHashSet等 4. List接口的实现类主要有:ArrayList、LinkedList、Stack以及Vector等
|
6月前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
111 5