数据结构

[toc]

Object

/*Class {@code Object} is the root of the class hierarchy.
 * Every class has {@code Object} as a superclass. All objects,
 * including arrays, implement the methods of this class.
 */
public class Object {

    private static native void registerNatives();
    static {
        registerNatives();
    }

数据结构

树

完全二叉树和满二叉树

满二叉树（Full Binary Tree）：一棵深度为 h，且有 2h - 1 个节点称之为满二叉树。

完全二叉树（Complete Binary Tree）： 若设二叉树的高度为h，除第h层外，其它各层（1～h-1）的结点数都达到最大个数，且第h层所有的节点都连续集中在最左边，这就是完全二叉树。

• 叶子结点只可能在最下面的两层上出现，对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1；

• 完全二叉树通常采用数组而不是链表存储，有如下特点：

  （1）若i为奇数且i>1，那么tree[i]的左兄弟为tree[i-1]；

  （2）若i为偶数且i<n，那么tree[i]的右兄弟为tree[i+1]；

  （3）若i>1，tree[i]的双亲为tree[i/2]；

  （4）若2*i<=n，那么tree[i]的左孩子为tree[2*i]；若2*i+1<=n，那么tree[i]的右孩子为tree[2*i+1]；

  （5）若i>n/2，那么tree[i]为叶子结点（对应于（3））；

  （6）若i<(n-1)/2，那么tree必有两个孩子（对应于（4））；

  （7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；

  （8）完全二叉树第i层至多有2^(i-1)个节点，共i层的完全二叉树最多有2^i-1个节点。

• 堆是一种完全二叉树 ；

• 完全二叉树中：度为0的结点总数=度为2的结点总数+1;，且完全二叉树中度为1的结点数只有0或1两种可能。

B树/B+树

M阶B树有以下的性质

M阶B+树需要满足以下几个要求：

• 从根节点到叶节点的所有路径都具有相同的长度；
• 所有数据信息都存储在叶子节点，非叶子节点仅作为叶节点的索引存在；
• 根节点至少有两个子树；
• 每个树节点最多拥有M个子树；
• 每个树节点（除了根节点）拥有至少M/2个子树。

栈和队列

栈的特点：

• 先进后出
• 常用操作：push()-入栈
• 底层实现：

什么是前中后缀表达式

前缀表达式：操作符在操作数的前面，比如 +-543

中缀表达式：操作符在操作数的中间，这也是人类最容易识别的算术表达式 3+4-5

后缀表达式：操作符在操作数的后面，比如 34+5-

计算机如何计算后缀表达式：

1.从左向右扫描

2.遇到数字，压入栈中；

3.遇到运算符，淡出栈顶的两个数，并用运算符对这两个数做相应的计算，并将结果入栈；

4.重复上述2、3步骤，直到表达式的最右端，最后的值即为表达式的结果。

队列的特点:

• 先进先出

• 常用操作：

• 底层实现：

HashMap

HashMap基于Map接口实现，用于Map通用的操作；实现了Cloneable可进行拷贝（HashMap实现的是浅拷贝，即对拷贝对象的改变会影响被拷贝对象）；实现了Serializable 接口，表示可实现序列化，可将HashMap对象保存至本地，之后可恢复状态；

元素以键值对的方式存储，并且允许使用null 建和null值，　因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的，可通过Collections类的静态方法synchronizedMap获取线程安全的HashMapMap map =Collections.synchronizedMap(new HashMap());。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 

与HashTable的区别： HashTable不允许key和value为null； HashTable是线程安全的，但是HashTable线程安全的策略实现代价太大-get/put等相关操作都是synchronized，这相当于给整个HashTable加了一把大锁（全表锁），多线程访问的时候，所有的线程都在竞争一把锁，只要有一个线程访问或操作该对象，那么其他的线程只能阻塞，安全却低效。

JDK 1.7

//默认初始化大小 16 
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
//最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子0.75，当容量达到75%时就要进行扩容操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;   
 //初始化的默认数组
static final Entry<?,?>[] EMPTY_TABLE = {}; 
 //table,长度必须2的n次方,动态扩大容器时使用的一个hashMap，table-真正存放数据的
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
 //HashMap中元素的数量
transient int size;    
  //用于判断是否需要扩容（threshold = 容量*负载因子）
int threshold;        
 //加载因子实际的大小,默认是DEFAULT_LOAD_FACTOR
    final float loadFactor;
    //用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
    transient int modCount;

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

构造函数

HashMap提供了四个构造方法，构造方法中 ，依靠第三个方法来执行的，但是前三个方法都没有进行数组的初始化操作，即使调用了构造方法此时存放HaspMap中数组元素的table表长度依旧为0 ,未真正初始化哈希表，真正的初始化table是在第一次调用put()。在第四个构造方法中调用了inflateTable()方法完成了table的初始化操作，并将m中的元素添加到HashMap中。

HashMap()    //无参构造方法
HashMap(int initialCapacity)  //指定初始容量的构造方法 
HashMap(int initialCapacity, float loadFactor) //指定初始容量和负载因子
HashMap(Map<? extends K,? extends V> m)  //指定集合，转化为HashMap

put

在该方法中，添加键值对时，首先进行table是否初始化的判断，如果没有进行初始化（分配空间，Entry[]数组的长度）。然后进行key是否为null的判断，如果key==null ,放置在Entry[]的0号位置。计算在Entry[]数组的存储位置，判断该位置上是否已有元素，如果已经有元素存在，则遍历该Entry[]数组位置上的单链表。判断key是否存在，如果key已经存在，则用新的value值，替换点旧的value值，并将旧的value值返回。如果key不存在于HashMap中，程序继续向下执行。将key-vlaue, 生成Entry实体，添加到HashMap中的Entry[]数组中。

