java 数据容器 笔记

图预览

顶层接口分别是Collection和Map。
但是这2个接口都不能直接被实现使用，分别代表两种不同类型的容器

Collection

Collection代表的是单个元素对象的序列
可以有序/无序,可重复/不可重复等
具体依据具体的子接口Set,List,Queue等

• List:元素可以重复,特殊的iterator遍历器(ListIterator)
• Set:元素不可以重复
• Queue

public interface Collection<E> extends Iterable<E> {
    add(E e) 
    clear()
    contains(Object o)
    isEmpty()
    iterator()
    remove(Object o)
    retainAll(Collection<?> c)
    size()
    toArray()
    toArray(T[] a)
}

List

常用实现类:

• ArrayList(数组实现,允许插入null)

size, isEmpty, get, set, iterator,add这些方法的时间复杂度是O(1)
add n个数据则时间复杂度是O(n).

• LinkedList(链表实现)

  • 查找方面:数组的效率更高,可以直接索引出查找,而链表必须从头查找。
  • 插入删除方面:特别是在中间进行插入删除,只需要在插入或者删除的地方断掉链然后插入或者移除元素,然后再将前后链重新组装,但是数组必须重新复制一份将所有数据后移或者前移。
  • 在内存申请方面,当数组达到初始的申请长度后,需要重新申请一个更大的数组然后把数据迁移过去才行,而链表只需要动态创建即可

同时LinkedList还实现了Deque接口,Deque接口是继承Queue的,所以LinkedList还支持队列的pop，push，peek操作。

• Vector(线程安全,每个方法体都有sychronized)

所有的API都是synchronized

List实现	使用场景	数据结构
ArrayList	数组形式访问List链式集合数据，元素可重复，访问元素较快	数组
LinkedList	链表方式的List链式集合，元素可重复，元素的插入删除较快	双向链表
Vector	所有的API都是synchronized,ArrayList的线程安全版	数组

ArrayList

transient Object[] elementData;
private int size;
public boolean add(E e) {
//每次add的时候会判断数据长度，如果不够的话会调用Arrays.copyOf，复制一份更长的数组，并把前面的数据放进去。
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}


public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
//System.arraycopy把需要删除index后面的都往前移一位然后再把最后一个去掉    
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

LinkedList

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

transient int size = 0;
//一个双向链表
transient Node<E> first;
transient Node<E> last;
//最基本的插入和删除的链表操作
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
    
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

Set

常用实现:

• HashSet(内部维护了Map的HashMap来实现)
• LinkedHashSet(核心概念相对于HashSet来说就是一个可以保持顺序的Set集合)
• TreeSet(内部维护了Map的TreeMap实现)

Set实现	使用场景	数据结构
HashSet	无序的、无重复的数据集合	基于HashMap
LinkedSet	维护次序的HashSet	基于LinkedHashMap
TreeSet	保持元素大小次序的集合，元素需要实现Comparable接口	基于TreeMap

HashSet

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

public void clear() {
    map.clear();
}
//所有的add，remove等操作其实都是HashMap的add、remove操作。遍历操作其实就是HashMap的keySet的遍历

Queue

boolean add(E e);   //利用offer增加一个元素,如果队列已满，则抛出一个IIIegaISlabEepeplian异常
boolean offer(E e); //添加一个元素并返回true,如果队列已满，则返回false,普通队列内部用enqueue
boolean offer(E e, long timeout, TimeUnit unit)  //添加一个元素并返回true,如果队列已满等待一会再重试失败再返回false

//BlockingQueue接口新增
void put(E e) throws InterruptedException;  //添加一个元素 如果队列满，则notFull阻塞


E remove();     //利用poll移除并返回队列头部的元素,如果队列为空，则抛出一个NoSuchElementException异常
E poll();       //移除并返问队列头部的元素,如果队列为空，则返回null，普通队列内部用了dequeue
E poll(long timeout, TimeUnit unit) throws InterruptedException  //移除并返问队列头部的元素,如果队列为空notEmpty.awaitNanos(nanos)再重试失败则返回null

//BlockingQueue接口新增
E take() throws InterruptedException;   //移除并返回队列头部的元素,如果队列为空，则notEmpty阻塞


E element();    //利用peek()返回队列头部的元素不删除,如果队列为空，则抛出一个NoSuchElementException异常
E peek();   //返回队列头部的元素不删除,如果队列为空，则返回null

ArrayBlockingQueue

基于数组的有界阻塞队列实现,操作带ReentrantLock
在ArrayBlockingQueue中,维护了一个内部定长的数组,以便缓存队列中的数据对象
其内部也没有实现读写分离,也就意味着生产和消费端不能完全并行,长度需要定义
可以指定先进先出也可以指定先进后出,也叫有界队列,在很多场合下很适用

