[数据结构与算法]StringBuffer和StringBuilder的异同

StringBuffer和StringBuilder的异同

String类是的对象代表不可变的字符序列，StringBuilder类和StringBuffer类代表可变字符序列
JDK9时String类底层由char数组变为byte数组，节省空间
StringBuffer JDK1.0提供的类，线程安全，做线程同步检查，效率较低
StringBuilder JDK1.5提供的类，线程不安全，不做线程同步检查，因此效率较高

StringBuilder、StringBuffer都是可变类，可以修改字符串而不需要创建对象，StringBuffer是在Java的初始版本中引入的，而StringBuilder是在Java5中引入的。StringBuffer是同步的，StringBuilder不是同步的。StringBuffer是线程安全的，所以多个线程不能同时访问，因此速度比较慢，由于StringBuilder不是线程安全的相比较StringBuffer（开销较少=效率较高），初始容量都是16和扩容机制都是旧容量*2+2，底层都是用char[]字符数组实现，且字符数组都是可变的，这点不同于String

理解StringBuilder源码

• StringBuilder类底层和String类一样，也是一个字符数组value，但不是final的。变量count表示的是底层字符数组的元素的真实个数，不是底层字符数组的长度
• 默认数组的长度是16。也可以通过构造方法直接指定初始长度。length()方法返回的是字符数组元素的真实个数，capacity()返回的是底层数组的长度
• 每次添加字符串时要扩容，扩容的默认策略时候增加到原来长度的2倍再加2

扩展

HashMap&Hashtable

??HashMap&Hashtable共同点都是双列集合，底层都是哈希算法。区别是HashMap是线程不安全的，效率高，JDK1.2版本，Hashtable是线程安全的，效率低，JDK1.0版本。HashMap可以存储null键和null值，Hashtable不可以存储null键和null值。HashMap&Hashtable继承的父类不同，HashMap继承自AbstractMap类，而Hashtable是继承自Dictionary类。不过HashMap&Hashtable都实现了map、Cloneable(可赋值)、Serializable(可序列化)这三个接口，而且Dictionary类是一个已经被废弃的类。父类都被废弃，自然而然也没有人使用他的子类。Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2N+1，HashMap默认的初始化大小为16，之后每次扩充变为原来的2倍，同时Hashtable在1.7中已经过时。

??HashMap不是线程安全的实现，而Hashtable确实通过同步操作提供线程安全。
即使Hashtable是线程安全的，它也不是很有效。另一个完全同步的Map Collections.synchronizedMap也没有表现出很大的效率，ConcurrentMap是Map接口的扩展。它旨在提供一种结构和指导来解决协调吞吐量与线程安全的问题。

HashMap

HashMap 的底层由数组 + 链表 + 哈希表组成
数组: 存储间隔连续，时间复杂度为 o (1) ，随机读取效率很高，插入和删除效率低，大小固定，不易扩展
链表: 间隔离散，时间复杂度为 o (n) ，插入和删除速度快，查询效率低
哈希表: 结合了数组和链表的优点，实现了高查询效率和插入删除效率

??HashMap 基于散列原则。我们通过 put ()和 get ()方法存储和获取对象。当我们将键值对传递给 put ()方法时，它调用键对象的 hashCode ()方法来计算哈希代码，然后找到存储值对象的 bucket 位置来存储条目键值对。获取对象时，通过键对象的 equals ()方法找到正确的键值对，然后返回 value 对象。HashMap 使用链表来解决冲突问题。当发生冲突时，对象将存储在链表的下一个节点中。HashMap 在每个链表节点中存储键值对对对象。
??HashMap 集合的关键部分的元素需要重写 equals 方法，因为 equals 的默认比较是两个对象的内存地址
??在 JDK8之后，如果链表的哈希形式中有8个以上的元素同时数组大于64时，则单链表的数据结构将变为红黑树数据结构。当红黑树上的节点数小于6时，红黑树将再次变为单链表数据结构。

HashMap扩容机制

