精华内容
下载资源
问答
  • 可以搜索微信公众号【Jet 与编程】查看更多精彩文章原文发布于自己的博客平台【http://www.jetchen.cn/analysis-hashmap/】HashMap 这个数据结构,不管是日常...背景很早的时候就想写点关于数据结构方面的文章,时...

    可以搜索微信公众号【Jet 与编程】查看更多精彩文章

    原文发布于自己的博客平台【http://www.jetchen.cn/analysis-hashmap/】


    HashMap 这个数据结构,不管是日常开发,还是求职面试,它始终都是所有 Java 程序员绕不开的宿命,所以还是决定写篇文章来详细剖析下 HashMap 这个数据结构,探探期间到底有多少奥秘。


    背景

    很早的时候就想写点关于数据结构方面的文章,时隔多年,终于决定正式开始提笔了,那就先从最热门的 HashMap 开始吧。

    HashMap 是 Java 程序中使用率最高的数据结构之一,其主要用于处理键值对这种数据结构。而且在 JDK 1.8 中对底层的实现进行了优化,比如引入了红黑树、优化了扩容机制等。

    本文主要是基于 JDK 最常用的 1.8 版本来介绍,详细分析了几个最重要的参数和方法,比如索引的计算、数组的扩容、put() 方法等,末尾也会稍微对比下 1.8 和 1.7 版本之间的差异。

    简介

    特点

    HashMap 继承自 Map,有如下特点:

    1. 存储 key - value 类型结构,数据类型不限制
    2. 根据 key 的 hashcode 值进行存储数据
    3. 最多只允许一条记录的键(key)为 null(对 value 值不约束)
    4. 它是无序的(其实一见 hash 我们便知道了)
    5. 查询效率很高
    6. 它是线程不安全的(要线程安全,可以使用 Collections 的 synchronizedMap,或者使用更加推荐的 ConcurrentHashMap)

    它还有一些常见的兄弟姐妹,比如 LinkedHashMap、TreeMap、Hashtable,本文就不进行对比介绍了。

    基本结构

    HashMap 的结构,是数组+链表+红黑树的结构,草图可以见下图。

    红黑树是在 JDK1.8 版本才引入的,目的是加快链表的查询效率

    c74b4aaa798dc8963a00046816cf4ff8.png

    HashMap 数据结构草图

    从上图可看出,HashMap 底层是一个哈希桶数组,名为 table,数组内存储的是基于 Node 类型的数据,所以,这个 Node 甚为关键,下文会详解。

    然后同一个数组所以的位置可以存储多个 Node,并以链表或红黑树的形式来实现,所以很容易猜到,既然是链表,那么每个 Node 必然会记录下一个 Node。但是如果链表很长,那查询效率便会降低,所以自 JDK1.8 开始便引入了红黑树,即当链表长度超过 8 的时候,链表便会转为红黑树,另外,当链表长度小于 6 的时候,会从红黑树转为链表。

    链地址法

    HashMap 是使用哈希表来存储数据的。哈希表为了解决冲突,一般有两种方案:开放地址法链地址法

    开放地址法:哈希完后如果有冲突,则按照某种规则找到空位插入

    HashMap 采用的便是 链地址法,即在数组的每个索引处都是一个链表结构,这样就可以有效解决 hash 冲突。

    当两个 key 的 hash 值相同时,则会将他们至于数组的同一个位置处,并以链表的形式呈现。

    但是如果大部分的数据都集中在了数组中的同一索引处,而其余索引处的数据比较少,即分配不均衡,则说明哈希碰撞较多。

    所以为了提高 HashMap 的存取效率,我们需要将数据尽可能多地分散到数组中去,即减少哈希碰撞,为了达到这一目的,最直接的方案便是改善 hash 算法,其次是扩大哈希桶数组的大小(扩容),在下文会详细介绍。

    字段和属性

    一些默认参数

    // 默认的初始容量为 16 (PS:aka 应该是 as know as)static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16// 最大容量(容量不够时需要扩容)static final int MAXIMUM_CAPACITY = 1 << 30;// 默认的负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;// 链表长度为 8 的时候会转为红黑树static final int TREEIFY_THRESHOLD = 8;// 长度为 6 的时候会从红黑树转为链表static final int UNTREEIFY_THRESHOLD = 6;// 只有桶内数据量大于 64 的时候才会允许转红黑树static final int MIN_TREEIFY_CAPACITY = 64;

    初始容量是 16,可以扩容,但是扩容之后的容量,也是 2 的幂次方,比如 32、64,why?这里面涉及到很多巧妙的设计,下文介绍 resize() 方法的时候会详细介绍。

    另外,我们解释下 MIN_TREEIFY_CAPACITY,虽然说当链表长度大于 8 的时候,链表会转为红黑树,但是也是需要满足桶内存储的数据量大于上述这个参数的值,否则不仅不会转红黑树,反而会进行扩容操作。

    比如下面这段代码是判断是否要将链表转为红黑树,乍看,只是将链表长度和 UNTREEIFY_THRESHOLD 进行对比,其实不然,点开 treeifyBin(tab, hash) 这个方法,我们便可以看到,如果此时桶数组内的数据量小于 MIN_TREEIFY_CAPACITY,则不会将链表转红黑树,而是进行扩容操作,见下图:

    87798948b70a9b4776bcdb8408302fc3.png

    链表转红黑树

    一些重要的字段

    // Map 中存储的数据量,即 key-value 键值对的数量transient int size;// HashMap 内部结构发生变化的次数,即新增、删除数据的时候都会记录,// 注意:修改某个 key 的值,并不会改变这个 modCounttransient int modCount;// 重点,代表最多能容纳的数据量// 即最多能容纳的 key-value 键值对的数量int threshold;// 负载因子,默认为 0.75// 注意,这个值是可以大于 1 的final float loadFactor;

    其中有两个参数需要注意一下,一个是 threshold,还有一个是 loadFactor

    threshold 代表最多能容纳的 Node 数量,一般 threshold = length * loadFactor,也就是说要想 HashMap 能够存储更多的数据(即获得较大的 threshold),有两种方案,一种是扩容(即增大数组长度 length),另一种便是增大负载因子。

    threshold 和数组长度不是一回事哦

    0.75 这个默认的负载因子的值是基于时间和空间考虑而得的一个比较平衡的点,所以负载因子我们一般不去调整,除非有特殊的需求:

    1. 比如 以空间换时间,意思是如果内存比较大,并且需要有较高的存取效率,则可以适当降低负载因子,这样做的话,就会减小哈希碰撞的概率。
    2. 再比如 以时间换空间,意思是如果内存比较小,并且接受适当减小存取效率,则可以适当调大负载因子,哪怕大于 1,这样做的话,就会增大哈希碰撞的概率。

    关于 0.75 这个负载因子的详细的解释,需要建立数学模型来分析,由于鄙人才疏学浅,暂不进行讨论。

    Node

    HashMap 底层是一个 Node[] table,所以 Node 是一个很重要的数据结构。

    Node 实现了 Entry 接口,所以,Node 本质上就是一个 Key-Value 数据结构。

    static class Node implements Map.Entry {    // key 的 hash 值    final int hash;    final K key;    V value;    // 记录下一个 Node    Node next;    Node(int hash, K key, V value, Node next) {...}    public final K getKey()        { return key; }    public final V getValue()      { return value; }    public final String toString() { return key + "=" + value; }    public final int hashCode() {...}    public final V setValue(V newValue) {...}    public final boolean equals(Object o) {...}}

    构造函数

    总共有四个构造函数,依次来讲解下。

    46b8c8280af6f09ae4926e9c5c6df01c.png

    构造函数列表

    HashMap()

    构造一个空的 HashMap,初始容量为 16,负载因子为 0.75

    // 构造一个空的 HashMap,初始容量为 16,负载因子为默认值 0.75public HashMap() {        this.loadFactor = DEFAULT_LOAD_FACTOR;  // all other fields defaulted}

    HashMap(int initialCapacity)

    构造一个空的 HashMap,并指定初始化容量,负载因子为默认的 0.75。

    构造函数内部会调用下文紧接着讲到的第三种构造函数。

    // 构造一个空的 HashMap,并指定初始化容量,负载因子采用默认的 0.75public HashMap(int initialCapacity) {        // 调用另一个构造函数    this(initialCapacity, DEFAULT_LOAD_FACTOR);}

    HashMap(int initialCapacity, float loadFactor)

    构造一个空的 HashMap,并指定初始化容量,指定负载因子。

    // 构造一个空的 HashMap,并指定初始化容量,指定负载因子public HashMap(int initialCapacity, float loadFactor) {    // 初始容量不为负数    if (initialCapacity < 0)        throw new IllegalArgumentException("Illegal initial capacity: " +  initialCapacity);    // 初始容量大于最大值时,则取最大值    if (initialCapacity > MAXIMUM_CAPACITY)        initialCapacity = MAXIMUM_CAPACITY;    // 负载因子不能小于 0,并且必须是数字,否则抛异常    if (loadFactor <= 0 || Float.isNaN(loadFactor))        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);    this.loadFactor = loadFactor;    this.threshold = tableSizeFor(initialCapacity);        // 最大容量 MAXIMUM_CAPACITY 为 1 << 30}

    构造函数中会进行一系列的参数判断,并且会进行初始化操作。

    1. 如果初始容量小于 0,或者负载因子小于 0 或不为数字时,会抛出 IllegalArgumentException 异常。
    2. 如果初始容量大于最大值(2^30),则会使用最大容量。
    3. 设置 threshold,直接调用 tableSizeFor() 方法,该方法会返回一个大于等于指定容量的 2 的幂次方的整数,例如传入 6,则会返回 8。

    tableSizeFor() 方法的详细解释会放到下文来讲解。

    另外,直接将得到的值赋给 threshold,难道不是应该是这样的操作吗?this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;, 其实不然,我们再看一眼源码,会发现初始化的动作放在了 put 操作中。

    HashMap(Map extends K, ? extends V> m)

    构造一个非空的 HashMap,保证初始化容量能够完全容下传进来的 Map,另外,负载因子使用的是默认值 0.75。

    // 构造一个非空的 HashMap,指定了默认的负载因子 0.75public HashMap(Map extends K, ? extends V> m) {    this.loadFactor = DEFAULT_LOAD_FACTOR;    // 将 Map 中的 key-value 赋值到新的 Map 中去    putMapEntries(m, false);}

    putMapEntries() 方法是将传递进来的 Map 中的数据全都存入到当前的 HashMap 中去,方法的详解见下文。

    关键方法

    tableSizeFor(int cap)

    顾名思义,初始化桶数组的大小。

    该方法的作用是返回一个大于等于传入的参数的数值,并且返回值会满足以下两点:

    1. 返回值是 2 的幂次方
    2. 返回值是最接近传入的参数的值

    比如:传入 5,则返回 8;传入 8,则返回 8;

    这个方法的设计是很令人惊叹的,十分巧妙,除了敬仰还是敬仰。

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

    2 的幂次方有个特点,就是它的字节码除了最高位是 1,其余全是 0。

    比如 2,字节码为:10,最高位为 1,其余为 0

    再比如16,字节码为:10000,最高位为 1,其余为 0

    所以方法内使用了大量的 “或运算”和 “右移”操作,目的是保证从最高位起的每个 bit 都是 1。

    1. 首行 int n = cap - 1; 的作用,是为了防止传入的参数本身就是一个 2 的幂次方,否则会返回两倍于参数的值;
    2. n |= n >>> 1; 的作用,是保证倒数第二个高位也是 1,下面的代码类似。
    3. 最后一行之前,得到的数类似 0000 1111 这种从第一个高位起全是 1,这样只要加了 1,则返回的数值必然是 2 的幂次方。

    详细的计算过程详解见下图:

    e435e0186dad3b0fb6de661b80c6ee3b.png

    tableSizeFor 过程

    putMapEntries(Map extends K, ? extends V> m, boolean evict)

    该方法是将参数 m 中的所有数据存入到当前的 HashMap 中去,比如在上文提到的第四种构造函数便调用了此方法。

    此方法还是比较简单的,下文代码中都注释,其中涉及到的两个关键方法 resize() 和 putVal() 方法,作用分别为扩容和赋值,下文再详细介绍这两个方法。

    // 将参数 m 中的所有元素存入到当前的 HashMap 中去final void putMapEntries(Map extends K, ? extends V> m, boolean evict) {    // 获取 m 中的参数个数(key-value 的数量)    int s = m.size();    if (s > 0) {        // 判断 table 是否被初始化过,否则初始化一遍。(PS:table 是在 put 操作的时候进行初始化的,所以如果当前的 HashMap 没有进行过 put 操作,则当前的 table 并不会被初始化)        if (table == null) { // pre-size            // 根据传进来的 map 的元素数量来计算当前 HashMap 需要的容量            float ft = ((float)s / loadFactor) + 1.0F;            // 计算而得的容量是不能大于最大容量的            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);            // 将计算而得的容量赋值给 threshold,前提是大于当前容量(即不会减小当前的 HashMap 的容量)            if (t > threshold)                // 将容量转换为最近的 2 的 幂次方                threshold = tableSizeFor(t);        }        // table 不为空,即已经初始化过了,        // 如果 m 中的元素数量超过了当前 HashMap 的容量,则要进行扩容        else if (s > threshold)            resize();        // 遍历 m 的每个元素,将它的 key-value 插入到当前的 HashMap 中去        for (Map.Entry extends K, ? extends V> e : m.entrySet()) {            K key = e.getKey();            V value = e.getValue();            // 插入数据(注意,为什么不是 put() 呢,因为 put() 其实也是调用的 putVal() 方法)            putVal(hash(key), key, value, false, evict);        }    }}

    hash(Object key)

    HashMap 中的 hash 算法,是将 key 进行 hashCode 计算得到 h,然后将 h 的高16位与低16位进行异或运算。

    这样做是从速度、质量等多方面综合考虑的,而且将高位和低位进行混合运算,这样是可以有效降低冲突概率的。

    另外,高位是可以保证不变的,变的是低位,并且低位中掺杂了高位的信息,最后生成的 hash 值的随机性会增大。

    下图举例介绍异或计算(例如 h 为 467,926,597):

    889a47721e1ebd0c7ffde61672d7539f.png

    异或运算

    从上图中也看出,高位的数字是不变的。

    // (h = key.hashCode()) ^ (h >>> 16);static final int hash(Object key) {    int h;    // 高 16 位与低 16 位进行异或运算    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

    另外,hash() 的作用是根据 key 计算一个 hash 数值,然后根据这个 hash 数值计算得到数组的索引 i,基于这个索引我们才能进行相关的增删改查操作,所以这个索引甚是关键。

    计算公式为:i = hash(key) & (n-1),即下面这个方法,但是这个下面这个方法仅限 1.8 以前的版本:

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

    这里又是一个很精妙的设计,一般情况下,我们要获取索引 i,最常用的计算方式是取模运算:hash % length,但是此处却使用的是:hash & (length-1),妙哉妙哉。

    为什么要这么做呢?因为 '%' 操作相对于位运算是比较消耗性能的,所以采用了奇淫技巧 '&' 运算。但是为什么结果是和取模运算是一致的呢?其实还是因为table的 length 的问题。

    我们上文提到过,HashMap 的长度 length 始终是 2 的幂次方,这个是关键,所以才会有这种结果,简单分析见下图:

    使用 & 位运算替代常规的 % 取模运算,性能上提高了很多,这个是 table 如此设计数组长度的优势之一,另一个很大的优势是在扩容的时候,下文会分析。

    44e3788a8cd4a445cbf3a6adccc8d32a.png

    取模运算

    resize()

    resize() 是一个很重要的方法,作用是扩容,从而使得 HashMap 可以存储更多的数据。

    因为当我们不断向 HashMap 中添加数据时,它总会超过允许存储的数据量上限,所以必然会经历 扩容 这一步操作,但是 HashMap 底层是一个数组,我们都知道数组是无法增大容量的,所以 resize 的过程其实就是新建一个更大容量的数组来存储当前 HashMap 中的数据。

    resize() 方法是很精妙的,我们就一起来看下 JDK1.8 的源码吧。

    final Node[] resize() {    // 当前 table    Node[] oldTab = table;    // 当前的 table 的大小    int oldCap = (oldTab == null) ? 0 : oldTab.length;    // 当前 table 的 threshold,即允许存储的数据量阀值    int oldThr = threshold;    // 新的 table 的大小和阀值暂时初始化为 0    int newCap, newThr = 0;    // ① 开始计算新的 table 的大小和阀值    // a、当前 table 的大小大于 0,则意味着当前的 table 肯定是有数据的    if (oldCap > 0) {        // 当前 table 的大小已经到了上线了,还咋扩容,自个儿继续哈希碰撞去吧         if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }        // 新的 table 的大小直接翻倍,阀值也直接翻倍        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            newThr = oldThr << 1; // double threshold    }    // b、当前的 table 中无数据,但是阀值不为零,说明初始化的时候指定过容量或者阀值,但是没有被 put 过数据,因为在上文中有提到过,此时的阀值就是数组的大小,所以直接把当前的阀值当做新 table 的数组大小即可    // 回忆一下:threshold = tableSizeFor(t);    else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;    // c、这种情况就代表当前的 table 是调用的空参构造来初始化的,所有的数据都是默认值,所以新的 table 也只要使用默认值即可    else {               // zero initial threshold signifies using defaults        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;    // ② 初始化新的 table    // 这个 newTab 就是新的 table,数组大小就是上面这一堆逻辑所计算出来的    @SuppressWarnings({"rawtypes","unchecked"})    Node[] newTab = (Node[])new Node[newCap];    table = newTab;    if (oldTab != null) {        // 遍历当前 table,处理每个下标处的 bucket,将其处理到新的 table 中去        for (int j = 0; j < oldCap; ++j) {            Node e;            if ((e = oldTab[j]) != null) {                // 释放当前 table 数组的对象引用(for循环后,当前 table 数组不再引用任何对象)                oldTab[j] = null;                // a、只有一个 Node,则直接 rehash 赋值即可                if (e.next == null)                    newTab[e.hash & (newCap - 1)] = e;                // b、当前的 bucket 是红黑树,直接进行红黑树的 rehash 即可                else if (e instanceof TreeNode)                    ((TreeNode)e).split(this, newTab, j, oldCap);                // c、当前的 bucket 是链表                else { // preserve order                    Node loHead = null, loTail = null;                    Node hiHead = null, hiTail = null;                    Node next;                    // 遍历链表中的每个 Node,分别判断是否需要进行 rehash 操作                    // (e.hash & oldCap) == 0 算法是精髓,充分运用了上文提到的 table 大小为 2 的幂次方这一优势,下文会细讲                    do {                        next = e.next;                        // 根据 e.hash & oldCap 算法来判断节点位置是否需要变更                        // 索引不变                        if ((e.hash & oldCap) == 0) {                            if (loTail == null)                                loHead = e;                            else                                loTail.next = e;                            loTail = e;                        }                        // 原索引 + oldCap                        else {                            if (hiTail == null)                                hiHead = e;                            else                                hiTail.next = e;                            hiTail = e;                        }                    } while ((e = next) != null);                    // 原 bucket 位置的尾指针不为空(即还有 node )                    if (loTail != null) {                        // 链表末尾必须置为 null                        loTail.next = null;                        newTab[j] = loHead;                    }                    if (hiTail != null) {                        // 链表末尾必须置为 null                        hiTail.next = null;                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    return newTab;}

    好了,下面我们就介绍下上面的源码中提到的计算索引的操作,即判断 if ((e.hash & oldCap) == 0)。

    下图展示的是扩容前和扩容后的计算索引的方法,主要关注红色框中的内容。这种方案是没问题的,但是之前我们提到,table 的大小为 2 的幂次方,这什么要这么设计呢,期间的又一个奥秘便体现在此,请看图中的备注。

    4f2f59b9b02d90cae9bad11170488b73.png

    扩容索引计算1

    既然扩容后每个 key 的新索引的生成规则是固定有规律的,即只有两种形式,要么不变 i,要么增加原先的数组大小的量(i+n),所以我们其实并不需要真的去计算每个 key 的索引,而只需要判断索引是否不变即可。所以此处巧妙地使用了 (e.hash & oldCap) == 0 这个判断,着实精妙,计算的细节过程看下面的图即可。

    e9684f668195f9da684f40ecf55180b9.png

    扩容索引计算2

    put(K key, V value)

    此处介绍的是 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict),因为 put() 其实就是直接调用的 putVal();

    put() 方法是 HashMap 中最常用的方法之一,我们先大体关注下 put() 方法的流程,文字就暂不赘述了,看下图便很清晰了:

    c2305b3e478627703921b46ce182ff03.png

    put 流程

    下面简单分析下源码:

    public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}// 参数 onlyIfAbsent,true:不修改已存在的 value,false:已存在则进行修改final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {    Node[] tab; Node p; int n, i;    // ① 如果当前 table 为空则进行初始化    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // (n - 1) & hash 计算得到索引 i,算法在上文有提到,然后查看索引处是否有数据    // ② 如果没有数据,则新建一个新的 Node    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    // 索引处有数据    else {        Node e; K k;        // ③ 索引处的第一个 Node 的  key 和参数 key 是一致的,所以直接修改 value 值即可(修改的动作放在下面)        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        // ④ 索引处的 bucket 是红黑树,按照红黑树的逻辑进行插入或修改        else if (p instanceof TreeNode)            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);        // ⑤ 索引处的 bucket 是链表        else {            // 遍历链表上面的所有 Node            for (int binCount = 0; ; ++binCount) {                // 索引处的 Node 为尾链                if ((e = p.next) == null) {                    // 直接新建一个 Node 插在尾链处                    p.next = newNode(hash, key, value, null);                    // 判断是否需要转换为红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        // 链表转换为红黑树,此方法在上文中也有介绍                        treeifyBin(tab, hash);                    break;                }                // 当前 Node 的 key 值和参数 key 是一致的,即直接修改 value 值即可(修改的动作放在下面)                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        // 找到了相同 key 的 Node,所以进行修改 vlaue 值即可        if (e != null) { // existing mapping for key            V oldValue = e.value;            // 修改 value 值            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            // 修改操作,直接 return 结束掉代码逻辑            return oldValue;        }    }    // 记录结构发生变化的次数    ++modCount;    // ⑥ 判断是否需要扩容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    // 新增的 Node,返回 null    return null;}

    get(Object key)

    此处介绍的是 getNode(int hash, Object key,因为 get() 其实就是直接调用的 getNode();

    get() 方法也是比较简单的,就是根据 key 获取 table 的索引,然后再分情况查找拥有相同 key 的 Node;

    源码大致如下:

    public V get(Object key) {    Node e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}final Node getNode(int hash, Object key) {    Node[] tab; Node first, e; int n; K k;    // 当前 table 不为空    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        // 判断索引处的第一个 Node 的 key 值是否和参数 key 相同,相同则返回该 Node        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            return first;        // 索引处的第一个 Node 不是想要的,则接着查 next        if ((e = first.next) != null) {            // bucket 是红黑树结构            if (first instanceof TreeNode)                return ((TreeNode)first).getTreeNode(hash, key);            do {                // bucket 是链表结构                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}

    JDK1.8 VS JDK1.7

    1.7 和 1.8 之间的区别,最最主要的是如下三方面,当然,鄙人觉得这三点的变化可以算是比较成功的优化。

    1. 扩容后 Node 索引的计算方式不同。上文提到,由于 table 大小的这种神奇的设计,所以扩容时计算索引的时候,1.8 中只需要简单使用 & 运算来判断是否为 0 即可,并不需要像 1.7 一样每次都是用 & 运算来计算出索引值。
    2. 1.8 中引入了红黑树结构。上文也提到了,当链表长度大于 8 的时候会转换为红黑树,但是 1.7 中是数组+链表的组合。
    3. 1.8 中采用的是尾插法,而 1.7 中采用的是头插法。比如扩容的时候,头插法会使链表上 Node 的顺序调转,而尾插法则不会,另外,头插法也会造成环形链死循环等问题,本文就不深讨了。

    其它

    HashMap 是线程不安全的,因为它是允许多线程同时操作同一个数组的,比如 put(),比如 resize(),这些都会造成数据异常甚至死循环。

    所以要使用线程安全的 Map 的时候,可以使用 HashTable,但是这个不推荐,或者使用自 JDK1.8 开始引入的 Concurrent 包中的 ConcurrentHashMap,这个是比较推荐的,具体的介绍就放到下文再说吧。

    参考了美团的技术博客:传送门

    9c7322e6359a536cdf40ba6f647eabe9.png
    展开全文
  • Map 接口 Java集合包括俩大类 一类是保存单列数据的Collection接口,Collection又包括List 和Set子接口 ...Hashmap 底层结构 Hashmap 源码 Hashtable 底层结构 Hashtable 源码 **Hashmap Hashtable 对比 ** ...

    Map 接口
    Java集合包括俩大类
    一类是保存单列数据的Collection接口,Collection又包括List 和Set子接口
    一类是保存双列数据的Map接口,常见的实现类为Hashmap , Hashtable TreeMap,Properties

    Map 接口的特点
    保存键值对的数据
    键不能重复
    keyvalue值可以为null
    list&map 均重写了toString 可以直接打印

    Hashmap
    Hashmap 有俩个影响因素
    一个是初始capacity: 创建hashmap时候桶的个数
    一个是load factor:0.75 平衡了存储和查询

    Hashmap 底层结构
    创建hashMap, HashMap hashMap = new HashMap();
    初始化了如下变量
    table: 保存了数据的数组,如下:
    在这里插入图片描述
    table 结构如下图,每一个格子称为桶,当一个桶上有多个元素时候,一般以链表保存,当元素个数>8 的時候,以树结构保存

    在这里插入图片描述
    threshold: 临界值,超过该值就要扩容,初始化hashmap之后就变为0.75

    在这里插入图片描述
    第一次put值的时候,变量赋值,table 容量变为16,临界值threshold = 160.75 =12
    在这里插入图片描述
    当到达threshold=12 时候,table 容量变为16
    2 = 32
    threshold =32*0.75=24
    在这里插入图片描述

    Hashmap 源码
    初始化 HashMap hashMap = new HashMap();
    底层就是把loadFactor 从0 变为0.75

     public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    

    往hashmap 中put 元素

    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
      //这里的hash 方法获取到key的hashcode方法
     static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    

    扩容方法,采用的是左移位运算相当与*2 的计算
    HashMap的resize方法
    在这里插入图片描述
    当扩容的时候,有可能打乱hashmap元素顺序,重新放置元素

    hashmap 总结
    在这里插入图片描述
    Hashtable 底层结构
    hashtable使用和hashmap 几乎一样
    底层结构也是哈希表,同hashmap
    所以只要直到二者区别就好了
    在这里插入图片描述
    Treemap底层结构(非重点)
    treemap 底层是红黑树
    treemap 元素默认按照key的自然排序,或者定制排序的
    treeset底层是treemap, key是treeset元素,value为空
    自然排序指implement comparable 重写compare to 方法
    定制排序指创建treemap 的时候,指定排序规格 用new Comparator(){}内部类实现

    面试题

    通过map.size() 和 map.isEmpty() 判断map 元素个数是否为空,那个效率高?
    效率一样高, map.isEmpty() 底层也是判断size() ==0

    展开全文
  • 废话不多说,直接上正文!1:HashMap 的数据结构?A:哈希表结构(链表散列:数组+链表)... HashMap 底层是 hash 数组和单向链表实现,数组中的每个元素都是链表,由 Node 内部类(实现 Map.Entry接口)实现,HashMap ...

    废话不多说,直接上正文!

    1:HashMap 的数据结构?

    A:哈希表结构(链表散列:数组+链表)实现,结合数组和链表的优点。当链表长度超过 8 时,链表转换为红黑树。transient Node[] table;

    2:HashMap 的工作原理?

      HashMap 底层是 hash 数组和单向链表实现,数组中的每个元素都是链表,由 Node 内部类(实现 Map.Entry接口)实现,HashMap 通过 put & get 方法存储和获取。

    存储对象时,将 K/V 键值传给 put() 方法:

      ①、调用 hash(K) 方法计算 K 的 hash 值,然后结合数组长度,计算得数组下标;

      ②、调整数组大小(当容器中的元素个数大于 capacity * loadfactor 时,容器会进行扩容resize 为 2n);

      ③、i.如果 K 的 hash 值在 HashMap 中不存在,则执行插入,若存在,则发生碰撞;

        ii.如果 K 的 hash 值在 HashMap 中存在,且它们两者 equals 返回 true,则更新键值对;

        iii. 如果 K 的 hash 值在 HashMap 中存在,且它们两者 equals 返回 false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。

    (JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法)(注意:当碰撞导致链表大于 TREEIFY_THRESHOLD = 8 时,就把链表转换成红黑树)

      获取对象时,将 K 传给 get() 方法:①、调用 hash(K) 方法(计算 K 的 hash 值)从而获取该键值所在链表的数组下标;②、顺序遍历链表,equals()方法查找相同 Node 链表中 K 值对应的 V 值。

    hashCode 是定位的,存储位置;equals是定性的,比较两者是否相等。

    3.当两个对象的 hashCode 相同会发生什么?

      因为 hashCode 相同,不一定就是相等的(equals方法比较),所以两个对象所在数组的下标相同,"碰撞"就此发生。又因为 HashMap 使用链表存储对象,这个 Node 会存储到链表中。

    4.你知道 hash 的实现吗?为什么要这样实现?

      JDK 1.8 中,是通过 hashCode() 的高 16 位异或低 16 位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度,功效和质量来考虑的,减少系统的开销,也不会造成因为高位没有参与下标的计算,从而引起的碰撞。

    5.为什么要用异或运算符?

      保证了对象的 hashCode 的 32 位值只要有一位发生改变,整个 hash() 返回值就会改变。尽可能的减少碰撞。

    6.HashMap 的 table 的容量如何确定?loadFactor 是什么? 该容量如何变化?这种变化会带来什么问题?

      ①、table 数组大小是由 capacity 这个参数确定的,默认是16,也可以构造时传入,最大限制是1<<30;

      ②、loadFactor 是装载因子,主要目的是用来确认table 数组是否需要动态扩展,默认值是0.75,比如table 数组大小为 16,装载因子为 0.75 时,threshold 就是12,当 table 的实际大小超过 12 时,table就需要动态扩容;

      ③、扩容时,调用 resize() 方法,将 table 长度变为原来的两倍(注意是 table 长度,而不是 threshold)

      ④、如果数据很大的情况下,扩展时将会带来性能的损失,在性能要求很高的地方,这种损失很可能很致命。

    7.HashMap中put方法的过程?

    • 答:“调用哈希函数获取Key对应的hash值,再计算其数组下标;
    • 如果没有出现哈希冲突,则直接放入数组;如果出现哈希冲突,则以链表的方式放在链表后面;
    • 如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表;
    • 如果结点的key已经存在,则替换其value即可;
    • 如果集合中的键值对大于12,调用resize方法进行数组扩容。”

    8.数组扩容的过程?

      创建一个新的数组,其容量为旧数组的两倍,并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种,原下标位置或原下标+旧数组的大小。

    9.拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?

      之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。

    10.说说你对红黑树的见解?

    • 1、每个节点非红即黑
    • 2、根节点总是黑色的
    • 3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
    • 4、每个叶子节点都是黑色的空节点(NIL节点)
    • 5、从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)

    11.jdk8中对HashMap做了哪些改变?

    • 在java 1.8中,如果链表的长度超过了8,那么链表将转换为红黑树。(桶的数量必须大于64,小于64的时候只会扩容)
    • 发生hash碰撞时,java 1.7 会在链表的头部插入,而java 1.8会在链表的尾部插入
    • 在java 1.8中,Entry被Node替代(换了一个马甲)。

    12.HashMap,LinkedHashMap,TreeMap 有什么区别?

      HashMap 参考其他问题;  LinkedHashMap 保存了记录的插入顺序,在用 Iterator 遍历时,先取到的记录肯定是先插入的;遍历比 HashMap 慢;  TreeMap 实现 SortMap 接口,能够把它保存的记录根据键排序(默认按键值升序排序,也可以指定排序的比较器)

    13.HashMap & TreeMap & LinkedHashMap 使用场景?

      一般情况下,使用最多的是 HashMap。  HashMap:在 Map 中插入、删除和定位元素时;  TreeMap:在需要按自然顺序或自定义顺序遍历键的情况下;  LinkedHashMap:在需要输出的顺序和输入的顺序相同的情况下。

    14.HashMap 和 HashTable 有什么区别?

      ①、HashMap 是线程不安全的,HashTable 是线程安全的;

      ②、由于线程安全,所以 HashTable 的效率比不上 HashMap;

      ③、HashMap最多只允许一条记录的键为null,允许多条记录的值为null,而 HashTable不允许;

      ④、HashMap 默认初始化数组的大小为16,HashTable 为 11,前者扩容时,扩大两倍,后者扩大两倍+1;

      ⑤、HashMap 需要重新计算 hash 值,而 HashTable 直接使用对象的 hashCode

    15.Java 中的另一个线程安全的与 HashMap 极其类似的类是什么?同样是线程安全,它与 HashTable 在线程同步上有什么不同?

      ConcurrentHashMap 类(是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现)。  HashTable 是使用 synchronize 关键字加锁的原理(就是对对象加锁);  而针对 ConcurrentHashMap,在 JDK 1.7 中采用 分段锁的方式;JDK 1.8 中直接采用了CAS(无锁算法)+ synchronized。

    16.HashMap & ConcurrentHashMap 的区别?

      除了加锁,原理上无太大区别。另外,HashMap 的键值对允许有null,但是ConCurrentHashMap 都不允许。

    17.为什么 ConcurrentHashMap 比 HashTable 效率要高?

      HashTable 使用一把锁(锁住整个链表结构)处理并发问题,多个线程竞争一把锁,容易阻塞;

      ConcurrentHashMap

    • JDK 1.7 中使用分段锁(ReentrantLock + Segment + HashEntry),相当于把一个 HashMap 分成多个段,每段分配一把锁,这样支持多线程访问。锁粒度:基于 Segment,包含多个 HashEntry。
    • JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度:Node(首结点)(实现 Map.Entry)。锁粒度降低了。

    18.针对 ConcurrentHashMap 锁机制具体分析(JDK 1.7 VS JDK 1.8)?

      JDK 1.7 中,采用分段锁的机制,实现并发的更新操作,底层采用数组+链表的存储结构,包括两个核心静态内部类 Segment 和 HashEntry。    ①、Segment 继承 ReentrantLock(重入锁) 用来充当锁的角色,每个 Segment 对象守护每个散列映射表的若干个桶;    ②、HashEntry 用来封装映射表的键-值对;    ③、每个桶是由若干个 HashEntry 对象链接起来的链表

    2075b91b6b1aafb17c390e2d76641383.png

      JDK 1.8 中,采用Node + CAS + Synchronized来保证并发安全。取消类 Segment,直接用 table 数组存储键值对;当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时,链表转换为红黑树,提升性能。底层变更为数组 + 链表 + 红黑树。

    80791aa9f5d239fe686d310dbef142ce.png

    19.ConcurrentHashMap 在 JDK 1.8 中,为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock?

      ①、粒度降低了;  ②、JVM 开发团队没有放弃 synchronized,而且基于 JVM 的 synchronized 优化空间更大,更加自然。  ③、在大量的数据操作下,对于 JVM 的内存压力,基于 API 的 ReentrantLock 会开销更多的内存。

    20.ConcurrentHashMap 简单介绍?

    ①、重要的常量:

      private transient volatile int sizeCtl;

      当为负数时,-1 表示正在初始化,-N 表示 N - 1 个线程正在进行扩容;

      当为 0 时,表示 table 还没有初始化;

      当为其他正数时,表示初始化或者下一次进行扩容的大小。

    ②、数据结构:

      Node 是存储结构的基本单元,继承 HashMap 中的 Entry,用于存储数据;

      TreeNode 继承 Node,但是数据结构换成了二叉树结构,是红黑树的存储结构,用于红黑树中存储数据;

      TreeBin 是封装 TreeNode 的容器,提供转换红黑树的一些条件和锁的控制。

    ③、存储对象时(put() 方法):

      1.如果没有初始化,就调用 initTable() 方法来进行初始化;

      2.如果没有 hash 冲突就直接 CAS 无锁插入;

      3.如果需要扩容,就先进行扩容;

      4.如果存在 hash 冲突,就加锁来保证线程安全,两种情况:一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入;

      5.如果该链表的数量大于阀值 8,就要先转换成红黑树的结构,break 再一次进入循环

      6.如果添加成功就调用 addCount() 方法统计 size,并且检查是否需要扩容。

    ④、扩容方法 transfer():默认容量为 16,扩容时,容量变为原来的两倍。

      helpTransfer():调用多个工作线程一起帮助进行扩容,这样的效率就会更高。

    ⑤、获取对象时(get()方法):

      1.计算 hash 值,定位到该 table 索引位置,如果是首结点符合就返回;

      2.如果遇到扩容时,会调用标记正在扩容结点 ForwardingNode.find()方法,查找该结点,匹配就返回;

      3.以上都不符合的话,就往下遍历结点,匹配就返回,否则最后就返回 null。

    21.ConcurrentHashMap 的并发度是什么?

      程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16,且可以在构造函数中设置。当用户设置并发度时,ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度(假如用户设置并发度为17,实际并发度则为32)

    最后

    我把这份资料也分享给大家,希望大家都能进大厂,年薪百万!

    私信我【资料】即可获取

    知识点的梳理非常重要!

    b3f2d60da4c1b6e10574672ffea98780.png

    知识导图思维笔记

    配套的相关面试题:

    0db2e00631304a13ed2c9e77f901fcff.png

    配套的相关面试题

    大厂面试真题:

    37262d17da95e4592283452d9f68a3ff.png
    18aac8ccdcdd1fa960df755aa9c95eda.png

    大量电子书

    私信【资料】即可获取

    展开全文
  • Queue什么是队列队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。队列的种类单队列(单队列就是常见的队列, 每次添加元素时,都是添加到...

    Queue

    什么是队列

    队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。

    队列的种类

    • 单队列(单队列就是常见的队列, 每次添加元素时,都是添加到队尾,存在“假溢出”的问题也就是明明有位置却不能添加的情况)
    • 循环队列(避免了“假溢出”的问题)

    Java 集合框架中的队列 Queue

    Java 集合中的 Queue 继承自 Collection 接口 ,Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。Queue 用来存放 等待处理元素 的集合,这种场景一般用于缓冲、并发访问。除了继承 Collection 接口的一些方法,Queue 还添加了额外的 添加、删除、查询操作。

    推荐文章

    • https://blog.csdn.net/u011240877/article/details/52860924

    Set

    什么是 Set

    Set 继承于 Collection 接口,是一个不允许出现重复元素,并且无序的集合,主要 HashSet 和 TreeSet 两大实现类。

    在判断重复元素的时候,Set 集合会调用 hashCode()和 equal()方法来实现。

    补充:有序集合与无序集合说明

    • 有序集合:集合里的元素可以根据 key 或 index 访问 (List、Map)
    • 无序集合:集合里的元素只能遍历。(Set)

    HashSet 和 TreeSet 底层数据结构

    HashSet 是哈希表结构,主要利用 HashMap 的 key 来存储元素,计算插入元素的 hashCode 来获取元素在集合中的位置;

    TreeSet 是红黑树结构,每一个元素都是树中的一个节点,插入的元素都会进行排序;

    推荐文章

    • https://www.jianshu.com/p/b48c47a42916

    List

    什么是List

    在 List 中,用户可以精确控制列表中每个元素的插入位置,另外用户可以通过整数索引(列表中的位置)访问元素,并搜索列表中的元素。 与 Set 不同,List 通常允许重复的元素。 另外 List 是有序集合而 Set 是无序集合。

    List的常见实现类

    ArrayList 是一个数组队列,相当于动态数组。它由数组实现,随机访问效率高,随机插入、随机删除效率低。

    LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低,但随机插入、随机删除效率高。

    Vector 是矢量队列,和ArrayList一样,它也是一个动态数组,由数组实现。但是ArrayList是非线程安全的,而Vector是线程安全的。

    Stack 是栈,它继承于Vector。它的特性是:先进后出(FILO, First In Last Out)。相关阅读:https://blog.csdn.net/javazejian/article/details/53362993

    ArrayList 和 LinkedList 源码学习

    • https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/ArrayList.md
    • https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/LinkedList.md

    推荐阅读

    • https://blog.csdn.net/javazejian/article/details/52953190

    Map

    • https://juejin.im/post/5ab0568b5188255580020e56
    • https://link.juejin.im/?target=http%3A%2F%2Fwww.cnblogs.com%2Fchengxiao%2Fp%2F6842045.html

    • 1 二叉树

    https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91(百度百科)

    (1)https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

    (2)https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

    (3)https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/10421057——平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    • 2 完全二叉树

    https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91(百度百科)

    完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

    • 3 满二叉树

    https://baike.baidu.com/item/%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91(百度百科,国内外的定义不同)

    国内教程定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

    https://blog.csdn.net/qq_33186366/article/details/51876191

    堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

    • 4 二叉查找树(BST)

    http://www.cnblogs.com/yangecnu/p/Introduce-Binary-Search-Tree.html

    二叉查找树的特点:

    1. 若任意节点的左子树不空,则左子树上所有结点的 值均小于它的根结点的值;
    2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    3. 任意节点的左、右子树也分别为二叉查找树。
    4. 没有键值相等的节点(no duplicate nodes)。
    • 5 平衡二叉树(Self-balancing binary search tree)

    https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91(百度百科,平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等)

    • 6 红黑树
    • 红黑树特点:
    1. 每个节点非红即黑;
    2. 根节点总是黑色的;
    3. 每个叶子节点都是黑色的空节点(NIL节点);
    4. 如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
    5. 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
    • 红黑树的应用:
     TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。
    • 为什么要用红黑树
     简单来说红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。详细了解可以查看 [漫画:什么是红黑树?](https://juejin.im/post/5a27c6946fb9a04509096248#comment)(也介绍到了二叉查找树,非常推荐)
    • 推荐文章:
     - [漫画:什么是红黑树?](https://juejin.im/post/5a27c6946fb9a04509096248#comment)(也介绍到了二叉查找树,非常推荐) - [寻找红黑树的操作手册](http://dandanlove.com/2018/03/18/red-black-tree/)(文章排版以及思路真的不错) - [红黑树深入剖析及Java实现](https://zhuanlan.zhihu.com/p/24367771)(美团点评技术团队) 
    • 7 B-,B+,B*树

    https://yq.aliyun.com/articles/38345

    https://blog.csdn.net/aqzwss/article/details/53074186

    https://blog.csdn.net/bigtree_3721/article/details/73632405

    B-树(或B树)是一种平衡的多路查找(又称排序)树,在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)

    1. B+ 树的叶子节点链表结构相比于 B- 树便于扫库,和范围检索。
    2. B+树支持range-query(区间查询)非常方便,而B树不支持。这是数据库选用B+树的最主要原因。
    3. B*树 是B+树的变体,B*树分配新结点的概率比B+树要低,空间使用率更高;
    5576a9ac96a5785409a2716b70e43c26.png
    1. QQ讨论群组:984370849 706564342 欢迎加入讨论

    想要深入学习的同学们可以加入QQ群讨论,有全套资源分享,经验探讨,没错,我们等着你,分享互相的故事!

    b3f01371a398444defde4411af883e53.png
    展开全文
  • 红黑树是一个比较复杂的数据结构,相信很多人也只知其名而不知其意,因为理解它的原理确实需要花费一定的功夫。之所以写这篇文章,也是为了更好的理解 Java 中 TreeMap 的源码。写之前,搜了下网上的文章,说实话,...
  • TreeMap底层使用红黑树的结构进行数据的增删改查,红黑树是一种自平衡的二叉查找树,想了解红黑树推荐看看这篇博文:30张图带你彻底理解红黑树。学过数据结构的都知道二叉查找树是一种有序树,即进行中序遍历可以...
  • 本章节主要分析红黑树的“插入算法”和“获取算法”,也就是put()方法和get()方法的底层实现。 在学习TreeMap的put()方法之前,我们首先应该创建一个叶子节点Entry类,叶子节点Entry是TreeMap的内部类,它有几个重要...
  • 概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是...而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序。这点会在接下...
  • 继承关系 1.TreeMap存储K-V键值对,通过红黑树(R-B tree)实现; 2.TreeMap继承了NavigableMap接口,...4.TreeMap因为是通过红黑树实现,红黑树结构天然支持排序,默认情况下通过Key值的自然顺序进行排序; 基本属
  • TreeMap 底层数据存储结构探究
  • TreeMap底层数据结构在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择LinkedHashMap,那...
  • TreeMap底层原理

    千次阅读 2018-11-02 14:39:31
    TreeMap是桶+红黑树的实现方式.TreeMap底层结构就是一个数组,数组中每一个元素又是一个红黑树.当添加一个元素(key-value)的时候,根据key的hash值来确定插入到哪一个桶中(确定插入数组中的位置),当桶中有多个元素时...
  • 底层数据结构 : 红黑树 使用TreeMap存储自定义数据时需要定义比较器 import java.util.Comparator; import java.util.TreeMap; public class TestTreeMap { /*** * TreeMap底层实现 * * private final ...
  • 1. HashMap的原理,内部数据结构底层使用哈希表(数组 + 链表),当链表过长会将链表转成 红黑树以实现 O(logn) 时间复杂度内查找 2. 讲一下 HashMap 中 put 方法过程? 对 Key 求 Hash 值,然后再计算 下标...
  • 1、红黑树的基本概念。 每个节点都只能是红色或者黑色 根节点是黑色 每个叶节点(NIL节点,空节点)是黑色的。...二、TreeMap数据结构 TreeMap的定义如下: public class TreeMap<K,V> extend
  • TreeMap底层的数据结构与存储结构基于红黑树(Red-Black tree)的 NavigableMap 实现(是自平衡的二叉树)。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造...
  • 5.remove()方法剖析remove(Object key)的作用是删除key值对应的entry,该方法首先通过上文中提到的...由于删除操作会改变红黑树的结构,有可能破坏红黑树的约束,因此有可能要进行调整。这里先说下关于后继节...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 702
精华内容 280
关键字:

treemap底层结构