final ReentrantLock lock;

private final Condition notEmpty;

private final Condition notFull;

LinkedBlockingQueue

基于链表的无界阻塞队列实现,操作带ReentrantLock
同ArrayBlockingQueue类似,内部维护着一个数据缓冲队列(该队列基于一个链表实现)
LinkedBlockingQueue之所以能够高并发的处理数据,是因为内部维护了一个采用分离锁
读写分离两个锁

• takeLock 读锁
• putLock 写锁
  从而实现生产和消费并行运行,他是一个无界队列

private final ReentrantLock takeLock = new ReentrantLock();

private final Condition notEmpty = takeLock.newCondition();

private final ReentrantLock putLock = new ReentrantLock();

private final Condition notFull = putLock.newCondition();

PriorityBlockingQueue

基于数组优先级的无界阻塞队列,操作带ReentrantLock
(优先级的判断通过构造函数传入的Compator对象来决定,也就是说传入的对象必须实现了Comparable接口)
在实现PriorityBlockingQueue时,内部控制线程同步的锁是公平锁,他也是一个无界队列

class Task implements Comparable<Task>{
    private int id;
    private String name;
    @Override
    public String toString() {
        return "Task{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public Task(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int compareTo(Task task) {
        return this.id > task.id ? 1:0;
    }
}

public class priorityblockingqueue {
    public static void main(String[] args) {
        PriorityBlockingQueue<Task> q = new PriorityBlockingQueue<>();
        q.add(new Task(1, "张三"));
        q.add(new Task(2, "李四"));
        q.add(new Task(3, "王五"));

        for (int i=q.size();i>0;i--){
            Task task = q.poll();
            System.out.println(task.toString());
        }
    }
}
//Task{id=1, name='张三'}
//Task{id=3, name='王五'}
//Task{id=5, name='李四'}

poll方法

/**
 * @By Vicky:出队一个元素
 */
public E poll() {
    // size==0队列为0，直接返回null
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    // 出队总是将数组的第一个元素进行出队，
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        // 同时将队列的最后一个元素放到第一个位置，然后自上而下调整堆
        siftDown(0, x);
    return result;
}

/**
 * @By Vicky:自下而上调整堆
 */
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

/**
 * @By Vicky:自下而上调整堆
 */
private void siftDownUsingComparator(int k, E x) {
    // 由于堆是一个二叉树，所以size/2是树中的最后一个非叶子节点
    // 如果k是叶子节点，那么其无子节点，则不需要再往下调整堆
    int half = size >>> 1;
    while (k < half) {
        // 左节点，固定规则
        int child = (k << 1) + 1;
        Object c = queue[child];
        // 右节点
        int right = child + 1;
        // 找出两个子节点以及父节点中较小的一个
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        // 如果父节点最小，则无需继续往下调整堆
        if (comparator.compare(x, (E) c) <= 0)
            break;
        // 否则将父节点与两个子节点中较小的一个交换，然后往下继续调整
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

DelayQueue

带有延迟时间的PriorityQueue,操作带ReentrantLock
其中的元素只有当指定的延迟时间到了,才能获取其中的元素,DelayQueue必须实现Delayed接口
DelayedQueue是一个没有大小限制的队列,应用场景很多,比如对缓存超时的数据进行移除,任务超时处理,空闲连接的关闭等等

• 可重入锁
• 用于根据delay时间排序的优先级队列
• 用于优化阻塞通知的线程元素leader
• 用于实现阻塞和通知的Condition对象

DelayQueue = BlockingQueue + PriorityQueue + Delayed

public interface Comparable<T> {
    public int compareTo(T o);
}

public interface Delayed extends Comparable<Delayed> {
    long getDelay(TimeUnit unit);
}

public class DelayQueue<E extends Delayed> implements BlockingQueue<E> { 
    private final PriorityQueue<E> q = new PriorityQueue<E>();
}

示例

class Data implements Delayed {

    private Data(Builder builder) {
        time = builder.time;
        name = builder.name;
    }

    @Override
    public String toString() {
        return "Data{" +
                "time=" + time +
                ", name='" + name + '\'' +
                '}';
    }



    @Override
    public long getDelay(TimeUnit unit) {
        return unit.convert(this.time - System.nanoTime(), TimeUnit.NANOSECONDS);
    }

    @Override
    public int compareTo(Delayed o) {
        return this.getDelay(TimeUnit.SECONDS) > o.getDelay(TimeUnit.SECONDS)? 1: 0;
    }

    private long time;
    private String name;


    public static final class Builder {
        private long time;
        private String name;

        public Builder() {
        }

        public Builder time(int val) {
            time = TimeUnit.NANOSECONDS.convert(val, TimeUnit.MILLISECONDS) + System.nanoTime();
            return this;
        }

        public Builder name(String val) {
            name = val;
            return this;
        }

        public Data build() {
            return new Data(this);
        }
    }
}

public class MyDelayedQueue {

    private static DelayQueue<Data> queue = new DelayQueue<>();

    public static void main(String[] args) throws InterruptedException {
        Data data1 = new Data.Builder()
                .name("张三")
                .time(1000).build();
        Data data2 = new Data.Builder()
                .name("李四")
                .time(3000).build();
        queue.offer(data1);
        queue.offer(data2);
        Data result = null;
        while (null != (result = queue.take())){
            System.out.println(result);
        }

    }
}
//Data{time=105335615627085, name='张三'}
//Data{time=105337616479560, name='李四'}

offer方法

DelayQueue内部的实现使用了一个优先队列。当调用DelayQueue的offer方法时，把Delayed对象加入到优先队列q中。

public boolean offer(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E first = q.peek();
        q.offer(e);
        if (first == null || e.compareTo(first) < 0)
            available.signalAll();
        return true;
    } finally {
        lock.unlock();
    }
}

take方法

DelayQueue的take方法，把优先队列q的first拿出来（peek），如果没有达到延时阀值，则进行await处理。

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        for (;;) {
            E first = q.peek();
            if (first == null) {
                available.await();
            } else {
                long delay =  first.getDelay(TimeUnit.NANOSECONDS);
                if (delay > 0) {
                    long tl = available.awaitNanos(delay);
                } else {
                    E x = q.poll();
                    assert x != null;
                    if (q.size() != 0)
                        available.signalAll(); // wake up other takers
                    return x;

                }
            }
        }
    } finally {
        lock.unlock();
    }
}

