Java 常用数据结构概述

数据结构包含三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构与存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的的存储结构。逻辑结构（线性结构与非线性结构）存储结构（顺序存储、链式存储、索引存储、散列存储）

常用数据结构关系

Collection 单列集合

List 有序，可重复

ArrayList

底层是数组，查询快，增删慢
线程不安全，效率高

Vector

底层是数组，查询快，增删慢
线程安全，效率低

LinkedList

底层是双向链表，查询慢，增删快
线程不安全，效率高

Set 无序，唯一

HashSet

底层是哈希表
哈希表唯一依赖两个方法：hashCode(),equals();
执行顺序：
先看哈希值是否相同即hashCode():
是：调用equals()方法，判断返回值
是true:不添加
是false：添加到集合
否：直接添加

LinkedHashSet

底层是哈希表和链表
哈希表保证元素唯一
链表保证元素有序

TreeSet 自动排序

底层是红黑树，自平衡二叉树
保证元素唯一性：
看元素返回值是否为0来决定
有两种排序方法
自然排序：元素具备比较性
元素所在的类实现Comparable接口，重写compareTo()方法
比较器排序：集合具备比较性
让集合接收一个实现Comparator的类对象，重写compare()方法

Map 双列集合

A: Map集合的数据结构仅对键有效，对值无效
B: Map集合中存储的是键值对的元素，键唯一，值可以重复

HashMap

底层是哈希表
哈希表唯一依赖两个方法：hashCode(),equals();
线程不安全，效率高，允许null键null值
执行顺序：
先看哈希值是否相同即hashCode():
是：调用equals()方法，判断返回值
是true:不添加
是false：添加到集合
否：直接添加

LinkedHashSet

底层是哈希表和链表
哈希表保证元素唯一
链表保证元素有序

Hashtable

线程安全，效率低，不允许null键null值

TreeMap

底层是红黑树，自平衡二叉树
保证元素唯一性：
看元素返回值是否为0来决定
有两种排序方法
自然排序：元素具备比较性
元素所在的类实现Comparable接口，重写compareTo()方法
比较器排序：集合具备比较性
让集合接收一个实现Comparator的类对象，重写compare()方法

参考资料：
数据结构与算法系列 目录
HashMap底层原理

(部分内容参考于网络，如有不妥，请联系删除～)