 public V put(K key, V value) {
     //如果table数组为空数组{},进行数组填充(为table分配实际内存空间)，
        if (table == EMPTY_TABLE) { 
            //该方法主要是为table在内存中分配存储空间，确保capacity为大于或等于toSize的最接近toSize的二次幂；入参是threshold，此时的threshold为initialCapacity默认是1<<4(16)
            inflateTable(threshold);
        }
     //放置在table[0]号位置
        if (key == null) 
            return putForNullKey(value);
        int hash = hash(key); //计算hash值
        int i = indexFor(hash, table.length);  //计算在table中的存储位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果该对应数据已经存在，执行覆盖操作，并返回旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
     //保证并发访问，若HashMap内部结构发生变化，快速响应失败
        modCount++;
        addEntry(hash, key, value, i); //新增一个entry
        return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
     if ((size >= threshold) && (null != table[bucketIndex])) {
         resize(2 * table.length); //扩容操作，将数据元素重新计算位置后放入newTable中，链表的顺序与之前的顺序相反
         hash = (null != key) ? hash(key) : 0;
         bucketIndex = indexFor(hash, table.length);
     }

    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Get

public V get(Object key) {
     if (key == null)
         //返回table[0] 的value值
         return getForNullKey();
     Entry<K,V> entry = getEntry(key);

     return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
     if (size == 0) {
         return null;
     }
    //1.计算key的hashcode
     int hash = (key == null) ? 0 : hash(key);
    //2.定位到具体的桶中
     for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
         Object k;
         if (e.hash == hash &&
             ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
      }
     return null;
}

hash() 和 indexFor()

tatic final int hash(Object key) { 
 int h;
 // h = key.hashCode() 为第一步 取hashCode值
 // h ^ (h >>> 16) 为第二步 高位参与运算
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//计算该对象应该保存在table数组的哪个索引处:通过h & (table.length -1)来得到该对象的保存位，
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
    //为什么用& ?HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
 return h & (length-1); //第三步 取模运算
}

resize

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数组里，数组索引位置的计算通过key值的hashcode进行hash运算后再通过length-1进行位运算得到最终数组索引位置
 table = newTable; //HashMap的table属性引用新的Entry数组
 threshold = (int)(newCapacity * loadFactor);//修改阈值
 }

JDK 1.8

• 在JDK 1.8中优化了HashMap的数据结构：数组+链表+红黑树；
• 引入的原因：解决发生hash冲突后，链表过长从而导致索引效率慢的问题O(n)，利用红黑树快速增删改查的特点，时间复杂度由O(n)降低为O(logn);
• 当链表长度>8时，将该链表转化成红黑树，红黑树作为存储数据和解决hash冲突的方案。

//默认的初始容量，必须是2的平方 
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
 static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子0.75，0。75是对时间和空间平衡的选择；如果内存空间很多而又对时间效率要求很高，可以降低负载因子的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子的值，这个值可以大于1。
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
//实际加载因子
final float loadFactor;
//存储数据的Node类型
 transient Node<K,V>[] table;
 transient Set<Map.Entry<K,V>> entrySet;
//HashMap中存储的键值对的数量
transient int size;
transient int modCount;
//当>=threshold，进行扩容
int threshold;

//==========================与红黑树相关的参数==========================

//用于判断是否需要将链表转换为红黑树的阈值。
 static final int TREEIFY_THRESHOLD = 8;
//用于红黑树转为链表的阈值：<6将红黑树转为链表
 static final int UNTREEIFY_THRESHOLD = 6;
//最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
   // 否则，若桶内元素太多时，则直接扩容，而不是树形化
   // 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
 static final int MIN_TREEIFY_CAPACITY = 64;

关于加载因子：

• 加载因子越大，填满的元素越多，空间利用率高；但是冲突率加大，链表变长，查找效率低；
• 加载因子越小，冲突概率减小，链表短，查找效率高；但填满的元素少了，空间利用率低，需要频繁扩容，从而导致性能消耗大；
• 需要在查找效率和空间利用率之间寻找一种平衡，默认的0.75就是找到的一种平衡，也可根据实际情况进行时间换空间/空间换时间设置加载因子。

Node<K,V>

• HashMap中数组元素和链表节点采用Node类实现，JDK 1.7中采用的是Entry类；
• 实现了 Map.Entry<K,V>，本质上就是一个映射（键值对），实现了 getKey()、getValue() 、 hashCode()和equals(Object o)等方法

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    //返回的是oldValue
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    //判断两个对象是否相等，必须键值都相等，才返回true
        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;
        }
    }