SynchronousQueue

一种没有缓存的队列,生产者生产的数据直接会被消费者获取并消费

SynchronousQueue<Integer> sc = new SynchronousQueue<>(); // 默认不指定的话是false，不公平的  
sc.take();// 没有元素阻塞在此处，等待其他线程向sc添加元素才会获取元素向下执行  
sc.poll();//没有元素不阻塞在此处直接返回null向下执行  
sc.poll(5,TimeUnit.SECONDS);//没有元素阻塞在此处等待指定时间，如果还是没有元素直接返回null向下执行

• 默认不公平,使用TransferStack,否则公平使用TransferQueue
• transfer(E e, boolean timed, long nanos) timed是否非阻塞,nanos等待时间

public boolean offer(E e) {
    if (e == null) throw new NullPointerException();
    return transferer.transfer(e, true, 0) != null;
}

public boolean offer(E e, long timeout, TimeUnit unit)
        throws InterruptedException {
    if (e == null) throw new NullPointerException();
    if (transferer.transfer(e, true, unit.toNanos(timeout)) != null)
        return true;
    if (!Thread.interrupted())
        return false;
    throw new InterruptedException();
}

public void put(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    if (transferer.transfer(e, false, 0) == null) {
        Thread.interrupted();
        throw new InterruptedException();
    }
}

ConcurrentLinkedQueue

我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法，另一种是使用非阻塞算法。
使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现，而非阻塞的实现方式则可以使用循环CAS的方式来实现
Doug Lea是如何使用非阻塞的方式来实现线程安全队ConcurrentLinkedQueue的以后会专开博文去解析集合的源码和实现原理

Map

public interface Map<K,V> {
    ...
    interface Entry<K,V> {
        K getKey();
        V getValue();
        ...
    } 
}

每个元素都是一个Key-Value键值对实现类

简介

TreeMap

- HashMap不保证数据有序
- LinkedHashMap保证数据可以保持插入顺序
- TreeMap可以保持key的大小顺序

就是利用了红黑树构建了TreeMap

HashMap(无序,以数组+链表/红黑树的方式进行存储)

存储方式-散列表(哈希表):像之前提到过的用数组存储
同数组小标用链表存储,链表长度超过8则用红黑树存储,退化到6则从红黑树转链表  
升级红黑树的时候如果数组的长度小于64则2次方扩容  
添加元素的时候如果所有的元素大小超过了threshold阈值(数组长度*0.75加载因子)则做如下几种情况的操作:

1:如果原来数组大小超过1 << 30,变更阈值就为0x7fffffff不做数组扩容
2:如果原来数组大小乘2扩容后还小于1 << 30,并且原数组长度大于1 << 4,则新数组扩容乘以2,新数组的阈值也乘2
3:如果原数组长度=0且原阈值>0,则新数组长度为原数组的阈值,新阈值为新长度*0.75f  
4:如果原数组长度=0且原阈值=0,则新数组长度为1 << 4,新阈值为0.75f*(1 << 4)


