集合

ArrayList & Linkedlist

首先,他们的底层数据结构不同, Arraylist底层是基于数组实现的, Linkedlist底层是基于链表实现的
由于底层数据结构不同,他们所适用的场景也不同, Arraylist更适合随机查找, Linkedlist更适合删除和添加,查询、添加、删除的时间复杂度不同
另外 Arraylist和 Linkedlist都实现了List接口,但是 Linkedlist还额外实现了 Deque接口,所以nkedlist还可以当做队列来使用

CopyonwriteArraylist

首先 Copyon Arraylist内部也是用过数组来实现的,在向 Copyonwritearraylist添加元素时,会复制一个新的数组,写操作在新数组上进行,读操作在原数组上进行2.并且,写操作会加锁,防止岀现并发写入丢失数据的问题3.写操作结束之后会把原数组指向新数组4.Coρyoη Writearraylist允许在写操作时来读取数据,大大提高了读的性能,因此适合读多写少的应用场景,但是 Copyη Writearray List会比较占内存,同时可能读到的数据不是实时最新的数据,所以不适合实时性要求很高的场景

Map

hashtable *

线程安全，低效，不支持null

底层是通过在 put、get 操作上添加 synchronized 实现的，因为 put、get 操作都 synchronized ，所以效率最低。

public synchronized V put(K key, V value) {}
public synchronized V get(Object key) {}
public synchronized V remove(Object key) {}

散列算法影响速度，采用最简单的取余运算

int index = (hash & 0x7FFFFFFF) % tab.length;

Hash冲突算法采用链表的方式，通过entry的结构可以看出

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
}

使用

@Test
public void test(){
    Hashtable<String, String> hashtable = new Hashtable();
    hashtable.put("test", "test-val");
    System.out.println(hashtable.get("test"));
}

hashmap *

特点：HashMap非线程安全，高效，支持null；

概念

负载因子（loadFactor）：扩容系数，使用的节点数/总节点数>loadFactor，进行扩容

阈值：需要扩容的值

Jdk1.7结构

entry数组+链表（解决hash冲突的问题）

jdk1.8结构

entry数组+链表（解决节点数量小于8的hash冲突）+红黑树（解决节点数量大于8的hash冲突）

put方法

步骤：

