基本数据结构：
数组、链表、栈、队列
栈：LIFO 压栈出栈，只允许在栈顶操作
队列：FIFO ，一般只允许队尾插，队首取，可以查看队头和队尾的数据，双端队列，两头都能插和取。
java：list、queue、map、set
- list：有序存储，可以根据下标获取值 arraylist数组实现、linkedlist链表实现（双向的）
Vector、ArrayList、LinkedList、 - queue队列：
deque（双端队列的接口继承了queue）、ArrayDeque、LinkedList
BlockingQueue(阻塞队列接口，继承queue) - map：hashmp：数组加链表、treemap：红黑树存储、ArrayMap完整hash两个数组1:2
hashmap、linkedhashmap、treemap、hashtable - set：hashset用hashmap实现，key为set的值，value为同一个值PRESENT。 treeset：treemap实现
阻塞队列：
| 存 | 取 | 备注 |
|---|---|---|
| boolean put | E take | 阻塞 |
| boolean offer | E poll | 若满了/空了直接返回false/null |
| boolean add | - | 调用了offer返回false改成抛异常 |
Vector：数组实现，扩展1.5倍 +1
ArrayList：默认10，扩展1.5倍 +1
Map
hashtable：方法全加锁，也是数组家链表实现，类似HsahMap
ArrayMap: 不安全，性能比Hashmap好
两个数组，A数组存放key的完整hashcode，有序存放的，二分查找插入，B数组存放value，长度为A的2倍，put时A数组根据key的hashcode按大小二分查找找出位置index存放，然后B数组2*index位置和2*index+1位置存放真正的key和valu
couurenthashmap：
key，hash 和 next 域都被声明为 final 型，value 域被声明为 volatile 型.由于 HashEntry 的 next 域为 final 型，所以新节点只能在链表的表头处插入
hashmap：数组加列表的方式存储，java8以后某位置存储超过8以后会变为红黑树存储。
散列：先对key hashcode，然后hashcode的高16位和低16位异或运算，保留更多细节，再与数组长度-1，比如15，进行与运算，然后得到一个小于数组长度的散列值。就是要放的桶。
扩容：
LinkedHashMap:继承Hashmap，在Node上多增加了俩节点：before和after
（默认Node自带一个next节点，因为hashmap在桶里是链表存放的。），形成一个循环/双向链表用来记录顺序，默认添加一个空的head，head前面的是最前面的，head后面的哪一位是最后的。accessOrder默认false为插入顺序，设为true就是访问顺序。
List:
Vector：数组实现，j加锁的 扩展1.5倍 +1
ArrayList：扩展2倍
CopyOnWriteArrayList：
增删改查的时候创建新的数组并操作，完成后再将引用指向新的数组,适用于常迭代的情况。读不加锁、写加锁。
set:
CopyOnWriteArraySet：
内部使用了一个CopyOnWriteArrayList来使用
sparsearray：
key为int类型的情况，key一个int数组，value一个object数组，key是排好序的，插入的时候会通过二分查找再插入。
Queue
ArrayBlockingQueue，
维护了一个定长数组，这是一个常用的阻塞队列，采用ReentrantLock和两个条件。类似于生产者消费者模式
其他：
ForkJoinPool:继承自AbstractExecutorService
可以充分利用多核cpu的优势，把一个任务拆分成多个“小任务”，把多个“小任务”放到多个处理器核心上并行执行；当多个“小任务”执行完成之后，再将这些执行结果合并起来即可。
ArrayBlockingQueue vs LinkedBlockingQueue
ArrayBlockingQueue：
维护了一个定长数组，这是一个常用的阻塞队列，采用ReentrantLock和两个条件。类似于生产者消费者模式
/** Main lock guarding all access */
final ReentrantLock lock;
/** Condition for waiting takes */
private final Condition notEmpty;
/** Condition for waiting puts */
private final Condition notFull;
LinkedBlockingQueue：
使用链表方式实现，采用了两把锁，因为take的时候从头部取，put的时候往尾部插，所以可以用take锁和put锁。
/** Lock held by take, poll, etc */
private final ReentrantLock takeLock = new ReentrantLock();
/** Wait queue for waiting takes */
private final Condition notEmpty = takeLock.newCondition();
/** Lock held by put, offer, etc */
private final ReentrantLock putLock = new ReentrantLock();
/** Wait queue for waiting puts */
private final Condition notFull = putLock.newCondition();
ArrayBlockingQueue中放入数据阻塞的时候，需要消费数据才能唤醒。而LinkedBlockingQueue中放入数据阻塞的时候，因为它内部有2个锁，可以并行执行放入数据和消费数据，不仅在消费数据的时候进行唤醒插入阻塞的线程，同时在插入的时候如果容量还没满，也会唤醒插入阻塞的线程。
ConcurrentHashmap
参考1.7原理
transient关键字只能修饰变量，而不能修饰方法和类。注意，局部变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。
ConcurrentHashMap:
此处怎么会存在键值对存在且的Value值为null的情形呢？JDK官方给出的解释是，这种情形发生的场景是：初始化HashEntry时发生的指令重排序导致的，也就是在HashEntry初始化完成之前便返回了它的引用。这时，JDK给出的解决之道就是加锁重读，源码如下：
ConcurrentHashMap计算size
private transient volatile CounterCell[] counterCells;
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
阻塞队列：BlockingQueue
| 存 | 取 | 备注 |
|---|---|---|
| boolean put | E take | 阻塞调用 |
| boolean offer、add | E poll、remove | 非阻塞，前者不抛异常，后者抛，后者实际上调用了前者 |
添加：
- boolean offer(E e):不会阻塞
加锁，判断，队列满了直接返回false，否则入队列并返回true，finally解锁 - boolean add(E e)：直接调用offer方法，offer返回false的话抛异常
- void put(E e) throws InterruptedException：阻塞方法
获取
- E poll()：不阻塞 返回null 或者数据
- Eremove() :调用的poll方法，返回null抛异常。
- E take() throws InterruptedException：阻塞调用，加锁，判断有无数据，返回
其他方法：
- E peek()：返回队列头元素，但不会移除，只是拿到引用
peek偷窥一下的意思 - element() ：同上，调用了peek方法，返回null的话抛异常
说明：
1、add()和offer()区别: add调用offer抛异常
add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！
2、poll()和remove()区别：remove调用poll方法抛异常
remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。
3、element() 和 peek() 区别：element调用peek方法抛异常
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。
网友评论