数据结构包含三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构与存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的的存储结构。逻辑结构（线性结构与非线性结构）存储结构（顺序存储、链式存储、索引存储、散列存储）
常用数据结构关系
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底层原理
(部分内容参考于网络，如有不妥，请联系删除～)
网友评论