判断entry数组是否存在，不存在，通过resize操作创建数组，默认大小是16
根据hash计算节点的位置，判断是否为null，如果为null，则重新创建节点
判断节点是否相同（判断内容：key的hash值，key的内容和地址），相同，保存查询出来的旧节点
判断节点是否是TreeNode，如果是向Tree树添加节点
处理链表，循环判断next是否有非空节点
1. 如果为null，追加新节点；追加新节点后判断链表节点数量是否转换成红黑树
2. 如果不为空，判断key，相同保存查询出来的旧节点
判断数量是否超过根据负载因子计算出来的数量，如果超过，则扩容

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	//初始化操作，如果数组为空或长度为0，扩容
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	//通过就算，如果计算出的位置上没有值，创建新的节点
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	//到这步操作，说明计算的位置上已经有值
	else {
		Node<K,V> e; K k;
		//如果当前位置的节点跟插入的节点key相同，赋值（此处只有单个节点）
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		//如果当前节点是红黑树的节点，调用红黑树的插入方法
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		//进入这步说明此处的数据结构是链表
		else {
			//遍历链表
			for (int binCount = 0; ; ++binCount) {
				//如果没有相等的元素
				if ((e = p.next) == null) {
					//追加新元素到链表的最后面
					p.next = newNode(hash, key, value, null);
					//static final int TREEIFY_THRESHOLD = 8; 如果大小超过8，链表转红黑树
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				//如果有相等的元素
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		//如果查出的节点值不为空，进行value的更新操作
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	//如果新插叙的值大于阀值（允许的最大值），进行扩容操作
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);
	return null;
}

get方法

判断entry是否为null，为null，直接返回
根据hash计算节点的位置，判断key的hash和key的值是否相同，相同，返回节点
不同，判断是否有next节点
1. 判断是否是TreeNode，调用TreeNode节点的get方法
2. 链表的next查找

final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	//如果数组不为空和长度不为0继续查找
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		//如果查找到的hash值和计算的hash值相同，key也相同，返回节点（单个元素的情况）
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		//如果当前位置有多个元素（链表+红黑树）
		if ((e = first.next) != null) {
			//如果是红黑树，调用红黑树方法
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			//如果是链表，遍历lianbiao
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

resize方法

1.7 扩容方法 *

判断是否扩容，如果满足条件，阀值和容量扩大两倍
先生成新数组
遍历老数组中的每个位置上的链表上的每个元素
取每个元素的key,并基于新数组长度,计算出每个元素在新数组中的下标
将元素添加到新数组中去
所有元素转移完了之后,将新数组斌值给 Hashmap对象的 Stable属性

1.8 扩容方法 *

判断是否扩容，如果满足条件，阀值和容量扩大两倍
先生成新数组
遍历老数组中的每个位置上的链表或红黑树
如果是链表,则直接将链表中的每个元素重新计算下标,并添加到新数组中去
如果是红黑树,则先遍历红黑树,先计算出红黑树中每个元素对应在新数组中的下标位置
a. 统计每个下标位置的元素个数
b. 如果该位置下的元素个数超过了8,则生成一个新的红黑树,并将根节点的添加到新数组的对应位置
c.如果该位置下的元素个数没有超过8,那么则生成一个链表,并将链表的头节点添加到新数组的对应位置
所有元素转移完了之后,将新数组赋值给 Hashmap对象的 Itable属性

判断是否扩容，如果满足条件，阀值和容量扩大两倍
将节点放到新的entry数组中
1. 普通节点，直接赋值
2. 树节点，需要拆分
3. 链表节点，这里使用了巧妙的方法，通过e.hash & oldCap来得出newTab中的位置，因为table是2倍扩容，所以只需要看hash值与oldCap进行与操作，结果为0，那么还是原来的index；否则index = index + oldCap 参考地址
  在遍历oldTab上的链表时进行了 (e.hash & oldCap) == 0 的判断，如果成立则索引位置不变，如果不成立则新的索引位置为： index = index + oldCap，如上面流程图中最右边部分的循环图示。接下来我们就来证明一下为什么上面的计算方式是正确的，首先明白三个计算原则： 1.table的容量始终是2^x，每次扩容都是扩容为原有的2倍（特殊情已经在流程中过滤） 2.hash的运算：在HashMap中是使用了移位运算，h = key.hashCode()) ^ (h >>> 16)，即高16位和低16位进行亦或运算（“>>>”符号是无符号右移，忽略符号位，空位都以0补齐） 3.索引的计算公式为(n - 1) & hash，相当于取模运算 hash % n (注：这里的n为table的容量，具体原理可以参考博客) 对于二进制运算在这里我们就用符号"..."代替不重要的低位上的数了，高位我们用0补齐。这里我们设置 oldCap = 2^x，我们用二进制表示 oldCap = 00000000 1(第x+1位) 000....000 (1后面一共x个0，即低x位都为0) 根据第三条计算原带入x计算原索引：index = (2^x - 1) & hash 计算结果：index = 00000000 0(第x + 1位) ..........(低x位) ；那么 newCap = oldCap * 2 = 2^(x +1)，扩容后新索引为：newIndex = (2^(x + 1) - 1) & hash 则索引结果无非就是两种：在二进制中的 x+1 位不是0就是1 第一种结果：newIndex = 0000000 0(第x + 2位) 1 (第x + 1位) .........(低x位) 第二种结果：newIndex = 0000000 0(第x + 2位) 0 (第x + 1位) .........(低x位) 到这里我们就可以知道如果是第 x + 1 位是0那么和index的值就是一样的。如果第 x + 1 位是1那么得到： newIdex = index + oldCap 即：0000000 0(第x + 2位) 1 (第x + 1位) .........(低x位) = 00000000 0(第x + 1位) ..........(低x位) + 00000000 1(第x+1位) 000....000 所以得到必然的结果就是新索引要么与原索引相同要么就是原索引加上原容量值得到新索引。但是这还不足以解释为什么 (e.hash & oldCap) == 0 就可以判断新索引与原索引不变。细心点你可以发现(e.hash & oldCap) = hash & 2^x，这个式子相当于 hash & 0000000 1(第x+1位) 000....000 (1后面一共x个0，即低x位都为0) 这里可以发现和求新索引的计算式很像： hash & (2^(x+1) -1)，实际上就是将后面的低x位全部换成0，只需关心第x+1位进行hash运算后的值。这里我们得到了我们想要的结论： hash & oldCap = 0，代表的就是第x + 1位上的值位0，hash & oldCap = 1，代表x + 1位上的值为1。再根据前面的结论: x + 1 位为0时，newIndex = index；x + 1位为1时， newIndex = index + oldCap。所以最后得出： (e.hash & oldCap) == 0，newIndex = index；(e.hash & oldCap) != 0, newIndex = index + oldCap

死循环：

【问hashmap为什么会形成链表？为什么会出现cpu100%的情况？】

原因：

并发扩容
扩容采用的头插法（1.6以前），会形成链表的倒置

过程：

假如有一个链表如下图，此时有两个线程在进行扩容

线程1刚要进行扩容，但失去了cpu时间片，但是此时线程2抢占到了cpu的执行权，完成了扩容操作，结果如图上所示
导致形成环形链表的代码，问题出在resize方法的transfer方法上

void transfer(Entry[] newTable)

{

    Entry[] src = table;

    int newCapacity = newTable.length;

    //下面这段代码的意思是：

    //  从OldTable里摘一个元素出来，然后放到NewTable中

    for (int j = 0; j < src.length; j++) {

        Entry<K,V> e = src[j];

        if (e != null) {

            src[j] = null;

            do {

                **Entry<K,V> next = e.next;**

                **int i = indexFor(e.hash, newCapacity);**

                **e.next = newTable[i];**

                **newTable[i] = e;**

                **e = next;**

            } while (e != null);

        }

    }

}

三次的循环导致问题

（1）第一次：

e = 3，next = 7
e.next = 3.next = new[3] = null
new[3] = e = 3
e = next = 7

（2）第二次：

e = 7, next = 3
e.next = 7.next = new[3] = 3
new[3] = 7
e = next = 3

（3）第三次：

e = 3，next = null
e.next = 3.next = new[3] = 7
new[3] = 3
e = next = null

（4）形成环形链表，3.next = 7,7.next = 3

形成环形链表后，当进行put操作，如果put操作落到了环形链表，则会形成死循环，cpu100%；当进行get操作，如果get操作落到了环形链表，并且get的key在环形链表中不存在时，则会形成死循环，cpu100%。

位运算

计算hash的时候位移操作

高16位异或低16位的“扰动函数”，减小碰撞的几率，增大随机性

大小是2的n次幂

2^n 的二进制
- 2^1 = 10
- 2^2 = 100
- 2^3 = 1000
- 2^n = 1(n个零)
2^n - 1
- 2^1 -1 = 01
- 2^2 -1 = 011
- 2^3 -1 = 0111
- 2^n -1 = 0(n个1)

当 length = 2^n 的时候， h & (length -1)的结果，就是 0 ~ (length -1) 之间的数值，就是相当于 h % length 的结果，而当length != 2^n 的时候，这个特点不成立

HashMap中的数据结构是数组+单链表的组合，我们希望的是元素存放的更均匀，最理想的效果是，Entry数组中每个位置都只有一个元素，这样，查询的时候效率最高，不需要遍历单链表，也不需要通过equals去比较K，而且空间利用率最大。那如何计算才会分布最均匀呢？我们首先想到的就是%运算，哈希值%容量=bucketIndex

红黑树

红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。加快检索速率。

其他

1、HashMap和HashTable的区别

Hashtable是早期提供的接口，HashMap是新版JDK提供的接口。
Hashtable继承Dictionary类，HashMap实现Map接口。
Hashtable线程安全，HashMap线程非安全。
Hashtable不允许null值，HashMap允许null值。

ConcurrentHashMap *

ConcurrentHashMap的结构

1.7：采用了分段锁，Segment 数组+hashentry数组
1.8：采用了节点锁，entry数组+链表+红黑树，节点是数组的每一个元素，节点有可能是链表的头节点或者是红黑树的根节点

原理

1.7
- 明确hashentry数组大小的定义，大小只能为1或者是2的n次幂。例如初始化容量是15，默认并发级别16，则entry的初始化大小是1，15/16<0；初始化容量是33，默认并发级别16，则entry的初始化大小是4，2<33/16<4；
- get操作没有使用锁，两次的散列算法，定位到hashentry中具体的节点，通过volatile的修饰，保证拿到的值一直是最新的。
- put操作需要注意的是它会初始化Segment中的hashentry数组，采用cas操作，保证只有一个线程可以操作成功
  - put 方法会通过tryLock()方法尝试获得锁，成功操作节点；失败，自旋等待获得锁，次数达到上限，会通过lock方法获得锁。
- rehash方法，该方法扩容的是hashentry数组数组【注意：Segment数组初始化大小后，不再改变】。这里也是使用了一个特性，扩容的大小是2倍，扩容后节点之可能在原来的位置i，或i+oldcap（原来的容量）
- 注意点
  - 并发级别的定义，定义小了，会导致Segment的锁竞争激烈。定义大了本来位于同一个Segment的元素却被散列到不同的Segment元素中，cpu cache的命中率降低。
  - 弱一致性，虽然采用volatile修饰变量保证了获取到的值一直是最新的，但因为是并发操作，get和containkey有可能获取到的值是过时的。
  - 应该避免在多线程环境下使用size和containsValue 方法。因为他们是现计算的，计算两次判断是否相同，相同则返回；不同则锁住所有的Segment，进行统计。
1.8
- 改进：
  - 取消segments 字段，采用table 数组元素作为锁，从而实现了缩小锁的粒度，进一步减少并发冲突的概率，并大量采用了CAS（底层的一些核心方法） + synchronized 来保证并发安全性
  - 结构的改变，保证hash冲突后链表过长导致查询效率低，链表o(n)，红黑树，logN。当链表长度大于8，转红黑树；当红黑树长度小于6，转链表
- 重要的变量
  - ForwardingNode，特殊的node节点，用于扩容的时候表示节点为null或者已经被移动
  - sizectl
    - -1：正在初始化
    - -N：有n-1个线程正在扩容
    - 0：没有初始化
    - > 0：阈（yu）值，达到该值需要进行扩容
- get方法与hashmap的方法大致相同，三种情况的取值
- put方法
  - 节点为空，cas操作放入节点
  - 如果正在扩容，当前线程帮助扩容
  - 锁节点（链表的头节点【尾插法】、红黑树的根节点），最后判断是否需要链表转红黑树
- 扩容transfer
  - 并发扩容其实就是将数据迁移任务拆分成多个小迁移任务，在实现上使用了一个变量stride 作为步长控制，每个线程每次负责迁移其中的一部分。
  - 类型
    - 为null 或者已经处理过的节点，会被设置为forwardNode 节点，当线程准备扩容时，发现节点是forwardNode 节点，跳过这个节点，继续寻找未处理的节点，找到了，对节点上锁，
    - 如果这个位置是Node 节点（fh>=0），说明它是一个链表，就构造一个反序链表，把他们分别放在nextTable 的i 和i+n 的位置上
    - 如果这个位置是TreeBin 节点（fh<0），也做一个反序处理，并且判断是否需要红黑树转链表，把处理的结果分别放在nextTable 的i 和i+n 的位置上
- size方法是实时统计的
  - 对baseCount 做CAS 自增操作。
  - 如果并发导致baseCount CAS 失败了，则使用counterCells。
  - 如果counterCells CAS 失败了，在fullAddCount 方法中，会继续死循环操作，直到成功。

扩容*

1.7 扩容

1.7版本的 Concurrenthash Map是基于 Segment分段实现的
每个 Segment相对于一个小型的 Hashmap
每个 Segment内部会进行扩容,和 Hash Map的扩容逻辑类似
先生成新的数组,然后转移元素到新数组中
扩容的判断也是每个 Segment内部单独判断的,判断是否超过阈值

1.8 扩容

1.8版本的 Concurrenthash Map不再基于 Segment实现
当某个线程进行pu时,如果发现 Concurrenthashmap正在进行扩容那么该线程一起进行扩容
如果某个线程put时,发现没有正在进行扩容,则将key-vaue添加到 Concurrenthashmap中,然后判断是否超过阈值,超过了则进行扩容
Concurrenthashmap是支持多个线程同时扩容的
扩容之前也先生成一个新的数组
在转移元素时,先将原数组分组,将每组分给不同的线程来进行元素的转移,每个线程负责一组或多组的元素转移工作

阻塞队列

ArrayBlockingQueue:一个由数组结构组成的有界阻塞队列,线程池,生产者消费者
LinkedBlockingQueue:一个由链表结构组成的无界阻塞队列,线程池,生产者消费者
PriorityBlockingqueue:一个支持优先级排序的无界阻塞队列,可以实现精确的定时任务
Delayqueue:一个使用优先级队列实现的无界阻塞队列,可以实现精确的定时任务
Synchronousqueue:一个不存储元素的阻塞队列,线程池
LinkedTransferqueue:一个由链表结构组成的无界阻塞队列
LinkedBlockingDeque:一个由链表结构组成的双向无界阻塞队列,可以用在“工作窃取"模式中