??加载因子是用来决定何时增加 HashMap 的容量的度量值。默认的加载因子是0.75 f。
??HashMap 的阈值是当前容量和负载因子的乘积。
??这意味着，在将第12个元素(键值对)添加到 HashMap 中之后，HashMap 的容量将从16增加到32。

阈值 = (当前容量) * (负载系数)
阈值 = 16 * 0.75 = 12

为什么加载因子使用0.75f?
??首先加载因子0.75f总是在空间和时间方面提供最好的性能。
??当选择负载因子为1.0 f，那么在填满当前容量的100% 之后会发生重新散列。这可能会节省空间，但会增加现有元素的检索时间。假设如果您选择负载因子为0.5 f，那么在填充了当前容量的50% 之后会发生重新散列。这将增加重新散列操作的数量。这将进一步降低 HashMap 在空间和时间方面的性能。

put

??第一步是将 k 和 v 封装到 Node 对象(节点)中。在第二步中，它的底层将调用 k 的 hashCode ()方法来获取哈希值。第三步是通过哈希表函数/哈希算法将哈希值转换为数组的下标。如果下标位置中没有元素，则将 Node 添加到此位置。如果在下标对应的位置有一个链表。此时，它将保存链表中每个节点的 k 和 k 为相等。如果所有 equals 方法返回 false，那么这个新节点将被添加到链接列表的末尾。如果其中一个等于返回 true，则该节点的值将被覆盖。

get

??第一步: 首先调用 k 的 hashCode ()方法以获得散列值，然后通过散列算法将其转换为数组的下标。步骤2: 通过前面的哈希算法转换为数组的下标之后，通过数组的下标快速定位某个位置。重要的是要理解，如果这个位置没有任何东西，则返回 null。如果在这个位置有一个单链表，它等于单链表中每个节点的参数 k 和 k。如果所有 equals 方法返回 false，get 方法返回 null。如果其中一个节点的 k 和参数 k 等于返回 true，那么该节点的值就是我们要寻找的值，而 get 方法最终将返回我们要寻找的值。

ArrayList&Vector

当Vector元素超过初始大小时，Vector的容量增加1倍，而Arraylist只增加0.5，所以使用Arraylist有利于节省空间，Arraylist初始容量为0空数组，添加第一个元素时扩容至10，后续0.5倍扩容
两个类都实现了list接口，它属于一个有序集合，一个有序集合，顾名思义，存储在两个集合中的元素是当一个元素被删除时，可以根据位置索引来获取它。这两个类都允许重复数据。这是与集合的最大区别
Vector是线程安全的，但是arraylist不是线程安全的。退一步,如果只有一个线程访问集合,最好是有一个arraylist,因为线程基本上是不担心线程安全,但是如果你访问多个线程在一起,你仍然需要使用向量,因为你不需要思考,自己编写线程安全的代码

Hashtable&Properties

Properties是 Hashtable 的子类，不同之处在于 Properties 只有键和值 String Object，但是在 HashTable 中，我们可以将任何对象作为键和值
Properties是一个非常特殊的类，用于保存通常存储在某个文件中的配置和/或资源，它是为字符串到字符串的映射而设计的，它还增加了将映射存储到文本文件中并将其读回的能力。

Synchronizied同步特性

Java 中的同步是控制多线程访问任何共享资源的能力
同步主要用于防止线程干扰、防止一致性问题
同步类型有进程同步、线程同步
对于synchronized锁（同步代码块和同步方法），如果正常执行完毕，会释放锁。如果线程执行异常，JVM也会让线程自动释放锁。所以不用担心锁不会释放

synchronized锁的缺点：

• 如果获取锁的线程由于要等待IO或其他原因（如调用sleep方法）被阻塞了，但又没有释放锁，其他线程只能干巴巴地等待，此时会影响程序执行效率。甚至造成死锁;
• 只要获取了synchronized锁，不管是读操作还是写操作，都要上锁，都会独占。如果希望多个读操作可以同时运行，但是一个写操作运行，无法实现。

