丙-集合 基础 - 图1

HashMap

数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node。
1.8插入数据时判断链表长度是否大于 8并且数组长度大于64， 大于的话链表转换为红黑树；当删除小于六时重新变为链表

根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。

负载因子0.75

提高空间利用率 和 减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小，

加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；
加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。
在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，所以，一般在使用HashMap时建议根据预估值设置初始容量，减少扩容操作。
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择，.

初始化长度16

默认初始化长度（1<<4就是16），因为**位与运算**比算数计算的效率高了很多。
15的的二进制是1111 。
因为Length-1的值是所有二进制位全为1，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。2的幂实现均匀分布。

红黑树

红黑树是一种自平衡的二叉查找树

  1. 节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点都是黑色的空节点（NIL节点）。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
    这些规则确保 从根到叶子节点的最长路径不超过最短路径的2倍。
    平衡时使用：变色 + 旋转

左旋转： 逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。

为什么要有红黑树

二叉搜索树的查询、插入和删除一个节点的时间复杂度均为O（log(n)）。但向其依次插入有序数组后会退化成链表。因此引入平衡二叉树。

平衡二叉树具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树保证了在最差的情况下，二叉树依然能够保持绝对的平衡，即左右两个子树的高度差的绝对值不超过1。但是这又会带来一个问题，那就是平衡二叉树的定义过于严格，导致每次插入或者删除一个元素之后，都要去维护二叉树整体的平衡，这样产生额外的代价又太大了。二叉搜索树可能退化成链表，而平衡二叉树维护平衡的代价开销又太大了，那怎么办呢？这就要谈到“中庸之道”的智慧了。说白了就是把平衡的定义适当放宽，不那么严格，这样二叉树既不会退化成链表，维护平衡的开销也可以接受。

红黑树和平衡二叉树区别

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差的绝对值不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况。
红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树。

红黑树是牺牲了严格的高度平衡的优越条件 为 代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

迭代器

HashMap 中的 Iterator 迭代器是 fail-fast。

  • 快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。在遍历过程中使用一个 modCount 变量，遍历下一个元素之前都会去监测这个值。
  • 安全失败（fail—safe）遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。（java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。）

扩容机制

数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容（resize）。

  • 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
  • ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。
    （长度扩大以后，Hash的规则变化HashCode（Key） & （Length - 1）） HashCode（Key）就是：hashcode的高16位和低16位异或，用之前需要对数组的长度取模运算（因为数组的初始大小才16放不下哦），把散列值和数组长度-1做一个”与”操作）

扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8 不用重新hash就可以直接定位原节点在新数据的位置；（扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，重新hash数值比原来大16（旧数组的容量））

jdk1.7头插法（新元素总会被放在链表的头部位置）在resize时多线程会形成环形链表。
1.8使用尾插法避免（使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。）但是它没有加同步锁，多线程情况最容易出现的就是：线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，A会把B的数据覆盖。

为什么重写equals方法的时候需要重写hashCode方法呢？

在java中，所有的对象都是继承于Object类。在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样。

  • 对于值对象，==比较的是两个对象的值
  • 对于引用对象，比较的是两个对象的地址

对hashCode方法重写，以保证相同的对象返回相同的hash值。不然链表咋找对象？？

线程安全的实现

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

  1. HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大。

HahTable对象的key、value值均不可为null。Hashtable使用的是安全失败机制（fail-safe），如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。HashMap 的键值则都可以为 null

  1. Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁Map，方法内通过对象锁（Map）实现【还有排斥锁mutex，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。】；
  2. ConcurrentHashMap使用CAS + synchronized，让并发度大大提高。

LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。
TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。

HashTable和HashMap的区别

散列表，又叫哈希表（Hash Table），是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。

1、继承：
HashTable继承自Dirctionary，HashMap继承自AbstractMap，二者均实现了Map接口。
2、线程安全性：
HashTable的方法是同步的，即是线程安全的。HaspMap的方法不是同步的，不是线程安全的的。在多线程并发的情况下，我们可以直接使用HashTable，如果 要使用HashMap，就需要自行对HashMap的同步处理。
3、键值：
HashTable中不允许有null键和null值，HashMap中允许出现一个null键，可以存在一个或者多个键的值都为null。程序中，对于HashMap，如果使用get(参数为 键)方法时，返回结果为null，可能是该键不存在，也可能是该键对应的值为null，这就出现了结果的二义性。因此，在HashMap中，我们不能使用get()方法来查询键 对应的值，应该使用containskey()方法。
4、遍历：
这两个在遍历方式的实现不同。HashTable和HashMap两者都实现了Iterator。但是，由于历史原因，HashTable还使用了Enumeration。
5、哈希值：
HashTable是直接使用对象的hashCode。HashMap是重新计算hash值。
6、扩容：
HashTable和HashMap的底层实现的数组和初始大小和扩容方式。HashTable初始大小为11，并且每次扩容都为：2_old+1。HashMap的默认大小为16，并且一 定是2的指数，每次扩容都为old_2。

ConcurrentHashMap

jdk1.7

jdk1.7时，由 Segment 数组（ 继承于 ReentrantLock）-》里面存放数据使用的是
HashEntry（HashEntry跟HashMap差不多的，但是不同点是，他使用volatile去修饰了数据Value还有下一个节点next） 组成。分段锁技术：当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。set需要获取Segment 锁；而 get 方法由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，因为不需要加锁。

jdk1.8

jdk1.8时，采用了 CAS + synchronized 来保证并发安全性。抛弃了原有的 Segment 分段锁，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰。采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized。

  1. JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）
  2. JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
  3. JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档

JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，有以下几点
因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了
JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然
在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据

put操作

ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：

  1. 根据 key 计算出 hashcode 。
  2. 判断是否需要进行初始化。
  3. 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
  4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  5. 如果都不满足，则利用 synchronized 锁写入数据。
  6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。
CAS 带来的ABA问题加个版本号、时间戳就能解决。

ArrayLists和LinkedList

ArrayList是实现了基于动态数组(jdk1.8后对arraylist进行优化，默认为0，初次添加元素时扩容为10,为的是避免无用内存占用。每次扩容1.5倍)的数据结构，随机访问占优，空间浪费主要体现在在list列表的结尾预留一定的容量空间；

  • 当使用ArrayList（int initialCapacity）的时候，不会初始化数组大小，只是指定了elementData缓冲区数组的大小， 跟数组的大小size并没有什么关系。（elementData用transient来修饰，因为elementData里面有一些元素是空的，这种是没有必要序列化的。）
    LinkedList基于链表的数据结构，新增和删除占优，空间花费则体现在它的每一个元素都需要消耗相当的空间。

ArrayList遍历性能更快

ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

Arrays.asList()的坑
Arrays.asList()方法返回的是的Arrays内部的ArrayList，用的时候需要注意。它体现的是适配器模式，后台的数据仍然是数组，所以不能使用修改集合的方法（add/remove/clear）

数组 (Array) 和列表 (ArrayList) 有什么区别

  • Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
  • Array 大小是固定的，ArrayList 的大小是动态变化的。

使用Vertor、Collections.synchronizedList、CopyOnWriteArrayList 确保线程安全。

CopyOnWrite并发容器用于读多写少的并发场景（ 只是在增删改上加锁，但是读不加锁）。

  • 内存占用问题。因为CopyOnWrite的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，
  • 数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性，不能保证数据的实时一致性。

CopyOnWriteArrayList 写入操作 add() 方法在添加集合的时候加了锁，保证同步，避免多线程写的时候会 copy 出多个副本。

虽然同步容器（例如Vertor）的所有方法都加了锁，但是对这些容器的复合操作无法保证其线程安全性。需要客户端通过主动加锁来保证。
由于同步容器存在的并发度低问题，从Java5开始，java.util.concurent包下，提供了大量支持高效并发的访问的集合类—并发容器。但是，作为代替Vector的CopyOnWriteArrayList并没有解决同步容器的复合操作的线程安全性问题。

ConcurrentHashMap中增加了对常用复合操作的支持，比如putIfAbsent()、replace()

Comparable 和 Comparator 接口

  • Java 提供了只包含一个 compareTo() 方法的 Comparable 接口。这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明输入对象小于，等于，大于已经存在的对象。
  • Java 提供了包含 compare() 和 equals() 两个方法的 Comparator 接口。compare() 方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。equals() 方法需要一个对象作为参数，它用来决定输入参数是否和 comparator 相等。只有当输入参数也是一个 comparator 并且输入参数和当前 comparator 的排序结果是相同的时 候，这个方法才返回 true。

1、如果实现类没有实现Comparable接口，又想对两个类进行比较（或者实现类实现了Comparable接口，但是对compareTo方法内的比较算法不满意），那么可以实现Comparator接口，自定义一个比较器，写比较算法

2、实现Comparable接口的方式比实现Comparator接口的耦合性要强一些，如果要修改比较算法，要修改Comparable接口的实现类，而实现Comparator的类是在外部进行比较的，不需要对实现类有任何修 改。从这个角度说，其实有些不太好，尤其在我们将实现类的.class文件打成一个.jar文件提供给开发者使用的时候。实际上实现Comparator 接口的方式后面会写到就是一种典型的策略模式。

其它基础知识

String，StringBuild，StringBuff的区别

执行效率： stringbuild>stringbuff>string
String类是不可变类，任何对String的改变都会引发新的String对象的生成；
StringBuffer是可变类，任何对它所指代的字符串的改变都不会产生新的对象，线程安全的。
StringBuilder是可变类，线性不安全的，不支持并发操作，不适合多线程中使用，但其在单线程中的性能比StringBuffer高。

Java 15

  1. 提供详细的错误信息。-XX：+ShowCodeDetailsInExceptionMessages 可以看到a().b().c().xx 哪个出问题了。

    无论对于基本类型or引用变量，Java中的参数传递都是值复制的传递过程。

    Ref var（引用变量）是基本的数据类型，默认值null，存储refobj的首地址，可直接用双等号==进行判断。
    refvar作为引用变量，不管它指向谁，均占用4B空间。无论refobj（引用指向的实际变量）有多小，最小占用12B（存储基本信息-对象头），存储空间分配必须是8的倍数，占用16B。
    基本数据类型int占4字节，包装类Integer占用16个字节（4+12refobj）。字段属性除了成员属性int value外，其他的都是静态成员变量，类加载时就分配了内存。

    字节码必须通过类加载过程加载到JVM中才可以执行。

  2. 解释执行。

  3. JIT编译执行。
  4. JIT编译与解释混合执行。（默认）省去编译时间，通过热点代码分析，基于JIT将Java字节码动态的编译成可以直接发送给处理器指令执行的机器码。

  • 因此，机器在热机状态承受的负载要大于冷机状态（热点代码统计+JIT动态编译）

    Throwable 与 Exception

    Throwable — Error（StackOverFlow、OutofMemory）只能人工介入 + Exception【checked + unchecked】

  • check（SQLException、ClassNotFound）：需要在代码中显式处理，否则编译出错。

  • unchecked（继承RuntimeException）：不需要显示处理。