Java集合Collection、Map(JDK1.8的HashMap)的各个功能特点及总结
Java中集合总结
可以 点击看大图
结构分析
- 数组 : 查询快,增删慢
- 链表 : 查询慢,增删快
- 哈希表 : 保证元素的唯一
引用块内容
Collection
List
特点: 有序且可重复的
ArrayList
- 底层数据结构是数组,查询快,增删慢
- 线程不安全,效率高
Vector
- 底层数据结构是数组,查询快,增删慢
- 线程安全,效率低
LinkedList
- 底层数据结构是链表,查询慢,增删快
- 线程不安全,效率高
Set
特点: 无序且不可重复的
HashSet
- 底层数据结构是哈希表。
- 哈希表依赖两个方法：hashCode()和equals()
- 执行顺序 :
- 先判断hashCode()值是否相同
- 如果是,继续执行equal(),看其返回值
- true : 说明元素重复,不添加
- fasle : 直接添加到集合中
- 如果否,直接添加到集合中
- 最终 :
- 自动生成hashCode()和equals()方法即可
LinkedHashSet
- 底层数据结构由链表和哈希表组成。
- 由链表保证元素有序。
- 由哈希表保证元素唯一。
TreeSet
- 底层数据结构是红黑树。(是一种自平衡的二叉树)
- 如何保证元素唯一性呢?
- 根据比较的返回值是否是0来决定
- 如何保证元素的排序呢?
- 两种方式
- 自然排序(元素具备比较性)
- 让元素所属的类实现Comparable接口
- 比较器排序(集合具备比较性)
- 让集合接收一个Comparator的实现类对象
- 自然排序(元素具备比较性)
- 两种方式
Map
HashMap
在JDK1.8之前,HashMap底层是基于哈希表的,数据结构是数组+链表
在JDK1.8,引入了红黑树,数据结构是数组+链表+红黑树
JDK1.8的HashMap
引入原因 : 提高HashMap的性能
- 解决发生哈希碰撞后,链表过长从而导致索引效率慢的问题
- 具体:
- 利用红黑树快速增删改查的特点
- 时间复杂度从O(n) 降为 O(logn)
应用场景
- 当链表长度>8时,将该链表转换成红黑树
- 即红黑树作为存储数据&解决Hash冲突的第3方案
- 无冲突时:存放数组
- 冲突&链表长度<8时:存放在单链表
- 冲突&链表长度>8时:存放在红黑树
Hashtable
- 底层数据结构是哈希表。
- 哈希表依赖两个方法：hashCode()和equals()
- 执行顺序 :
- 先判断hashCode()值是否相同
- 如果是,继续执行equal(),看其返回值
- true : 说明元素重复,不添加
- fasle : 直接添加到集合中
- 如果否,直接添加到集合中
- 最终 :
- 自动生成hashCode()和equals()方法即可
LinkedHashMap
- 底层数据结构由链表和哈希表组成。
- 由链表保证元素有序。
- 由哈希表保证元素唯一。
TreeMap
- 底层数据结构是红黑树。(是一种自平衡的二叉树)
- 如何保证元素唯一性呢?
- 根据比较的返回值是否是0来决定
- 如何保证元素的排序呢?
- 两种方式
- 自然排序(元素具备比较性)
- 让元素所属的类实现Comparable接口
- 比较器排序(集合具备比较性)
- 让集合接收一个Comparator的实现类对象
- 自然排序(元素具备比较性)
- 两种方式
按照实现接口分类：
实现Map接口的有：EnumMap、IdentityHashMap、HashMap、LinkedHashMap、WeakHashMap、TreeMap
实现List接口的有：ArrayList、LinkedList
实现Set接口的有：HashSet、LinkedHashSet、TreeSet
实现Queue接口的有：PriorityQueue、LinkedList、ArrayQueue
根据底层实现的数据结构分类：
- 底层以数组的形式实现：EnumMap、ArrayList、ArrayQueue
- 底层以链表的形式实现：LinkedHashSet、LinkedList、LinkedHashMap
- 底层以hash table的形式实现：HashMap、HashSet、LinkedHashMap、LinkedHashSet、WeakHashMap、IdentityHashMap
- 底层以红黑树的形式实现：TreeMap、TreeSet
- 底层以二叉堆的形式实现：PriorityQueue