集合:
List:
vector:
这个实现和ArrayList很相似,不过这个是线程安全的数组,很多方法都用了synchronized 上锁,所以并发能力不太行。
默认的容量是10 扩容倍数是 2
list有两个关键的继承子类:ArrayList 和 LinkedList
ArrayList : 底层基于数组实现 , 可以动态扩容 刚初始化时容量为0 , 只有当第一次添加数据或者构造时有参数传递才真的开启容量 默认长度是 10 扩容倍数是1.5 oldSize + (oldSize << 1)
平时我们使用的 size 代表的是list列表中所含有的数据量 而不是 底层elementData的长度
LinkedList : 这个List的实现是双向的链表结构 ------> 可以用作队列或者栈
对比: ArrayList 适合查询数据 根据索引直接定位 时间复杂度为 o(1) ,但是不适合插入和删除,时间复杂度为o(n)
LinkedList 就和 ArrayList 相反 关于链表的插入和删除操作要理解
HashTable:
默认初始容量是11 , 扩展因子是0.75 扩容为之前的2n+1
结构上和HashMap相似 , 但是HashTable是线程安全的 , 也是加锁 不过这个数据结构已经算是淘汰了 , 现在想使用线程安全的Map 可以使用currentHashMap
区分:
先给Map和Set做个区分 Map是双列集合
所以说在Map中Key是唯一的 Set中值是唯一的 如果想做去重两个都可以选
HashSet:
Set基于 数组+链表+红黑树实现(1.8之后)* 默认长度是16 拓展因子是0.75 就是说 当 数组长度为 12 时 需要扩容了 然后扩容倍数是两倍* ( 数组长度 - 1 )& hashCode* 如果自定义的类想要使用set 必须要重写hashCode和equals方法* 因为set默认是通过地址值计算 不是我们所希望的* 去重必须使用属性值计算 如果发生了哈希冲突* 新的元素会在数组上挂一条链表,一直向下连下去 但是* 如果链表长度大于8 且 数组长度大于64 就要转化成红黑树的模式
LinkHashSet:
在HashSet的基础上加上了一条双向链表;所以在HashSet无序的基础上,变成了有序的状态
TreeSet:
天生有序,而且不重复,底层是基于红黑树,不需要重写hashCode和equal方法,只需要指定Compare接口的比较方式就可以了
HashMap:
和HashSet是一样的,通过Key计算哈希值 , 一个节点里存了Key和Value
关于HashMap的扩容机制,和HashSet是相似的,都是默认大小是16 扩容因子是0.75 , 扩容倍数的2倍
LinkHashMap:
和LinkHashSet类似 , 在HashMap的上面多了一层双向链表
TreeMap:
和TreeSet类似
红黑树:
是一种特殊的二叉平衡树 但是我觉得在逻辑层面上来讲他确实不是二叉树
特性:
1、根节点的颜色是黑色
2、节点颜色要么是黑色、要么是红色
3、如果一个节点的颜色是红色,则它的子节点必须是黑色,即不能有2个连续的红色节点
4、每个叶子节点都是黑色(这里的叶子节点是为空的叶子节点)
5、从一个节点到该节点的叶子节点的所有路径上都包含相同数量的黑色节点
插入和删除都有特殊的操作,左旋右旋、颜色反转等等,记得不是很熟,还有特殊规则
B树:
每个数据占一个节点,不管是叶子结点还是非叶子结点都可以放数据
B+树:
数据只放在叶子结点上,非叶子结点只做索引的作用
可变参数:
可变参数也算一个集合吧 写法 public static void f( int …agrs ){} 这里把agrs收集成了一个ArrayList集合
集合类工具:
Collections类 下面举例一下常用的方法
private static void test1() { ArrayListarrayList = new ArrayList<>(); //统一添加元素到集合中 Collections.addAll(arrayList,"xxx","aaa","bbb","ccc"); //将集合随机乱序 Collections.shuffle(arrayList); //将集合中的元素反转 Collections.reverse(arrayList);}