TreeNode继承LinkedHashMap的Entry,LinkedHashMap的Entry继承于HashMap.Node,HashMap数组就是HashMap.Node[]  

链表转红黑树先经过treeifyBin勘测是否要数组扩容
后取出数组下标的链表全部转treeNode
最后利用treeify排列红黑树

HashSet就是基于HashMap，只使用了HashMap的key作为单个元素存储

下标通过(n - 1) & hash锁定
hash通过(h = key.hashCode()) ^ (h >>> 16)得出

LinkedHashMap

继承与HashMap、底层使用HashMap一致的方式来保存所有元素。其基本操作与父类HashMap相似

LinkedHashMap的Entry继承于HashMap.Node

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

它通过继承重写Entry类,增加before和after以及head和tail来实现自己的链接列表特性。

WeakHashMap(适用于缓存,内存大对象情况,Entry被WeakReference包裹)

HashTable(线程安全,方法都是sychronized,除了HashTable都是通过AbstractMap)

• 数据结构:数组+链表形式,所有存取方法都加sychronized
• 下标寻找算法:(hash & 0x7FFFFFFF) % tab.length
• hash算法:int hash = key.hashCode();
• 检测扩容:元素大小是否超过阈值(0.75*数组长度)
• 扩容机制:新大小=(oldCapacity << 1) + 1,新阈值=新大小*0.75f

ConcurrentHashMap

ConcurrentHashMap

总结短语

Map集合提供3种遍历访问方法

1. 获得所有key的集合然后通过key访问value[keySet]
2. 获得value的集合[values]
3. 获得key-value键值对的集合[entrySet]

Map实现	使用场景	数据结构
HashMap	哈希表存储键值对,key不重复,无序	数组+(链表/红黑树)
LinkedHashMap	是一个可以记录插入顺序和访问顺序的HashMap	数组+(链表/红黑树)
TreeMap	具有元素排序功能	纯红黑树
WeakHashMap	弱键映射,映射之外无引用的键,可以被垃圾回收	数组+链表

HashMap

数据结构

HashMap底层是数组加单向链表或红黑树实现的(这是JDK 1.8,之前的版本纯粹是数组加单向链表实现)

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //用来定位数组索引位置
    final K key;
    V value;
    Node<K,V> next; //Node中存储key的hash,键值对,同时还有下一个链表元素    
    
    //省略一些代码

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}



//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//1<<4表示00001中的1向左移动了4位,变成了10000,换算成十进制就是2^4=16,Node[] table的初始化长度length(默认值是16)

//默认最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;


//默认链表转成红黑树的阈值,即使负载因子和Hash算法设计的再合理,也免不了会出现拉链过长的情况
//一旦出现拉链过长,则会严重影响HashMap的性能。于是在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。
//而当链表长度太长（默认超过8）时，链表就转换为红黑树
//利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法
static final int TREEIFY_THRESHOLD = 8;

//默认红黑树转为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;

//数组的长度，如果大于这个值会进行resize扩容数组操作
static final int MIN_TREEIFY_CAPACITY = 64;


//HashMap中实际存储的Node(键值对)的数量
transient int size;
//扩容阈值,所能容纳的key-value对极限,当size>=threshold时，就会扩容,根据loadFactor和capacity计算出来
int threshold;
//HashMap的负载因子
final float loadFactor;
//负载因子默认为0.75,当HashMap中存储的元素的数量大于(容量×加载因子),也就是默认大于16*0.75=12时,HashMap会进行扩容的操作。

关键参数

• size : HashMap中实际存在的键值对数量
• length&capacity : table的长度
• threshold : 负载因子,检测扩容限定数额
• TREEIFY_THRESHOLD : 当链表长度太长（默认超过8）时，链表就转换为红黑树
• modCount : 记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。内部结构发生变化指的是结构发生变化，如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

初始化方法

Map<K,V> map = new HashMap<K,V>();

调用HashMap的无参构造函数，令loadFactor等于0.75
在第一次put的时候，putVal函数调用resize函数初始化，设置initialCapacity为16

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
//首先判断初始容量是否小于0,如果小于0,会抛出异常    
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
//判断初始容量是否大于最大的容量(即2^31),如果大于,将初始容量设置为最大初始容量    
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
//判断加载因子:如果小于等于0,或者不是一个数字,都会抛出异常    
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
//threshold(阈值)=capacity*loadFactor    
}


static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}



