hashMap在Java7和java8中的区别，底层数据结构，如何处理哈希冲突即链表怎么实现，头插法为什么会导致链表成环，尾插法为什么不会，resize的大致过程，hashMap的主要参数，为什么它的容量是2的次幂，hashMap的增删改查大致过程，为什么要同时实现key的equals和hashCode方法
，为什么JAVA8要引入红黑树，hash函数的从1.7到1.8的变化原因，可以看到1.8中hash方法非常简单，高低位异或就完了，为什么要这样做等等问题；

hashMap在Java7和Java8的区别？

JDK7 和 JDK8 中HashMap的大致变化是：

①1.7中采用数组+链表，1.8采用的是数组+链表/红黑树

②1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。

③1.7是采用表头插入法插入链表，1.8采用的是尾部插入法。

在1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在1.8中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

HashMap的底层数据结构？

1.7以前是Entry数组+链表的形式

1.8之后是Node数组+链表+红黑树的形式

每一个节点都会保存自身的hash、key、value、以及它的下个节点，Node的源码如下：

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

什么时候用到链表，为什么要用链表，怎么实现链表

数组的大小是有限的，因此在散列运算时可能会出现不同key同一个hash值的情况（散列冲突），这些拥有相同hash值且不同key的node节点会组成链表。

1.7前增加节点是头插法，设计意图是最后添加的节点可能使用频率更高，放在前面搜索效率高，但是并发下会出现环形链表的问题，导致无限循环

1.8后增加节点是尾插法，不会出现环形链表的情况，但不代表是线程安全的

在并发下，头插法如何出现环形链表的？尾插法为什么不会出现？

Java7 在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。

而Java8 在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

举个例子，往一个容量大小为2的put两个值，负载因子是0.75，在put第二个的node后就会进行resize

注意，是先插入到链表之后再判断节点总数是否大于threshold，并决定进行扩容。

所以，在多线程下，往容量为2的容器插入A，B，C（hash值相同），各线程间的threshold不可见，未立刻（比如在插入第二个节点）触发resize，链表的指向可能如下，注意这是resize之前的情况：

而resize使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置，在旧数组中同一条Node链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上：

就可能出现下面的情况，B的下一个指针指向了A，而在这之前A是指向B的！

AB互相引用，产生了环形链表，如果这个时候去取值就会出现无限循环的问题

通过上面的例子可以发现，使用头插会改变链表的顺序。但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。这也是多线程下，java7中hashMap可能会引起死循环而Java8中的hashMap不会引起死循环的原因。

那使用尾插法后hashmap可以在多线程下使用吗？若不能，为什么会线程不安全？

即使不会出现死循环，但是源码中put/get方法都没有同步加锁，即多线程下会出现一些问题，比如无法保证上一秒put的值，下一秒get的时候是原值，所以多线程下是不安全的。

既然提到resize，什么时候resize呢？

因为数组容量有限，当数据到达一定的数量，也就是超过threshold时就会进行扩容
threshold=(int)(Capacity*LoadFactor)

Capacity是HashMap当前长度，LoadFactor是负载因子，默认值0.75f

它是怎么扩容的呢？

分为两步

