java集合底层实现

1. 数组（Array）

  • 结构说明：在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。
  • 结构特点：可以随机访问，插入和删除效率低、内存固定。
  • Java集合：ArrayList、Vector

2. 链表（Linked List）

  • 结构说明：是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
  • 结构特点：插入和删除效率高、查找效率低。
  • Java集合：LinkedList、LinkedHashMap（链表+哈希表）、LinkedHashSet（链表+哈希表）

3. 哈希表（Hash）

  • 结构说明：若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。
  • 结构特点：查找效率高，插入和删除较快，内存固定，存在散列冲突。
  • Java集合：HashMap、HashSet、HashTable、LinkedHashMap（链表+哈希表）、LinkedHashSet（链表+哈希表）

4. 堆（Heap）

  • 结构说明：在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。
  • 结构特点：插入、删除较快，对最大项、最小项存取快，其他项存取较慢。
  • Java集合：PriorityQueue（二叉堆实现的优先队列）

5. 栈（Stack）

  • 结构说明：只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。
  • 结构特点：先进后出（First In Last Out）。
  • Java集合：Stack

6. 队列（Queue）

  • 结构说明：一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
  • 结构特点：先进先出（First In First Out）。
  • Java集合：ArrayDeque（双端队列）、LinkedList（双端队列）

7. 树（Tree）

  • 结构说明：它是由n（n>=1）个有限节点组成一个具有层次关系的集合。 （1）每个元素称为结点（node）。 （2）有一个特定的结点被称为根结点或树根（root）。 （3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
  • 结构特点：查询、插入、删除都比较快，但是算法复杂。
  • Java集合：TreeMap（红黑树）、TreeSet（红黑树）

java集合框架示例

一、List：

有顺序以线性方式存储,可以存放重复对象

线程安全方法：List list = Collections.synchronizedList(new LinkedList(…));

  • LinkedList：双向链表实现存储 索引数据慢插入数度较快 线程不安全（比安全性能好）
  • ArrayList:数组方式存储数据 索引数据快插入数据慢 线程不安全
  • Vector:数组方式存储数据 索引数据快插入数据慢 线程安全
  • Stack：继承自Vector，实现一个后进先出的堆栈

二、Set：

无顺序,不包含重复的元素

  • HashSet：为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。
  • TreeSet： 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。
  • LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

三、Map：

键必须是唯一

同步方法：Map m = Collections.synchronizedMap(new TreeMap(…));

  • Hashtable:基于散列表的实现 允许空键空值 线程安全
  • HashMap:基于散列表的实现 允许空键空值 线程不安全 (与Hashtable基本一致)
  • TreeMap: 基于红黑树数据结构的实现 不允许空键空值 线程不安全
  • LinkedHashMap：基于散列表和双向链表的实现
  • WeakHashMap：改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

在除需要排序时使用TreeSet,TreeMap外,都应使用HashSet,HashMap,因为他们的效率更高。