cap=19
int n=cap-1;//得到n=18，换算为二进制为10010
n|=n>>>1;//表示n无符号右移一位后，与n按位或计算，其中n>>>1=01001，按位或结果为11011
n|=n>>>2;//其中n>>>2=00110,按位或的结果为11111，下面几步类似，最终得到的结果是n=11111(二进制，也就是2^5-1，31)
// >>> : 无符号右移只记住一点:忽略了符号位扩展，0补最高位
// >> : value >> num num 指定要移位值value 移动的位数。符号位不变，左边补上符号位
// << :3 <<2(3为int型)
　　1）把3转换为二进制数字0000 0000 0000 0000 0000 0000 0000 0011，
　　2）把该数字高位(左侧)的两个零移出，其他的数字都朝左平移2位，
　　3）在低位(右侧)的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，

put 方法

//如果原来存在相同的key-value，原来的value会被替换掉
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


//key=null时,也是有hash值的,是0,所以HashMap的key是可以为null的
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//HashTable源码的key直接进行了hashCode,如果key为null会抛出异常,所以HashTable的key不可以是null



//hash：表示key的hash值
//key：待存储的key值
//value：待存储的value值，从这个方法可以知道，HashMap底层存储的是key-value的键值对，不只是存储了value
//onlyIfAbsent：这个参数表示，是否需要替换相同的value值，如果为true，表示不替换已经存在的value
//evict:如果为false，表示数组是新增模式
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    //判断当前HashMap的数组是否为空或长度为0,如果是则调用resize()方法进行扩容
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
    //长度-1与hash按"与"位运算,判断为null时,在这个位置新增一个Node
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果取到了数据
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
        //p的hash值是否与传入的hash相等,再判断key是否相等
        //如果判断通过,传入的key-val键值对就是tab[i]位置上面的键值对,直接替换即可,不管后面是链表还是红黑树
            e = p;
        else if (p instanceof TreeNode)
        //如果之前的if未通过,则判断是不是红黑树节点
        //如果是,直接向红黑树新增一个节点
            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);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                    //如果链表的长度大于等于红黑树化的阈值-1
                    //就将链表转成红黑树存储数据。
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
    //判断当前的键值对数量是否即将超过阈值,如果将超过进行resize()操作
        resize();
    afterNodeInsertion(evict);
    return null;
}

key hash

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

resize JDK1.7 扩容方法

扩容使用2次幂的扩展(指长度扩为原来2倍)
所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

void resize(int newCapacity) {   //传入新的容量
    Entry[] oldTable = table;    //引用扩容前的Entry数组
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
        return;
    }
    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable);                         //！！将数据转移到新的Entry数组里
    table = newTable;                           //HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);//修改阈值
}


static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
    return h & (length-1);  //第三步 取模运算

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            do {
                Entry<K,V> next = e.next;
               int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
               e.next = newTable[i]; //标记[1]
               newTable[i] = e;      //将元素放在数组上
               e = next;             //访问下一个Entry链上的元素
           } while (e != null);
       }
   }
}

resize JDK1.8 扩容方法

只需要看看原来的hash值新增的那个bit是1还是0就好了
是0的话索引没变，是1的话索引变成”原索引+oldCap”，省去了重新计算hash值的时间
同时由于新增的1bit是0还是1可以认为是随机的
因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。
JDK1.7中rehash的时候，旧链表迁移新链表的时候，
如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        
        //如果老的数组为空，老的数组容量设为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        
        //如果老的数组容量大于0，首先判断是否大于等于HashMap的最大容量，
        //如果true，将阈值设置为Integer的最大值，同时数组容量不变
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            
            //如果扩容后的数组容量小于我们规定的最大数组容量，而且老的数组容量大于等于16，
            //对数组进行扩容，扩容后的数组容量为原来的两倍；同时阈值也扩容为原来的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        
        //如果老的数组容量为0，而且老的阈值大于0，则新的容量=老的阈值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               //老的阈值=0，容量和阈值都初始化为默认值，即16和12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        
        //如果新的阈值为0，为新的阈值赋值
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //首先定义一个新的容量的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        //遍历老的数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                //如果链表中只有一个数据，直接重新计算hash值，放入新的数组中
                        newTab[e.hash & (newCap - 1)] = e;
                //如果e是红黑树，需要将红黑树拆分后放入新的数组中
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}

线程安全性

为能理解用JDK1.7讲解

map初始化为一个长度为2的数组
loadFactor=0.75，threshold=2*0.75=1
也就是说当put第二个key的时候，map就需要进行resize。

public class HashMapInfiniteLoop {  
 
    private static HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);  
    public static void main(String[] args) {  
        map.put(5， "C");  
 
        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }  
}

