常见的数据结构
线性表(list)
1、有序列表,就像小朋友排队(一队)放学出校门,插入的顺序作为遍历的顺序,位置不变(长度固定)
2、顺序存储:从起始位置开始依次向后存储,查询方便,但是插入(排队加塞)和删除(排队晕倒)的效率较低,位置可变(长度可变)
3、链式存储(链表):哪里有空位就往哪里存,通过地址“链”起来,查询麻烦(移动指针寻址),但是插入和删除非常高效
散列表
Hash table(散列表,也叫哈希表)是根据关键码值(Key-value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。(目录+链表,就像字典)
树(平衡二叉树)
二叉树是每个结点最多有两个子树的有序树。这两个子树有左右之分,分别称之为:“左子树”(left subtree)和“右子树”(right subtree)。
平衡二叉树指的是根节点左右两个子树的高度差不超过1,即左右几乎对称 。左子树上所有节点的值均小于或等于它的根节点的值,右子树上所有节点的值均大于或等于它的根节点的值。
Java集合框架
java集合框架分为二大派别 Collection和Map
collection又分为List(有序的可重复的【集合内容可以一样 并且 插入和查询一致】)和Set(无序的 唯一的【集合内容不能一样 并且插入和查询位置不一定一致】)
List 有 Vector、ArrayList、LinkedList 先看看这三个的区别
Vector 特点:有序的动态的可变的(集合的长度可变的查询和插入的顺序是一致的)数据是可重复的 线程相对安全(多线程里) 数据结构属于顺序存储 性能:增加和删除效率低(增加和删除的时候整个下标都会移动所以效率低) 但是查询效率高
ArrayList 特点:有序的动态的可变的(集合的长度可变的查询和插入的顺序是一致的)数据是可重复的 线程不保证安全 数据结构属于顺序存储 性能:增加和删除效率低(增加和删除的时候整个下标都会移动所以效率低) 但是查询效率高
LinkedList 特点:有序的动态的可变的(集合的长度可变的查询和插入的顺序是一致的)数据是可重复的 线程不保证安全 数据结构属于链表(也就是见缝插针) 性能:增加和删除效率高(存数据的时候哪有位置就放哪效率高) 但是查询效率低
一、Set接口下面的类
1、HashSet
1)、数据结构:散列表
2)、效率:整体效率都很高 (增加删除查询数据效率都很高)
3)、安全:不保证线程安全
4)、无序:是 无下标 (插入和查询集合数据是不能通过下标去查找对应的数据 所以HashSet继承的方法没有一个方法是通过下标去查询的)
5)、唯一:是 (当添加重复的数据的时候 编译不会报错 只是添加不到集合中去)
6)、能否存null值:能
2、LinkHashSet
1)、数据结构:散列表(顺序存储+链表)+链表
2)、效率:整体效率都很高 (增加删除查询数据效率都很高)
3)、安全:不保证线程安全
4)、无序:是 只是没有下标 (插入和查询集合数据是不能通过下标去查找对应的数据 所以HashSet继承的方法没有一个方法是通过下标去查询的,但是这个插入顺序和遍历顺序是一致的)
5)、唯一:是 (当添加重复的数据的时候 编译不会报错 只是添加不到集合中去)
6)、能否存null值:能
3、TreeSet
1)、数据结构:平衡二叉树(红黑树)
2)、效率:整体效率都很高 (增加删除查询数据效率都很高)
3)、安全:不保证线程安全
4)、无序:是 只是没有下标 (插入和遍历不一定一致、可以对数据自动排序《如果是数字类型可以自动从小到大排序、如果是对象可以按照某个属性进行自动排序》)凡是不知道该怎么排序的数据都不允许添加到TreeSet
5)、唯一:是 (当添加重复的数据的时候 编译不会报错 只是添加不到集合中去)
6)、能否存null值:不能
4、TreeMap
1)、数据结构:平衡二叉树(红黑树)
2)、效率:整体效率都很高 (增加删除查询数据效率都很高)
3)、安全:不保证线程安全
4)、无序:是 没有下标 插入顺序和遍历顺序不一定一致 可以自动对数据进行排序(按键的自然顺序)
5)、唯一:是 (当添加重复的数据的时候 编译不会报错 后面的键值对会覆盖前面的)
6)、能否存null值:键不可以 值可以