TreeNode<K,V>

• 红黑树节点采用 TreeNode类实现；
• 继承LinkedHashMap.Entry<K,V>

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
    ... ... ...
}

主要方法

V get(Object key); // 获得指定键的值
V put(K key, V value);  // 添加键值对
void putAll(Map<? extends K, ? extends V> m);  // 将指定Map中的键值对 复制到 此Map中
V remove(Object key);  // 删除该键值对

boolean containsKey(Object key); // 判断是否存在该键的键值对；是 则返回true
boolean containsValue(Object value);  // 判断是否存在该值的键值对；是 则返回true

Set<K> keySet();  // 单独抽取key序列，将所有key生成一个Set
Collection<V> values();  // 单独value序列，将所有value生成一个Collection

void clear(); // 清除哈希表中的所有键值对
int size();  // 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
boolean isEmpty(); // 判断HashMap是否为空；size == 0时 表示为 空 

Put

如果当前map中没有数据，执行resize方法
如果要插入的键值对要存放的位置上刚好没有元素，那么就把它封装成Node对象，并放在这个位置上。
如果发生碰撞，判断node的类型是红黑树还是链表：
如果为红黑树，则将K-V对插在红黑树对应的位置。
如果为链表，遍历链表：
　a.如果为链表最后一个node ,则将新的node节点插入到链表尾
　b.插入完，如果链表的node数量大于8，则将链表转为红黑树的操作；如果当前哈希表为空或数组长度小于64，会扩容，否则转化为红黑树。转化的过程：先遍历链表 ，将链表的节点转化为红黑树的节点；然后将链表转化为红黑树。
c.遍历链表时，如果key已存在，则直接bredk循环。
判断是否要扩容
返回