创建一个新的Node空数组，长度是原数组的2倍。
ReHash，遍历原Node数组，把原有的Node重新Hash到新数组中
resize源码如下：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //若旧容量大于最大容量，返回旧数组
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //容量，阈值翻倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1;
        }
        else if (oldThr > 0) 
            newCap = oldThr;
        //默认初始化参数
        else {               
            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"})
        //创建新table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //table指向了空的新数组
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //e是链表的首节点
                if ((e = oldTab[j]) != null) {
                    //先置空
                    oldTab[j] = null;
                    //如果旧 table 的首节点没有连接链表
                    if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
                    //如果旧 table 的首节点是树节点
                    else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果旧 table 的首节点后有链表，保存其链表顺序后设置到新数组
                    else { 
                        //将新数组分为两部分
                        //索引在原数组范围内（(e.hash & oldCap) == 0）的low部分，即loHead和loTail
                        Node<K,V> loHead = null, loTail = null;
                        //索引在原数组范围外的high部分，即hiHead，hiTail
                        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);
                        //设置新数组的首节点
                        //low部分保存在原处
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        //high部分，保存在原来位置+原来数组长度的位置
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;

为什么要重新Hash呢，直接复制过去不行么？

是因为长度扩大以后，Hash也会随之改变。根据Hash的公式：index = HashCode（Key） & （Length - 1），当length变化时，index也会变化，因此原来位置的节点根据hash算法后可能存在于其他位置了，这时直接复制过去会不合适。

hash的计算规则？

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

如果key为空，返回的hash为0，否则返回高低位异或运算后的key的hashCode

这里对key的null判断也解释了为什么hashmap可以存储null键，因为null键全部存储在数组索引为0的地方

默认初始化大小是多少？为什么大小都是2的幂？

默认初始化大小是16
数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀，具体可看下图

如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，即index=35的hash的低位只有一种可能-100011，而如果length-1的低位不全是1呢？看下图：

index=35，h的低位部分不再具有唯一性了，我的hash既可以是100011也可以是100111，即哈希冲突的几率会变的更大，而且由于length-1行的红色区域为0，index的红色区域也一定为0，这样会导致很多index永远得不到，空间被浪费！

如何保证自定义容量是大于它的最小2次幂

返回给定容量的最小二次幂方法如下，是一种低位填充1的方式，自己随便举一个例子推算一遍就明白了

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

HashMap的主要参数都有哪些？

①负载因子：loadFactor，代表了table的填充度有多少，默认是0.75f

②阈值：threshold，当table 为空时，该值为初始容量（初始容量默认为16）；当table被填充了，即为table分配内存空间后，threshold一般为 capacity * loadFactory；HashMap在进行扩容时会 threshold

③实际节点数：size，实际存储的key-value键值对的个数

④修改次数：modCount，用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），会抛出异常ConcurrentModificationException

基本构造函数如下：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组

HashMap的存取原理？

注意，这里都传入了key的hash值，在put节点中发生哈希冲突需要遍历链表或红黑树时，是通过比较key的hash值和key的内容来确定是否是同一个节点的，即key的equals方法和hashCode方法必须同时重写，以此保证equals返回为true的key的hashCode都相同。

put的大致过程如下：

table为空时，调用resize方法初始化table
数组索引处是否为空，即是否发生hash冲突，没有则直接将节点添加到该索引处，否则，遍历链表或者红黑树，寻找相同key（hash值和内容同时相同）的节点，若找到了则覆盖（注意 onlyIfAbsent 是否为true），否则尾插入链表或者插入红黑树
判断实际节点个数是否大于阈值，若大于则扩容

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

    //onlyIfAbsent 是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;
        //table为空，或者长度为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);
                        //链表数目大于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;
                }
            }
            //当有相同key的node时
            if (e != null) { 
                V oldValue = e.value;
                //根据 onlyIfAbsent 和 oldValue是否为空决定是否覆盖旧值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get的大致过程：

先检查数组索引处的key是否与目标key相同，若相同直接返回
否则，遍历链表或红黑树

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 && ((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;
}

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

containsKey方法本质上是调用getNode方法
将链表转成红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; 
        Node<K,V> e;
        //table为空或者很小时扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
        //数组索引处不为空时
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            //遍历链表，将node节点转换为treenode节点并设置顺序信息
            do {
                //把节点转为树节点
                TreeNode<K,V> p = replacementTreeNode(e, null);
                //设置头结点
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            //将头结点设置到table的索引处
            if ((tab[index] = hd) != null)
                //将链表转树
                hd.treeify(tab);
        }
    }

remove 删除节点的大致过程，遍历链表或者红黑树，找到要被删除的节点，根据节点类型，即树节点调用红黑树的删除方法，链表节点就让前驱节点指向被删节点的后继节点

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//matchValue为真，当value也一致时才删除
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //初始p为bin的首节点
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 
            node = p;
        else if ((e = p.next) != null) {
            //如果p是树节点
            if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                //遍历链表
                do {
                    if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    //保证p节点是node节点的前驱节点
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //找到要删除的节点node
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //被删节点等于其前驱节点，表示被删节点是首节点
            else if (node == p)
                tab[index] = node.next;
            //前驱节点的后继节点设置为被删节点的后继节点
            else
                p.next = node.next;

            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

其实不论是put，get还是remove，都一个共性操作，需要遍历链表或者红黑树，找到key相同（指key的hash值相同且key的equals返回为true）的节点，覆盖，返回或删除，因此必须同时重写key的hashCode方法和equals方法，保证equals为true的key的hashCode也一致，即通过equals和hashCode可以唯一确定一个key。

为什么我们重写equals方法的时候需要重写hashCode方法呢？你能用HashMap给我举个例子么？

重写equals方法时重写hashCode方法的目的是保证相同（equals返回为true）内容的key返回相同的hashCode
当类放在HashTable，HashMap，HashSet等Hash结构的集合时，才会重载hashcode
hashcode方法用来定义索引位置，以提高效率的同时可能会发生效率冲突，当出现hash冲突时，我们就得通过equals（）方法来判断冲突的对象是否相等

举个例子，我新建了一个类Person，属性有age，name和val，重写了equals方法，即相同age和name的Person对象是相同的，但是我没有实现hashCode方法，即调用Person实例的hashCode会根据对象的内存地址返回hash值。这代表着，相同age和name的Person对象，equals返回true，但是hashCode会不一样！比如：

新建一个Person实例：Person p1=new Person("张三","18"，1)

将它存到hashmap中：map.put(p1,p1.getVal())

过一段时间，我想更新value的值为2，我得新建一个：Person p2=new Person("张三","18"，2)

覆盖掉原来的键值对：map.put(p2,p2.getVal())

这时会发生什么呢？map里面同时有p1->1，p2->2的键值对，而我们想实现的是只有p2->2，为什么会发生这种情况呢？put方法会同时判断hash值是否相同和equals返回是否为true，这里是两个对象，即p1和p2的hashCode不同，自然当成两个key了。

同理，当我们要查询p1对应的value时：map.get(p2)

会发生什么？返回值为null，和上面的分析一样，hashCode不同。当想删除p1->1时，传入p2的remove方法也不会生效

看到这里会疑惑？为什么我获取p1->1的值，我要传入p2对象呢？因为在我们眼里，p1和p2应该是“相同的”，因为name和age都相同啊，即equals返回为true

那有人会说，我就传入p1对象查不就好了，可是想过没，如果我要在另外一个方法查这个键值对怎么办？难道每次都要把这个p1对象传过去？我知道这个Person的name和age就不能查询到该键值对显然不太合理！

或者像前面的put方法，我put的值是Person中的val属性，我得新建一个Person实例设置这个val属性吧（如果没有set方法），那这样新建的实例比如p2永远无法覆盖p1的值，这就是因为没有实现hashCode方法！

你用过HashMap吗？” “什么是HashMap？你为什么用到它？

HashMap可以接受null键值和值，而Hashtable则不能；HashMap是非synchronized;HashMap很快；以及HashMap储存的是键值对等等。

你知道HashMap的工作原理吗？” “你知道HashMap的get()方法的工作原理吗？

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。
这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。

关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法

面试官会加入一些Java程序员每天要碰到的实际场景
当两个对象的hashcode相同会发生什么？
因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

如果两个键的hashcode相同，你如何获取值对象？

当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket，将会遍历链表直到找到值对象。

找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。？？

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

你了解重新调整HashMap大小存在什么问题吗？

当多线程的情况下，可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tailtraversing)。如果条件竞争发生了，那么就死循环了。

为什么String, Interger这样的wrapper类适合作为键？

因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的，那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

我们可以使用自定义的对象作为键吗？

当然你可能使用任何对象作为键，只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。

我们可以使用CocurrentHashMap来代替Hashtable吗？

因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。

这些问题设计哪些知识点：
1、hashing的概念 2、HashMap中解决碰撞的方法 3、equals()和hashCode()的应用，以及它们在HashMap中的重要性 4、不可变对象的好处 5、HashMap多线程的条件竞争 6、重新调整HashMap的大小

HashMap的工作原理
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。
因为HashMap的好处非常多，我曾经在电子商务的应用中使用HashMap作为缓存（集合中的内容是存储在内存中的）。因为金融领域非常多的运用Java，也出于性能的考虑，我们会经常用到HashMap和ConcurrentHashMap。

HashMap红黑树原理分析

相比 jdk1.7 的 HashMap 而言，jdk1.8最重要的就是引入了红黑树的设计，红黑树除了插入操作慢其他操作都比链表快，当hash表的单一链表长度超过 8 个的时候，数组长度大于64，链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个，会重新把红黑树变成单向链表数据结构。
为什么要这样设计呢？好处就是避免在最极端的情况下链表变得很长很长，在查询的时候，效率会非常慢。

红黑树查询：其访问性能近似于折半查找，时间复杂度 O(logn)；
链表查询：这种情况下，需要遍历全部元素才行，时间复杂度 O(n)；
简单的说，红黑树是一种近似平衡的二叉查找树，其主要的优点就是“平衡“，即左右子树高度几乎一致，以此来防止树退化为链表，通过这种方式来保障查找的时间复杂度为 log(n)。

关于红黑树的内容，网上给出的内容非常多，主要有以下几个特性：
1、每个节点要么是红色，要么是黑色，但根节点永远是黑色的；