android数据结构

基本数据结构：
数组、链表、栈、队列
栈：LIFO 压栈出栈，只允许在栈顶操作
队列：FIFO ，一般只允许队尾插，队首取，可以查看队头和队尾的数据，双端队列，两头都能插和取。

java：list、queue、map、set

1. list：有序存储，可以根据下标获取值 arraylist数组实现、linkedlist链表实现（双向的）
   Vector、ArrayList、LinkedList、
2. queue队列：
   deque（双端队列的接口继承了queue）、ArrayDeque、LinkedList
   BlockingQueue(阻塞队列接口，继承queue)
3. map：hashmp：数组加链表、treemap：红黑树存储、ArrayMap完整hash两个数组1:2
   hashmap、linkedhashmap、treemap、hashtable
4. 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。

---