public V put(K key, V value) {
    //调用putVal()方法完成
    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;
    //判断当前桶是否为空，空的话就需要初始化（resize()中会判断是否进行初始化）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //这里对应于JDK 1.7indexFor：计算存储的索引位置，如果没有元素，即没有Hash冲突，直接赋值
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
         //节点若已经存在，产生了Hash冲突
        Node<K,V> e; K k;
       //比较当前桶中的key、key的hashcode与写入的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 {
            //为链表，需要将当前的key、value封装成一个新节点写入到当前桶的后面，形成链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //链表长度8，将链表转化为红黑树存储
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //key存在，直接覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            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);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

hash

三连问：

以下三个问题均是为了提高存储k,V的数组下标位置的随机性和分布均匀性，尽量避免出现hash值冲突。

1.为什么不直接采用经过hashCode()处理的哈希码作为存储数组table的下标位置？

直接使用hashCode()处理容易出现哈希码与数组大小范围不匹配，计算出的哈希码可能不在数组大小范围内。

2.为什么次用哈希码&(数组长度-1)计算数组下标？

解决哈希码与数组大小范围不匹配的问题，且&操作，效率高于%

3.为什么在计算数组下标前，需对哈希码进行二次处理？

加大哈希码低位随机性，使分布得更均匀

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

HashMap在扩容的时候会调用resize()方法，这里的并发操作容易在一个桶上形成环形链表，这样在调用Get方法获取一个不存在的key时，若计算出的index正好是环形链表的下标就会出现死循环。

参考文献： https://juejin.im/post/5aa5d8d26fb9a028d2079264

ConcurrentHashMap

ConcurrentHashMap是Java并发包(java.util.concurrent)中提供的一个线程安全且高效的HashMap实现；这次使用了“分段锁”策略——将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据的时候，其他段的数据也能被其他线程访问；另外，ConcurrentHashMap可以做到读取数据不加锁，并且其内部的结构可以让其在进行写操作的时候能够将锁的粒度保持尽可能地小，不用对整个ConcurrentHashMap加锁。

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable

JDK 1.7

ConcurrentHashMap主要是由Segment[]、HashEntry[]组成，Segment是一种可重入锁ReentrantLock，HashEntry[]则用于存储键值对数据，一个ConcurrentHashMap里包含一个Segment[]，一个Segmet里面包含一个HashEntry[]，每个HashEntry是一个链表结构的元素，每个Segment守护一个HashEntry[]里的元素，当对HashEntry[]的数据进行修改时必须先获得它对应的Segment锁

static final class Segment<K,V> extends ReentrantLock implements Serializable { 
    //Segment中元素（HashEntry[]）的数量，为什么不将count设置为全局计数器？避免出现“热点域”而影响ConcurrentHashMap的并发性。
    transient volatile int count; 
    //对table的大小造成影响的操作的数量
    transient int modCount; 
    //Segment里面元素的数量超过这个值就会对Segment进行扩容
    transient int threshold; 
    //链表数组，数组中的每一个元素代表了一个链表的头部
    transient volatile HashEntry<K,V>[] table; 
    //负载因子
    final float loadFactor; 
}
//除了value以外，其他的几个变量都是final，这意味着不能从hash链的中间或尾部添加或删除节点，因为这些操作涉及到了next修改
static final class HashEntry<K,V> { 
    final K key; 
    final int hash; 
    volatile V value; 
    //final修饰，新节点只能在链表的表头处插入
    final HashEntry<K,V> next; 
} 

ConcurrentHashMap的初始化需要三个参数：其中concurrencyLevel代表Segment的数量，该变量一经指定，不可改变；若在后续过程中对ConcurrentHashMap进行扩容，不需要对整个ConcurrentHashMap做扩容，只需要对Segment里面的元素做一次扩容即可

public ConcurrentHashMap(int initialCapacity, 
                         float loadFactor, int concurrencyLevel) { 
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) 
        throw new IllegalArgumentException(); 

    if (concurrencyLevel > MAX_SEGMENTS) 
        concurrencyLevel = MAX_SEGMENTS; 

    // Find power-of-two sizes best matching arguments 
    int sshift = 0; 
    int ssize = 1; 
    while (ssize < concurrencyLevel) { 
        ++sshift; 
        ssize <<= 1; 
    } 
    segmentShift = 32 - sshift; 
    segmentMask = ssize - 1; 
    this.segments = Segment.newArray(ssize); 

    if (initialCapacity > MAXIMUM_CAPACITY) 
        initialCapacity = MAXIMUM_CAPACITY; 
    int c = initialCapacity / ssize; 
    if (c * ssize < initialCapacity) 
        ++c; 
    int cap = 1; 
    while (cap < c) 
        cap <<= 1; 

    for (int i = 0; i < this.segments.length; ++i) 
        this.segments[i] = new Segment<K,V>(cap, loadFactor); 
}

