Java集合框架源码研读后笔记

Spring Wu 391 2021-02-03

Collection

Collection是Java的一个集合容器抽象。这里面分为三种类型的集合容器:List、Set、Queue,其中List主要是提供类似数组一样的数据结构。Set提供不重复数据的数据结构。Queue提供队列来存储数据的方式。

List

  • ArrayList: 基于动态数组实现,保证添加数据的顺序。可以随机访问。

  • Vector:实现与ArrayList差不多,但是是线程安全的。每个方法都直接使用synchronized修饰。现在基本不用。

  • LinkedList:双向链表结构,数据是有序的,访问时可从链表头部开始访问,也可从尾部开始访问。主要看要获取的数据是偏链表头部还是链表尾部。偏向通过size >> 1也就是链表的大小size / 2来判断,如果index < (size >> 1)从头部开始迭代访问,反之从尾部开始访问。可用作于栈、队列和双向队列。

Set

  • HashSet:底层基于HashMap实现,数据是无序的,数据不可重复。查找速度很快,因为HashMap底层根据key的hash值来定位数据位置。

  • TreeSet:继承于SortedSet,保证数据的自然排序,不保证插入顺序,基于TreeMap实现。TreeMap底层基于红黑树实现。查找速度比HashSet慢。

  • LinkedHashSet:继承于HashSet,本类只有几个构造器,构造器都基于super HashSet,而HashSet中提供的有几个构造器是基于LinkedHashMap的。所以LinkedHashSet拥有LinkedHashMap的双向链表特性。而且查找也通过hash来查找,具有与HashSet的查找速度。

Queue

  • LinkedList:LinkedList保证数据的插入顺序,可从头部和尾部访问数据。

  • PriorityQueue:优先队列,使用二叉树最小堆顶结构实现。

Map

Map以key,value的格式存储数据。

  • HashMap:可存放null key, 1.7以前基于数组+单向链表+hash实现,1.8以后基于数组+单向链表+红黑树+hash实现。查找速度很快。只需通过计算key的hash,即可得到数据的位置。

  • TreeMap:不可存放null key,基于红黑树实现,查找速度比HashMap慢,因为要通过与Entry节点的数据做对比,当迭代到key值一样时,才能找出数据。

  • Hashtable:不可存放null key, 基于hash+单向链表实现,线程安全的map。相关方法都使用了synchronized修饰。现在基本不用,如果要使用线程安全的map一般使用JUC的ConcurrentHashMap。

  • LinkedHashMap:LinkedHashMap基于HashMap实现,是一个双向链表结构的HashMap。