通过设置断点让线程1和线程2同时debug到transfer方法(3.3小节代码块)的首行。注意此时两个线程已经成功添加数据。放开thread1的断点至transfer方法的”Entry next = e.next;” 这一行；然后放开线程2的的断点，让线程2进行resize。结果如下图。

注意，Thread1的 e 指向了key(3)，而next指向了key(7)，其在线程二rehash后，指向了线程二重组后的链表。

线程一被调度回来执行，先是执行 newTalbe[i] = e， 然后是e = next，导致了e指向了key(7)，而下一次循环的next = e.next导致了next指向了key(3)。

e.next = newTable[i] 导致 key(3).next 指向了 key(7)。注意：此时的key(7).next 已经指向了key(3)， 环形链表就这样出现了。

length优化规则

HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计
常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，
具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，
Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。
HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

小结

• HashMap会动态的将它替换成一个红黑树，将时间复杂度从O(n)降为O(logn)
• 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容
• HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap
• 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊
  • 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值
  • 如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值

LinkedHashMap

在HashMap中提到了下面的定义：
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap继承于HashMap，因此也重新实现了这3个函数，
顾名思义这三个函数的作用分别是：节点访问后、节点插入后、节点移除后做一些事情。

初始化

在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组

public LinkedHashMap(int initialCapacity, float loadFactor) {  
    super(initialCapacity, loadFactor);  
    accessOrder = false;  
}

afterNodeAccess

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果定义了accessOrder，那么就保证最近访问节点放到最后
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

afterNodeInsertion

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 如果定义了移除规则，则执行相应的溢出
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

afterNodeRemoval

void afterNodeRemoval(Node<K,V> e) { // unlink
    // 从链表中移除节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

put和get函数

put函数在LinkedHashMap中未重新实现，只是实现了afterNodeAccess和afterNodeInsertion两个回调函数。
get函数则重新实现并加入了afterNodeAccess来保证访问顺序，下面是get函数的具体实现：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

WeakHashMap

特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。特别适用于需要缓存的场景

存储结构是很普通的数组+链表
Entry是被WeakReference修饰的对象

expungeStaleEntries

对WeakHashMap进行增删改查时，都调用了expungeStaleEntries方法。

private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);

            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next; HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

TreeMap

TreeMap的实现是红黑树算法的实现

示例

TreeMap<Integer, String> tmap = new TreeMap<Integer, String>();
tmap.put(1, "语文");
tmap.put(3, "英语");
tmap.put(2, "数学");
tmap.put(4, "政治");
tmap.put(5, "历史");
tmap.put(6, "地理");
tmap.put(7, "生物");
tmap.put(8, "化学");
for(Entry<Integer, String> entry : tmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

put方法

如果存在的话，old value被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
        // 如果该节点存在，则替换值直接返回
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
        // 如果该节点未存在，则新建
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
        // 红黑树平衡调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

get方法

get函数则相对来说比较简单，以log(n)的复杂度进行get

final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
        // 按照二叉树搜索的方式进行搜索，搜到返回
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}
public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

迭代有序 - successor后继

如何保证迭代有序