可重入性
??Synchronized 方法和块背后的锁是可重入的。也就是说，当前线程可以一次又一次地获得同样的同步锁

线程同步
??相互排斥有助于防止线程在共享数据时相互干扰
??相互排斥可以通过三种反式实现：同步方法、同步阻塞、静态同步

Lock

基于synchronized锁的一些缺点，JDK1.5中推出了新一代的线程同步方式：Lock锁。更强大、更灵活、效率也更高

扩展：同步锁的底层优化：锁升级

• 在 Java 语言中，使用Synchronized 是能够实现线程同步的，在操作同步资源的时候直接先加锁。加锁可以使一段代码在同一时间只有一个线程可以访问，在增加安全性的同时，牺牲掉的是程序的执行性能，被称为重量级锁。
• 为了在一定程度上减少获得锁和释放锁带来的性能消耗，在JDK6 之后引入了“偏向锁”和“轻量级锁”，所以总共有4种锁状态，级别由低到高依次为：无锁状态、偏向锁状态、轻量级锁状态、重量级锁状态。这几个状态会随着竞争情况逐渐升级。
• 锁升级的过程
• 在markword中标记锁的类型
  普通对象在内存中的结构分为多部分，第一部分称为markword，共64位。在对应锁对象的markword字段的低位字段标记锁的类型。

Synchronized 和 Lock 区别

1. Lock 是一个接口，Synchronized 是关键词
2. Synchronized 自动释放锁，Lock必须手动释放锁
3. Lock 可以中断等待锁的线程的响应，但 Synchronized 不会，线程将一直等待
4. Lock 让你知道一个线程是否有锁，但 Synchronized 不能
5. Lock 可以提高多线程的效率
6. 同步锁定类、方法和代码块，而 Lock 是整个块范围的

java.util.concurrent

java.util.concurrent包涵盖了 Java 平台上的并发、多线程和并行性。并发性是并行运行多个或多个程序或应用程序的能力。Java 并发的主干是线程(一个轻量级进程，它有自己的文件和堆栈，并且可以访问同一进程中其他线程的共享数据)。通过异步或并行地执行耗时的任务，可以提高程序的吞吐量和交互性

Executor

Executor 是一组接口，它表示其实现执行任务的对象。这取决于任务是在新线程上运行还是在当前线程上运行的实现。因此，我们可以使用这个接口将任务执行流与实际的任务执行机制解耦。执行器不要求任务的执行是异步的。最简单的是可执行接口

ExecutorService

ExecutorService 是一个接口，只强制底层实现execute()方法。它扩展了 Executor 接口，并添加了一系列用于执行返回值的线程的方法。关闭线程池的方法以及实现任务执行结果的能力
shutdown()：它等待所有提交的任务执行完毕
shutdownNow()：它立即终止所有正在执行/挂起的任务
还有一个 awaitTermination ()方法，它强制阻塞所有任务，直到发生关闭事件触发或执行超时或执行线程本身被中断之后，才完成执行

ScheduledExecutorService

它类似于 ExecutorService。不同之处在于，这个接口可以定期执行任务。可运行函数和可调用函数都用于定义任务
ScheduledExecutorService 还可以在固定的延迟之后定义任务

Future

它表示异步操作的结果。其中的方法检查异步操作是否完成，得到完成的结果等等。Cancel (boolean isInterruptRunning) API 取消操作并释放执行线程。当 isInterruptRunning 值为 true 时，执行任务的线程将立即终止。否则，所有正在进行的任务都将完成

CountDownLatch

它是一个工具类，可以阻塞一组线程，直到某些操作完成为止
CountDownLatch 使用计数器(Integer 类型)进行初始化
当依赖线程的执行完成时，此计数器将递减。但是一旦计数器递减到零，其他线程就会被释放

CyclicBarrier

除了我们可以重用它之外，CyclicBarrier 几乎与 CountDownLatch 相同。它允许多个线程在调用最终任务之前使用 await ()等待彼此，而这个特性不在 CountDownLatch 中

Semaphore

