Java基础 集合类

Java基础 集合类

2020-04-17    07'47''

主播: 橙汁儿橙汁儿。

222 1

介绍:
Java中的集合类:有 Map 和 Collection 两个接口。 Collection 接口的实现类是单个集合。而 Map 是键值对的形式。 1.ArrayList 与 LinkedList ArrayList 底层是 Object 数组,默认长度是 10,以 1.5 倍扩容。对于数组,可以通过索引查找元素,而添加 和 删除元素,需要 把该位置之后的元素挨个赋值,效率低。要注意它有个 remove(Object o)方法,会从头到尾遍历,删除第一次出现的元素,还有个 remove(int index),删除指定下标的元素。如果是整型数组,要删除指定元素需要将传入的参数转化成 Integer 类型,否则会被作为下标对待。 LinkedList 是双向链表,不存在容量和扩容,它的空间消耗体现在 前驱节点 和 后继节点。对于链表,查找元素效率比较低,根据长度和下标的关系,从头或从尾遍历链表,而添加 和 删除效率较高。 2.ArrayList 与 Vector Vector 默认长度也是 10,扩容时可以指定容量增长因子,默认扩容是 2 倍。 ArrayList 是线程不安全的,而 Vector 使用 synchronized 保证线程安全。 3.ArrayList 线程不安全的体现 比如说现在数组容量是 9,添加元素前会使用 ensureCapacityInternal(size+1),线程 A 先判断不需要扩容,接下来 线程 B 添加了一个元素,这时数组容量变为 10,然后 CPU 切换回线程 A,而线程 A 之前判断过不需要扩容,就会向数组添加新元素,就会抛出 ArrayIndexOutofBounds 异常。 再有:添加元素时,检查完容量之后, elementData[size]=e; size++;比如说 size=8,如果线程 A 先 element[8]赋值,接下来 CPU 时间片切换到 线程 B,线程 B 给 elementData[8] 赋值,这样会导致 [8] 被重复赋值了,而 [9]没有被赋值,size 变为 10。 4.HashMap 以 key-value 形式存储元素,底层是 Node 类型的数组,每个Node 是链表,链表长度达到 8 会转化成红黑树。根据给定的 key,会调用本地方法 HashCode ,为不同的对象求得不同的整数值,这个值会与它右移 16 位的值相与,增加随机性。然后对数组长度取余,为方便计算,数组长度总是 2 的幂次方,取余操作就优化成 &(数组长度-1),可求得 key 对应的下标,如果下标对应的元素是 null,就直接赋值,如果不为 null,就通过 hashCode() 和 equals()比较 key 值是否重复,不重复的话会尾插链表,否则会覆盖旧值,并返回旧值。数组达到阈值会以 2 倍扩容,阈值是数组容量 * 负载因子,默认情况下是 16 * 0.75。 tableSizeFor()方法: 实现求 比指定数字大的 最小的 2 的倍数。 需要把最高位的 1 后面的位都变成 1 ,然后+1。 依次无符号右移 1,2,4,8,16,而且每次会进行 或 运算。最后给结果 +1 即可得到 比它大的 最小的 2 的倍数。 如果一开始已经是 偶数,就需要 先给数字 -1。 put()方法: 首先会看原来数组是否为null,是的话会调用 resize() 方法。 resize()方法: 除了扩容之外,还会将原来数组中的元素迁移到扩容后的数组中。 如果原来数组没有链链表,迁移时会根据新数组的长度重新计算下标。 如果原来数组链的是红黑树,会调用红黑树的方法 split()。 如果原来数组链的是链表,会使用 HashCode 与 旧容量 相与,如果结果是 0 ,说明到新数组中下标不变;如果 是 1,说明到新数组的下标值是原下标值+原数组长度,会为 下标不改变的元素 和 下标要改变的元素 分别生成两个链表,依次链到新数组中。 5.HashSet为什么不会重复: HashSet 底层有个 HashMap,而 HashSet 的 add() 方法返回值是 put(e,PRESENT)==null,PRESENT 是一个固定的 Object 类型的常量 。 添加元素时,如果根据 key 值求得的下标,如果下标处是 null,就会把添加的元素作为 key值,把 PRESENT 作为 value,返回 null,那么对应的 add() 方法返回值是 true,添加成功;否则说明元素重复,还是以 PRESENT 作为value 覆盖,返回的是原值 PRESENT,而对应 add()方法的返回值是 false,添加失败,只会有一个元素,不允许重复。 6.红黑树 是一个二叉搜索树。满足 5 个条件: (1)每个节点不是红色,就是黑色。 (2)根节点必须是黑色。 (3)红黑树的叶子节点( null 节点)必须是黑色。 (4)红色节点的两个子树必须是黑色。 (5)任意节点到叶子节点的路径中 黑色节点的个数相同(这个意义上来说是平衡的)。