1.1. JAVA容器

包括collection和Map

1.2. ArrayList:

  • 添加操作是O(n)复杂度,其余是O(1)复杂度。
  • 有容量,最小是链表的大小。当添加新的元素时,使用ensureCapacity,确保容量大小。
  • 不是线程安全的。

1.3. Conllection容器

1.3.1. 集合框架

Collection接口是所有集合的根,扩展出三大类集合,分别为List、Set和Queue/Deque

  • List:有序集合,方便访问、插入、排序
  • Set:不允许重复元素。
  • Queue/Deque:标准的队列结构,支持先入先出和后入后出。

1.3.2. 对比Vector、ArrayList、LinkedList的区别?

相同点:都是实现集合框架List,也就是所谓的有序集合,都提供了定位、添加、删除和迭代器遍历操作。

不同点:

线程安全 自动扩容 使用场景
Vector 安全 每次扩容1倍 随机访问场景
ArrayList 不安全 每次扩容0.5倍 随机访问场景
LinkedList 不安全 不需要 对插入、删除有性能要求

1.3.3. 默认排序算法

  • 原始数据类型:双周快速排序,是一种改进的快速排序
  • 对象数据类型:TimeSort,是一种结合归并与二分插入的排序算法。

1.3.4. ArrayList与LinkedList

1.3.5. hashMap原理

1.3.6. HashTable与concurrentHashMap区别


1.4. Map集合

1.4.1. 对比Hashtable、HashMap、TreeMap的区别

  • 共同点:都是常见的Map实现,以键值对形式存储和操作数据的容器类型。
  • 不同点:
    • Hashtable:线程同步的、不支持null键和值。
    • HashMap:不是同步的、支持null键和值。
    • TreeMap:基于共黑叔的一种顺序访问店Map,get、put和remove方法都是log(n)的复杂度。

1.4.2. Map整体结构

1.4.3. HashMap源码分析

  • 数组被分为一个个桶(bucket),通过hash值确定键值对在数组的寻址
  • hash值相同的键值对,则以链表形式存储。

  • 负载因子*容量>元素数量
  • 对链表进行树化改造,避免同样hash值中很长的链表造成的CPU开销。

1.4.4. map如何遍历


1.5. 集合线程安全

1.5.1. 如何保证容器是线程安全?ConcurrentHashMap如何实现高效线程安全?

Java提供了不同层面的线程安全支持。

  • 在传统集合框架内部,除了Hashtable等同步容器,还提供了所谓的同步包装器,我们可以调用Collections工具类提供的包装方法,来获取一个同步的包装容器,但是这些都是利用非常粗粒度的同步方式,在高并发情况下,性能比较低。
  • 利用并发包提供的线程安全:
    • 各类并发容器:ConcurrentHashMap、CopyOnWriteArrayList
    • 各类线程安全队列:ArrayBlockingQueue、SynchronousQueue
    • 各种有序容器的线程安全。

1.5.2. 为什么需要ConcurrentHashMap

HashTable本身比较低效,因为他的put、get、size操作都是加了“synchronized”,大大降低了并发操作效率。

1.5.3. ConcurrentHashMap分析

早期是基于:

  • 分离锁:将内部进行分段,里面是HashEntry的数组(Hash值相同的数据,以链表形式存储)
  • HashEntry内部使用volatile的value字段来保证可见性。

results matching ""

    No results matching ""