Java基础 集合类

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）任意节点到叶子节点的路径中 黑色节点的个数相同（这个意义上来说是平衡的）。