Semaphore包含了一定数量的许可证，通过获取许可证，从而获得对资源的访问权限。通过 tryAcquire()来获取许可，如果获取成功，许可证的数量将会减少
一旦线程release()许可，许可的数量将会增加

ThreadFactory

它充当一个线程池，ThreadFactory可以很方便的用来创建线程

BlockingQueue

BlockingQueue 接口通过在 BlockingQueue 为满或空时引入阻塞，支持流控制(除了队列)。试图将一个元素加入到完整队列中的线程被阻塞，直到其他线程通过排除一个或多个元素或完全清除队列而在队列中留出空间。类似地，它阻止一个试图从一个空队列中删除的线程，直到其他一些踏板插入一个项目。BlockingQueue 不接受空值。如果我们尝试将 null 项加入队列，那么它将抛出 NullPointerException

DelayQueue

DelayQueue 是一个专用的优先级队列，它根据元素的延迟时间对元素进行排序。这意味着只能从时间已经过期的队列中提取那些元素。DelayQueue 头包含在最短时间内过期的元素。如果没有延迟过期，则没有 head，poll 将返回 null。DelayQueue 只接受属于 DelayQueue 类型的类的元素。DelayQueue 实现 getDelay ()方法来返回剩余的延迟时间

Lock

它是阻止其他线程访问某段代码的实用工具。Lock 和 Synchronized 块的区别在于，我们在不同的方法中使用 Lock api Lock ()和 unlock ()操作，而 Synchronized 块完全包含在方法中

Phaser

它比 CountDownLatch 和 CyclicBarrier 更灵活。Phaser 用作一个可重用的屏障，线程的动态数量需要在其上等待，然后才能继续执行。通过在每个程序阶段重用 Phaser 的实例，可以协调多个执行阶段

悲观锁和乐观锁

* 公平锁 非公平锁
* 公平锁:当多个线程共同尝试上锁的时候,lock会倾向于让等待时间最长的线程优先获得
* 乐观锁 乐观锁认为线程安全问题很少出现,即是上锁,也锁不住
* 悲观锁 悲观锁任务线程安全问题随时放生,上了锁就能锁住
* 目前所学的所有的锁都是悲观锁

悲观锁的目的是通过使用锁来避免冲突
乐观锁允许发生冲突，但需要在写入时检测冲突。这可以使用物理时钟或逻辑时钟来完成。然而，由于逻辑时钟优于物理时钟，因此我们将使用一个版本列来捕获读取时间行快照信息，以实现并发控制/时钟机制

??悲观锁的缺点是，从事务中第一次访问资源到事务完成，资源一直处于锁定状态，在此期间，其他事务无法访问该资源。如果大多数事务只是简单地查看资源并且从不更改它，那么独占锁可能会过度消耗，因为它可能会导致锁争用，而乐观锁可能是一种更好的方法。通过悲观锁定，可以以故障安全的方式应用锁。在银行应用程序示例中，一旦在事务中访问一个帐户，该帐户就被锁定。尝试在锁定的其他事务中使用该帐户将导致另一个进程延迟，直到释放帐户锁，或者进程事务将回滚。锁一直存在，直到事务被提交或回滚。
??使用乐观锁定，事务首次访问资源时，资源实际上并没有锁定。相反，将保存资源用悲观锁定方法锁定时的状态。其他事务能够并发地访问资源，并且可能出现相互冲突的更改。在提交时，当资源即将在持久性存储中更新时，资源的状态将再次从存储中读取，并与首次在事务中访问资源时保存的状态进行比较。如果两种状态不同，则会执行冲突的更新，事务将被回滚。

锁的级别

类级别锁、对象级锁