Get

public V get(Object key) { 
    //进行二次hash，目的是为了减少哈希冲突，使元素能够均匀分布在不同的Segment上，从而提高容器的存取效率
    int hash = hash(key.hashCode()); 
     return segmentFor(hash).get(key, hash); 
 } 
//确定操作应该在哪一个Segment中进行
final Segment<K,V> segmentFor(int hash) { 
     return segments[(hash >>> segmentShift) & segmentMask]; 
 } 
//调用Segment的get方法
V get(Object key, int hash) { 
    //count定义是volatile -对volatile字段的写入操作happens-before于每一个后续的同一个字段的读操作即保证写操作在读操作之前，也就保证了写操作对后续的读操作都是可见的，get的后续操作可以拿到完整的元素内容; 
    if (count != 0) { // read-volatile // ①
        HashEntry<K,V> e = getFirst(hash); 
        while (e != null) { 
            if (e.hash == hash && key.equals(e.key)) { 
                V v = e.value; 
                if (v != null) // ② 注意这里
                    return v; 
                return readValueUnderLock(e); // recheck 
            } 
            e = e.next; 
        } 
    } 
    return null; 
}
//用位操作来确定链表的头部，hash & (tab.length - 1)的结果是hash值的低n位
HashEntry<K,V> getFirst(int hash) {
    HashEntry<K,V>[] tab = table;
     return tab[hash & (tab.length - 1)];
 }

JDK 1.8

ConcurrentHashMap抛弃了原来的Segment分段锁，虽然源码里面还保留了，也只是为了兼容性的考虑。 采用CAS+synchroinzed来保证并发安全性。数据结构跟HashMap 1.8 的结构一样：数组+链表+红黑树；将JDK 1.7中存放数据的HashEntry改为Node，其中val、next都有volatile修饰，保证了可见性。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;

        Node(int hash, K key, V val, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

hash用来存储该key的hash值，但是有三个状态需要注意：

名称	值	描述
MOVED	-1	表示当前节点已经被处理过了
TREEBIN	-2	表示当前节点是TreeBin
RESERVED	-3	保留的hash值，用在ReservationNode上面

TreeNode类表示的是红黑树上的每个节点，当一个链表上的节点数量超过了指定的值，会将这个链表变为TreeNode，但是不像HashMap，ConcurrentHashMap在桶里面存的是一个TreeBin，在TreeBin内部维护一个TreeNode。

static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next,
                 TreeNode<K,V> parent) {
            super(hash, key, val, next);
            this.parent = parent;
        }
    }

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
}

ForwardingNode，在扩容的时候用到，如果一个线程在进行扩容操作，另一个线程put一个元素进来，如果看到对应的位置上面试ForwardingNode对象的话，那么就参与扩容的操作队列。

static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            super(MOVED, null, null, null);
            //表示扩容之后的数组
            this.nextTable = tab;
        }
}

