集合框架-1.0-概述

Java集合概述

Java集合概览

Java集合框架如上图所示，集合也叫做容器，主要有两大接口派生而来：

1. Collection接口，主要用于存放单一元素
   • List
   • Set
   • Queue
2. Map接口，主要用于存放键值对

List、Set、Queue、Map四者的区别？

List：存储的元素是有序的、可重复的

Set：存储的元素是不可重复的

Queue：按照特定的排队规则来确定先后顺序（先进先出FIFO），存储的元素是有序的、可重复的

Map：使用键值对（key-value）进行存储，key是无序的、不可重复的，value是无序的、可重复的，每个key最多映射一个value

集合框架底层数据结构总结

Collection接口下的集合

List

• ArrayList：Object[]数组

  

• Vector：Object[]数组

  

• LinkedList：双向链表（在JDK1.6以前是循环链表，JDK1.7开始取消了循环）

Set

• HashSet（无序、唯一）：基于HashMap实现，底层采用HashMap来保存元素

  

• LinkedHashSet：是HashSet的子类，内部通过LinkedHashMap实现

  

• TreeSet（有序、唯一）：红黑树（自平衡的排序二叉树）

Queue

• PriorityQueue：Object[]数组实现小顶堆
• DelayQueue：基于PriorityQueue实现的无界队列
• ArrayDeque：可扩容动态双向数组

Map

• HashMap：JDK1.8以前使用链表+数组的方式实现，数组是HashMap的主体，链表是为了解决哈希冲突存在的（拉链法），在JDK1.8以后，HashMap在解决哈希冲突时有了比较大的变化，当链表长度>=阈值（默认为8）的时候，（在链表转为红黑树之前会先判断数组长度是否小于64，如果小于则对数组扩容，而不是转为红黑树）将链表转化为红黑树以减少搜索时间s
• LinkedHashMap：继承自HashMap，所以其底层仍基于拉链式散列结构（由数组和链表和红黑树组成），另外LinkedHashMap在上面结构的基础上增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序，同时对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable：数组+链表组成，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap：红黑树，自平衡的排序二叉树