对象级锁
??Java 中的每个对象都有一个唯一的锁。每当我们使用 synchronized 关键字时，只有锁的概念会出现在图片中。如果一个线程想要在给定的对象上执行那么 synchronized 方法。首先，它必须锁定该对象。一旦线程获得了锁，它就被允许在该对象上执行任何同步方法。方法执行完成后，线程自动释放锁。获取和释放锁在内部由 JVM 负责，而程序员不负责这些活动。
??它可以用于当你想要非静态的方法或非静态的代码块应该只被一个线程访问
类级别锁
??Java 中的每个类都有一个唯一的锁，这只不过是一个类级别的锁。如果一个线程想要执行一个静态同步方法，那么该线程需要一个类级别锁。一旦一个线程获得了类级别锁，那么它就可以执行该类的任何静态同步方法。方法执行完成后，线程自动释放锁。
??它可以用于当我们想要防止多个线程进入运行时上所有可用实例中的任何一个同步块。它应该始终用于使静态数据线程安全

死锁

??死锁产生的原因:1多个线程共享多个资源 2多个线程都需要其他线程的资源,每个线程又不愿或者无法放弃自己的资源(锁的开关无法人为控制)

??java 死锁产生的四个必要条件：

1. 互斥使用，即当资源被一个线程使用(占有)时，别的线程不能使用
2. 不可抢占，资源请求者不能强制从资源占有者手中夺取资源，资源只能由资源占有者主动释放。
3. 请求和保持，即当资源请求者在请求其他的资源的同时保持对原有资源的占有。
4. 循环等待，即存在一个等待队列：P1占有P2的资源，P2占有P3的资源，P3占有P1的资源。这样就形成了一个等待环路。

??当上述四个条件都成立的时候，便形成死锁。当然，死锁的情况下如果打破上述任何一个条件，便可让死锁消失。
??首先，我们应该避免为一个线程获取多个锁的需要。但是，如果一个线程确实需要多个锁，我们应该确保每个线程以相同的顺序获取锁，以避免锁获取中的循环依赖关系。
??我们还可以使用计时锁尝试，比如 Lock 接口中的 tryLock 方法，以确保如果一个线程无法获得锁，它不会无限制地阻塞。

读写锁

ReadWriteLock也是一个接口，在它里面只定义了两个方法：

public   interface   ReadWriteLock { 
      Lock readLock();   
      Lock writeLock(); 
} 

??一个用来获取读锁，一个用来获取写锁。也就是说将文件的读写操作分开，分成2个锁来分配给线程，从而使得多个线程可以同时进行读操作。
??ReadWriteLock是一个接口，ReentrantReadWriteLock是它的实现类，该类中包括两个内部类ReadLock和WriteLock，这两个内部类实现了Lock接口。
??ReentrantReadWriteLock里面提供了很多丰富的方法，不过最主要的有两个方法：readLock()和writeLock()用来获取读锁和写锁。
??读锁：如果没有线程请求写锁和写锁，那么多个线程可以锁定该锁进行读取。这意味着，只要没有线程写入数据或更新数据，多个线程就可以立即读取数据
??写锁：如果没有线程进行写或读操作，则每次只有一个线程可以锁定锁以进行写操作。其他线程必须等待，直到锁被释放。这意味着，此时只有一个线程可以写入数据，其他线程必须等待

锁池和等待队列

??在 java 中，每个对象都有两个池，一个锁池和一个等待池。
??锁定池: 假设线程 a 已经锁定了对象(注意: 不是类) ，而其他线程想调用对象的同步方法(或同步块) ，因为这些线程正在进入对象的同步方法。在获得对象锁的所有权之前，但是对象的锁当前为线程 a 所有，因此这些线程进入对象的锁池。
??等待池: 假设一个线程 a 调用一个对象的 wait ()方法，线程 a 释放对象的锁(因为 wait ()方法必须在 synchronized 中出现，所以在执行 wait ()方法之前自然而然地，线程 a 已经拥有对象的锁，线程 a 进入对象的等待池。如果另一个线程调用同一个对象的 notifyAll ()方法，那么该对象等待池中的线程都将进入该对象的锁池，准备竞争该锁的所有权。如果另一个线程调用相同对象的 notify ()方法，那么对象的等待池中只有一个线程(随机)进入对象的锁池。

关注博主即可阅读全文