for(Entry<Integer, String> entry : tmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
//java自动转换如下:
for(Iterator<Map.Entry<String, String>> it = tmap.entrySet().iterator() ; tmap.hasNext(); ) {
    Entry<Integer, String> entry = it.next();
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

在it.next()的调用中会使用nextEntry调用successor这个是过的后继的重点，具体实现如下：

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        // 有右子树的节点，后继节点就是右子树的“最左节点”
        // 因为“最左子树”是右子树的最小节点
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 如果右子树为空，则寻找当前节点所在左子树的第一个祖先节点
        // 因为左子树找完了，根据LDR该D了
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        // 保证左子树
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

a. 空节点，没有后继
b. 有右子树的节点，后继就是右子树的“最左节点”
c. 无右子树的节点，后继就是该节点所在左子树的第一个祖先节点

有右子树的节点，节点的下一个节点，肯定在右子树中，而右子树中“最左”的那个节点则是右子树中最小的一个，那么当然是右子树的“最左节点”，就好像下图所示：

无右子树的节点，先找到这个节点所在的左子树(右图)，那么这个节点所在的左子树的父节点(绿色节点)，就是下一个节点。

ConcurrentHashMap

ConcurrentHashMap不允许key或value为null值

重要内部类

• TreeBin 用于包装红黑树结构的结点类型

• ForwardingNode 扩容时存放的结点类型，并发扩容的实现关键之一

  一个用于连接两个table的节点类。
  它包含一个nextTable指针,用于指向下一张表。
  而且这个节点的key value next指针全部为null,它的hash值为-1.
  这里面定义的find的方法是从nextTable里进行查询节点,而不是以自身为头节点进行查找

• Node 普通结点类型,表示链表头结点

• nextTable

  扩容时用于存放数据的变量，扩容完成后会置为null。

• sizeCtl

  以volatile修饰的sizeCtl用于数组初始化与扩容控制,它有以下几个值

  if table未初始化:
      =0  //未指定初始容量时的默认值
      >0  //指定初始容量(非传入值，是2的幂次修正值)大小的两倍
      =-1 //表明table正在初始化
  else if nextTable为空:
      if 扩容时发生错误(如内存不足、table.length * 2 > Integer.MAX_VALUE等):
          =Integer.MAX_VALUE    //不必再扩容了！
      else:
          =table.length * 0.75  //扩容阈值调为table容量大小的0.75倍
  else:
      =-(1+N)  //N的低RESIZE_STAMP_SHIFT位表示参与扩容线程数，后面详细介绍

三个CAS原子操作方法:tabAt,casTabAt,setTabAt

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
    U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

hash计算

(hashCode ^ (hashCode >>> 16)) & 0X7FFFFFFF; // INT最大值

hashmap的hash计算  
(h = key.hashCode()) ^ (h >>> 16)

下标计算

hash & (n - 1)

hashmap的下标计算
hash & (n -1)

put解析

put方法依然沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，
如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。
ConcurrentHashMap中依然沿用这个思想，有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。
另外由于涉及到多线程，put方法就要复杂一点。在多线程中可能有以下两个情况：

如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。
这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，
如果检测到需要插入的位置被forward节点占有，就帮助进行扩容。 
如果检测到要插入的节点是非空且不是forward节点，就对这个节点加锁，
这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable的synchronized要好得多。



整体流程就是首先定义不允许key或value为null的情况放入 对于每一个放入的值，
首先利用spread方法对key的hashcode进行一次hash计算
由此来确定这个值在table中的位置。如果这个位置是空的，那么直接放入，而且不需要加锁操作。
如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。
如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。
需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，
则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。 如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。
如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。

• 判断是否数组是否为null或者长度为0,是则初始化initTable();

  if ((sc = sizeCtl) < 0)
      Thread.yield();
      //线程让步,如果前面有线程进行初始化,然后会while判断失效退出循环
  else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
      //难免会并发去初始化,通过CAS争夺执行权限
      return new Node<?,?>[16]
      //默认会初始化长度16的数组再返回出去
  }
  
  经历过initTable后还得再循环一边添加node

• 判断数组小标是否为空,为空直接放进去

  tabAt(tab, i = (n - 1) & hash)) == null
  
  casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null))

• 判断数组有下标的情况,取当前下标头结点,如果是链表则遍历价格节点,如果是TreeNode则加入树结点

• 添加元素数量size统计,并检查是否扩容

  • 大于当前扩容阈值并且小于最大扩容值才扩容，如果table还未初始化则等待初始化完成。
  • 线程可以参与扩容,并递增sizeCtl以表示线程数目

  • 计算元素数量,sumCount

    private final void addCount(long x, int check) {
        ...
        //check就是binCount，有新元素加入成功才检查是否要扩容。
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            //大于当前扩容阈值并且小于最大扩容值才扩容，如果table还未初始化则等待初始化完成。
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);  //@1
                if (sc < 0) {  //已经有线程在进行扩容工作
                    //检查是原容量为n的情况下进行扩容，保证sizeCtl与n是一块修改好的
                    //条件2与条件3在当前RESIZE_STAMP_BITS情况下应该不会成功，欢迎指正。
                    //条件4与条件5确保tranfer()中的nextTable相关初始化逻辑已走完。
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                        
                    //有新线程参与扩容则sizeCtl统计加1                        
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))  
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))  
                    
                    //有线程检测到需要扩容时走这里，初始值为(rs << RESIZE_STAMP_SHIFT) + 2))，+2没什么特别，
                    //只是为符合-（1+扩容线程数）的定义。
                                                                 
                    transfer(tab, null);
                    
                //元素数量计数                    
                s = sumCount();
            }
        }
    }

transfer 扩容解析

jdk1.8版本的ConcurrentHashMap支持无锁并行扩容

大体上分为2步骤:

• 构建一个nextTable,它的容量是原来的两倍,这个操作是单线程完成的,多线程遇到nextTable==null直接break

• 将原来table中的元素复制到nextTable中

  并且将原table的null节点forward节点,这里允许多线程进行操作,sychronized以数组头节点为主

先来看一下单线程是如何完成的：

它的大体思想就是遍历、复制的过程。首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素：