Put

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

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //key,value都不能为空，否则抛出异常
        if (key == null || value == null) throw new NullPointerException();
        //获取key的hash值
        int hash = spread(key.hashCode());
        //用来控制扩容或者转移为树
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            //第一次put进行table初始化
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            //通过哈希计算出一个表中的位置
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //如果这个位置没有元素的话，通过CAS的方式尝试添加一个Node，这个时候没有加锁
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            //如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩容的数据复制阶段
            else if ((fh = f.hash) == MOVED)
                //当前线程也参与复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
                tab = helpTransfer(tab, f);
            else {
                //如果当前位置有元素的话，就采用synchronized的方式加锁
                V oldVal = null;
                synchronized (f) {
                    //再次取出要存储的位置元素，跟前面取出的进行比较
                    if (tabAt(tab, i) == f) {
                        //取出的hash值大于0，当转化成RBT时，hash值为-2
                        if (fh >= 0) {
                            binCount = 1;
                            //遍历整个链表
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    //当在同一个节点的数目达到8个的时候，
                    if (binCount >= TREEIFY_THRESHOLD)
                       // 则扩容或将转化为RBT
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
//
static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

initTable

sizeCtl<0表示已经有线程在对table数组进行初始化，当前线程要做的就是让出cpu时间，权利支持初始化table数组。当看到table数组更新成功之后，sizeCtl更新为table数组大小的0.75倍sc = n - (n >>> 2)。

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin

            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

Get

 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)
                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;
    }

面对面试题：

为什么要使用ConcurrentHashMap？

回答角度：HashMap不安全；HashTable虽然安全却效率低；再就是就ConcurrentHashMap自身。

参考文献： https://www.cnblogs.com/xiaoxi/p/7474026.html

https://www.cnblogs.com/fsychen/p/9361858.html

关键字

volatile

见CSDN博客

算法。

动态规划

动态规划是一种多阶段决策最优解模型，一般用来求最值问题，多数情况下它可以采用自下而上（消除子问题重叠）的递推方式得出每个子问题(子问题之间是有一定联系的)的最优解（即最优子结构），进而得出原问题的最优解。

使用前提：

• 判断是否可以使用递归来求解；
• 分析递归的过程中是否存在大量的重复子问题
• 采用备忘录的方式来存子问题的解以避免大量的重复计算
• 改用自底向上的方式来递推

动态规划的三要素：

• 最优子结构
• 状态转移方程
• 重叠子问题

关键步骤：

• 定义子问题的状态
• 写出状态转移方程

贪心

使用前提：

• 原问题复杂过高；
• 求全局最优解的数学模型难以建立；
• 求全局最优解的计算量过大；
• 没有太大的必要一定要求出全局最优解，“比较优”就可以；

如何将原问题分解成子问题？

• 按串行任务分：时间串行的任务，按子任务来分解，即每一步都是在前一步的基础上再选择当前的最优解；
• 按规模递减分： 规模较大的复杂问题，可以借助递归思想，分解成一个规模小一点点的问题，循环解决，当最后一步的求解完成后就得到了所谓的“全局最优解”。；
• 按并行任务分： 这种问题的任务不分先后，可能是并行的，可以分别求解后，再按一定的规则（比如某种配比公式）将其组合后得到最终解。

如何知道贪心算法结果逼近了全局最优值？

​ 不能量化判断，正因为全局最优值不能够知道，才求的局部最优值，所以按照逻辑分析、和结果不超过忍受范围就可以了。

步骤：

• 明确到底什么是最优解
• 明确什么是子问题的最优解
• 分别求出子问题的最优解再堆叠出全局最优解

排序

快速排序

排序效率在O(nlogn)中效率最高，思想是使用分治法策略把一个序列分为两个子序列，基本步骤：

• 先从序列中取出一个数作为基准数；
• 分区过程：将把这个数大的数全部放到它的右边，小于或者等于它的数全部放到它的左边；
• 递归地对左右子序列进行步骤2，直到个区间只有一个数。

根据大神的解读，可以形象地将此过程描述成挖坑填数+分治法

挖坑填数过程：

如上图，此时arr[5]之前的数字都小于等于它，arr[5]之后的数字都大于它，那么就在对arr[0…4]和arr[6…9]进行子区间重复上述步骤。

时间复杂度：

• 最好情况下为O(nlogn)
• 最坏情况下为O(n^2)

时间复杂度与基准数的选择密不可分，所以对于基准数的选择有以下几种方式：

• 固定基准数

• 随机基准数

• 三数取中：使用左端、右端、中心位置上的是哪个元素的中值作为基准元