如果这个位置为空，就在原table中的i位置放入forwardNode节点，这个也是触发并发扩容的关键点；
如果这个位置是Node节点（fh>=0），如果它是一个链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上
如果这个位置是TreeBin节点（fh<0），也做一个反序处理，并且判断是否需要untreefi，把处理的结果分别放在nextTable的i和i+n的位置上
遍历过所有的节点以后就完成了复制工作，这时让nextTable作为新的table，并且更新sizeCtl为新容量的0.75倍 ，完成扩容。
再看一下多线程是如何完成的：

在代码的69行有一个判断，如果遍历到的节点是forward节点，就向后继续遍历，再加上给节点上锁的机制，就完成了多线程的控制。多线程遍历节点，处理了一个节点，就把对应点的值set为forward，另一个线程看到forward，就向后遍历。这样交叉就完成了复制工作。而且还很好的解决了线程安全的问题。 这个方法的设计实在是让我膜拜。

单线程新建nextTable,扩容为原table容量的两倍。

每个线程想增/删元素时,如果访问的桶是ForwardingNode节点,
则表明当前正处于扩容状态,协助一起扩容完成后再完成相应的数据更改操作。

扩容时将原table的所有桶倒序分配,每个线程每次最小分16个桶进行处理,防止资源竞争导致的效率下降
每个桶的迁移是单线程的,但桶范围处理分配可以多线程
在没有迁移完成所有桶之前每个线程需要重复获取迁移桶范围,直至所有桶迁移完成。

一个旧桶内的数据迁移完成但迁移工作没有全部完成时
查询数据委托给ForwardingNode结点查询nextTable完成(这个后面看find()分析)。

迁移过程中sizeCtl用于记录参与扩容线程的数量,全部迁移完成后sizeCtl更新为新table的扩容阈值。

代码片段

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)  //每个线程处理桶的最小数目，可以看出核数越高步长越小，最小16个。
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {    //不会重复初始化，addCount()处已有分析。
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];  //扩容一倍
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;  //扩容保护
            return;
        }
        nextTable = nextTab;
        transferIndex = n;  //扩容总进度，transferIndex之后的桶都已分配出去。
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);  //准备扩容时的特殊节点
    boolean advance = true;  //在table[i]的桶是否已完成迁移，这里的初始值不用理。
    boolean finishing = false; //table内所有桶都已迁移到nextTable标志位。
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)  //倒序处理职责内节点
                advance = false;
            //还未进行桶分配或一次迁移结束才会进行这个判断，为true表明要迁移的桶都已分配完毕，线程你就退出干活吧！
            else if ((nextIndex = transferIndex) <= 0) {  
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {  //transferIndex减少已分配出去的桶。
                //确定当前线程每次分配的待迁移桶的范围[bound, nextIndex)
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        //当前线程自己的活已经做完或所有线程的活都已做完。
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {  //所有线程已干完活，最后才走这里。
                nextTable = null;
                table = nextTab;  //替换新table
                sizeCtl = (n << 1) - (n >>> 1); //调sizeCtl为新容量0.75倍。
                return;
            }
            ////还未进行桶分配或一次迁移结束才会进行这个判断，为true表明要迁移的桶都已分配完毕，线程你就退出干活吧！
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                ////还记得addCount()处给sizeCtl赋的初值吗？这里检查是不是所有线程都干完活了，是的话置finishing=advance=true，为保险再检查一次。
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)   
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }

        //下面是正常的扩容逻辑，i处没节点放入ForwardingNode，方便其它线程检测。
        //ForwardingNode的作用主要有两个：1. 标明此节点已完成迁移，2. 为方便扩容期间的元素查找需求，里面有find()方法是从nextTable查找元素。
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)  //已迁移过，跳过。
            advance = true; // already processed
        else {
            synchronized (f) {  //对桶内元素迁移加锁。
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    if (fh >= 0) {  //链表
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        //找出最后一段完整的fh&n不变的链表
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        //1.6版本扩容套路，假设最后一段完整的fh&n不变的链表的runbit都是0，则nextTab[i]内元素ln前逆序，ln及其之后顺序，nextTab[i+n]内元素全部相对原table逆序。
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);  //在原table中设置ForwardingNode节点以提示该桶扩容完成。
                        advance = true;
                    }
                    else if (f instanceof TreeBin) { //红黑树处理，相似。
                        ...

helpTransfer

添加、删除节点之处都会检测到table的第i个桶是ForwardingNode的话会调用helpTransfer()方法。

final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

get

可以看到get()操作如果查询链表不用加锁,如果有红黑树结构的话e.find()方法内部实现需要获取锁。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {  //总是检查头结点
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)  //在迁移或都是TreeBin
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {  //链表则直接遍历查询
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

参考

• Java8系列之重新认识HashMap
• LinkedHashMap工作原理
• WeakHashMap解析
• TreeMap解析