精华内容
下载资源
问答
  • 从上面分析得出:synchronized关键字底层实现主要是通过monitor对象去完成的,修饰的位置不同,实现的方式有点差异,但是底层都是通过monitor对象去实现的。后面还讲了JDK1.6对synchronized关键字做出的锁优化。 ...

    ????相信对Java程序员来说,synchronized关键字对大家来说并不陌生,当我们遇到并发情况时,优先会想到用synchronized关键字去解决,synchronized确实能够帮助我们去解决并发的问题,但是它会引起一些其他问题,比如最突出的一点就是程序效率问题,不过后面随着JDK1.6对synchronized关键字做出了许多优化,让synchronized和java.util.concurrent.locks.ReentrantLock等并发包中的类效率差不多。下面主要来分析一下synchronized底层的实现原理

    1 基本使用

    ????synchronized关键字可以用来修饰三个地方:

    1.synchronized放在实例方法上,锁对象是当前的this对象

    2.synchronized放在类方法上,也就是我们所说的静态方法上,锁对象是方法区中的类对象,是一个全局锁

    3.synchronized修饰代码块,也就是synchronized(object){},锁对象是()中的对象

    synchronized关键字用来修饰的位置不同,其实现原理也是不同的。锁住的对象也是不同的。在Java中,每个对象里面隐式的存在一个叫monitor(对象监视器)的对象,这个对象源码是采用C++实现的,下面来看一下Monitor对象的源码:

    ObjectMonitor() {

    _header = NULL;

    _count = 0; // 记录个数

    _waiters = 0,

    _recursions = 0;

    _object = NULL;

    _owner = NULL;

    _WaitSet = NULL; // 处于wait状态的线程,会被加入到_WaitSet

    _WaitSetLock = 0 ;

    _Responsible = NULL ;

    _succ = NULL ;

    _cxq = NULL ;

    FreeNext = NULL ;

    _EntryList = NULL ; // 处于等待锁block状态的线程,会被加入到该列表

    _SpinFreq = 0 ;

    _SpinClock = 0 ;

    OwnerIsThread = 0 ;

    }

    当monitor对象被线程持有时,Monitor对象中的count就会进行+1,当线程释放monitor对象时,count又会进行-1操作。用count来表示monitor对象是否被持有

    2 同步原理

    ????针对synchronized修饰的地方不同,实现的原理不同

    1.先看synchronized放在实例方法上的代码:

    public class Test {

    public synchronized void test() {

    }

    }

    用javap -verbose查看反编译结果:

    519d7569e67cd99dcd162c0732138561.png

    从反编译的结果来看,我们可以看到test()方法中多了一个标识符。JVM就是根据该ACC_SYNCHRONIZED标识符来实现方法的同步:

    当方法被执行时,JVM调用指令会去检查方法上是否设置了ACC_SYNCHRONIZED标识符,如果设置了ACC_SYNCHRONIZED标识符,则会获取锁对象的monitor对象,线程执行完方法体后,又会释放锁对象的monitor对象。在此期间,其他线程无法获得锁对象的monitor对象

    2.第二种情况,synchronized放在类方法上:

    public class Test {

    public synchronized static void test(){

    }

    }

    反编译结果:

    3da7d49468af275e007029d2dc2339cd.png

    我们可以看到跟放在实例方法相同,也是test()方法上会多一个标识符。可以得出synchronized放在实例方法上和放在类方法上的实现原理相同,都是ACC_SYNCHRONIZED标识符去实现的。只是它们锁住的对象不同

    3.第三种情况,synchronized修饰代码块:

    public class Test {

    public void test(){

    synchronized (this) {

    }

    }

    }

    反编译结果:

    1127a4981cbfb68038b8a2b8c09cbe6f.png

    我们可以看到test()字节码指令中会有两个monitorenter和monitorexit指令,

    (1)monitorenter: monitorenter指令表示获取锁对象的monitor对象,这是monitor对象中的count并会加+1,如果monitor已经被其他线程所获取,该线程会被阻塞住,直到count=0,再重新尝试获取monitor对象

    (2)monitorexit: monitorexit与monitorenter是相对的指令,表示进入和退出。执行monitorexit指令表示该线程释放锁对象的monitor对象,这时monitor对象的count便会-1变成0,其他被阻塞的线程可以重新尝试获取锁对象的monitor对象

    从synchronized放置的位置不同可以得出,synchronized用来修饰方法时,是通过ACC_SYNCHRONIZED标识符来保持线程同步的。而用来修饰代码块时,是通过monitorenter和monitorexit指令来完成

    3 同步概念

    3.1 Java对象头

    ????像我们上面所提到的monitor监视器对象存在于Java对象的对象头Mark Word中,

    什么是Java对象头的Mark Word了?这就跟Java对象在JVM中的内存布局有关系,Java对象在JVM内存中分为三块区域:对象头,实例数据和对齐填充。

    1. 对象头:对象头又包含以下部分:Mark Word, 类型指针,如果对象是数组的话,还会存在一个数据数组长度,用来记录数据长度。其中Mark Word又包含:哈希码(HashCode),GC分代年龄,锁状态标志,线程持有的锁等信息。

    2. 实例数据:这部分是对象真正存储的有效信息,也就是我们在程序中所定义的各种类型的字段内容。

    3. 对齐填充:这部分数据并不是必然存在的,JVM内存管理系统要求我们定义的对象大小必须是8字节的整数倍,如果对象大小不是整数倍,这时就会有对齐填充这块数据,来将对象大小补全成为8字节的整数倍

    如果所示:

    553ff156ac6cbc34aa3c155717c904e5.png

    JDK对synchronized关键字的优化都是基于对象头中的Mark Word进行优化的,当对象被不同数量线程去竞争时,这是对象的锁状态会发生改变,来标识这时对象处于一个无锁,偏向锁,轻量级锁和重量级锁状态。

    下面结合锁的优化,来讲一下Mark Word中的锁状态发生的变化:

    无锁

    也就是代表对象的monitor对象并没有被线程所持有,代表的是对象处于无锁状态

    偏向锁

    偏向锁是JDK1.6后面引起的一项锁优化技术,是单线程执行代码块时使用的机制,如果出现多线程的情况,这时偏向锁便会升级成轻量级锁和重量级锁。偏向锁指的是这个锁会偏向于第一个获得它的线程。

    下面来看一下对象在无锁和偏向锁状态下,Mark Word的锁状态位变化:

    466d6e9846bf8d9f792d6ac59bd4499d.png

    ?

    我们可以看到这是偏向锁的标志位被至为了1,表示现在处于偏向模式

    3.轻量级锁

    ?表示线程通过CAS操作完成加锁和解锁操作,如果锁获取失败,会通过自旋来获取,竞争的线程不会阻塞,如果还是获取失败,表示此时存在其他线程竞争锁(两条或两条以上的线程竞争同一个锁),则轻量级锁会膨胀成重量级锁。

    4.重量级锁

    ?当一个锁被两条或两条以上的线程竞争的时候,这时候轻量级锁就会演变成重量级锁。

    在轻量级锁和重量级锁的情况下,锁状态标记位:

    756bdd5b4a69be9300ec9b7fdc4cbdca.png

    ????除了以上几种锁外,其实还有自旋锁,自适应自旋锁

    5.自旋锁

    ?当两个线程去竞争同一把锁时,一个线程获取成功,一个线程获取失败,这时可能会出现获取成功的线程持有锁的时间非常短,如果这时候将获取失败的线程进行挂起的话,会造成功线程上下文的切换,到时候又需要唤醒线程,这时我们可以让获取失败的线程进行一个自旋,无需将线程挂起。等到锁释放。但是这种方案适用于锁被占用的时间很短的情况,如果锁被持有的时间很长,然后线程将会一直处于自旋状态,白白消耗处理器资源。自旋等待的时间必须要有一定的限度,如果超过此数还是没有获取到,则将线程挂起。自旋此数的默认值是10次,可以使用JVM参数-XX:PreBlockSpin来进行更改。

    6.自适应自旋锁

    ?自适应自旋锁是在自旋锁的基础上产生的,进行了一次优化。自适应意味着自旋的时间不再固定,而是由前一次在同一个锁上的自旋时间几锁的拥有者的状态来决定的。

    锁的优缺点对比

    d3087359e70ea371b6d451af69c1178b.png

    结论:

    ????从上面分析得出:synchronized关键字底层实现主要是通过monitor对象去完成的,修饰的位置不同,实现的方式有点差异,但是底层都是通过monitor对象去实现的。后面还讲了JDK1.6对synchronized关键字做出的锁优化。

    原文:https://www.cnblogs.com/semi-sub/p/12906660.html

    展开全文
  • JDK1.8HashMap底层实现原理

    多人点赞 热门讨论 2021-05-24 18:25:48
    hashmap是我们开发中用的最常见的集合之一,但是我们是否有了解过他的底层呢?这篇文章我将带您了解一下hashmap的底层 ...在学习hashmap底层原理的时候,我们必须要掌握位运算,别问为什么,往下面看自然知晓 ...

    hashmap是我们开发中用的最常见的集合之一,但是我们是否有了解过他的底层呢?这篇文章我将带您了解一下hashmap的底层

    位运算

    在学习hashmap底层原理的时候,我们必须要掌握位运算,别问为什么,往下面看自然知晓

    我们知道,计算机用的是二进制,也就是010101…这样的字符,当我们输入某一个数字的时候,存入计算机里面的也是二进制譬如说

    • 0-》00000000
    • 1-》00000001
    • 2-》00000010
    • 3-》00000011

    &(按位与)

    参加运算的两个二进制数,同时为1,才为1,否则为0。举例 3&5=1。

    在这里插入图片描述

    |(按位或)

    参加运算的两个二进制数,一个为1就为1,否则为0。2 | 4=6

    在这里插入图片描述

    ^(按位异或)

    参加运算的两个二进制数,位不同则为1,位相同则为0。6^7=1

    在这里插入图片描述

    << (左位移运算符)

    将二进制码整体左移指定位数,左移后空出来的位用“0”填充,例如 -5 << 2 = -20

    例如:2<<4
    00000010->00100000=16

    “>>”(右位移运算符)与 >>(无符号右位移运算符)

    例如:16>>4
    00100000->00000010=2

    好了,现在了解了位运算,那么我们来了解一下hashmap

    hashmap的概述

    • HashMap 基于哈希表的 Map 接口实现,是以 key-value 存储形式存在,即主要用来存放键值对。
    • HashMap 的实现不是同步的,这意味着它不是线程安全的。它的 key、value 都可以为 null,此外,HashMap中的映射不是有序的。
    • jdk1.8 之前 HashMap 由 数组 + 链表 组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突(两个对象调用的hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用)而存在的(“拉链法”解决冲突)。
    • jdk1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64时,此时此索引位置上的所有数据改为使用红黑树存储。

    HashMap 特点:

    • 存储无序;
    • 键和值位置都可以是 null,但是键位置只能存在一个 null;
    • 键位置是唯一的,是由底层的数据结构控制的;
    • jdk1.8 前数据结构是链表+数组,jdk1.8 之后是链表+数组+红黑树;
    • 阈值(边界值)> 8 并且桶位数(数组长度)大于 64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询;

    HashMap存储数据的过程

    测试代码

     public static void main(String[] args) {
            HashMap map=new HashMap();
            map.put("student1","萧炎");
            map.put("student2","林动");
            map.put("student3","牧尘");
            map.put("student4","古尘沙");
            System.out.println(map);
        }
    

    结果

    在这里插入图片描述

    执行流程分析:

    • 首先程序读到HashMap map=new HashMap();的时候,并不会马上创建一个数组,而是在我们第一次使用hashmap自己的put方法的时候,创建一个长度为16的数组,也叫作桶Node[]table ,这个用来存储数据

    • 当我们需要存入一个数据,比方说(key=a,value=3),首先会先调用重写的String的hashcode方法,计算出对应的hash数值,然后根据数组的长度和某种算法,找到这组数据应该对应的桶位数,就是数组的下标,例如0,1,2,3,4,5…然后查看这个桶里面是否有存其他的数据,如果没有,那么就直接把数据存入桶中,我们加入这一次存在‘3’这个位置
      在这里插入图片描述

    • 当我们又再一次的调用put方法,存入(key=b,value=4)的时候,假设这次算出来的又是存在三号位,这个时候,三号位已经有一个数据了,这个时候会判断两个数据的hash值是否相同,如果不相同,那我们这个时候就会在这个桶下生成一个链表,用来存储数据,这个叫做拉链法

    • 如果相同的话则会对两个数据进行一次判断
      数据相同:直接覆盖
      数据不同:从该桶位的链表开始,一直往下比,直到出现不同的时候,便存在不同的地方的下一个位置,如果这个时候链表长度超过了8,那么链表就会转化成红黑树

    • 在不断的添加新数据的时候,如果某一时刻超过了阈值,并且那个时候要存入数据的地方刚好不为空,那么,我们就要扩容了,每次扩容都是在原来的基础上,扩大2倍,原因后面会讲。

    在这里插入图片描述

    jdk1.8 中引入红黑树的进一步原因:

    1. jdk1.8 以前 HashMap 的实现是数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有n个元素,遍历的时间复杂度就是O(n),完全失去了它的优势。
    2. 针对这种情况,jdk1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题。当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。

    在这里插入图片描述

    HashMap继承体系

    在这里插入图片描述
    从继承体系可以看出:

    • HashMap 实现了Cloneable接口,可以被克隆。
    • HashMap 实现了Serializable接口,属于标记性接口,HashMap 对象可以被序列化和反序列化。
    • HashMap 继承了AbstractMap,父类提供了 Map 实现接口,具有Map的所有功能,以最大限度地减少实现此接口所需的工作。

    存储结构

    在这里插入图片描述
    在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作
    在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。
    当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率。
    数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。

    HashMap基本属性与常量

    基本属性,常量一览

    /*
     * 序列化版本号
     */
    private static final long serialVersionUID = 362498820763181265L;
    
    /**
     * HashMap的初始化容量(必须是 2 的 n 次幂)默认的初始容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    /**
     * 最大的容量为2的30次方
     */
    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;
    
    /**
     * Node数组,又叫作桶(bucket)
     */
    transient Node<K,V>[] table;
    
    /**
     * 作为entrySet()的缓存
     */
    transient Set<Map.Entry<K,V>> entrySet;
    
    /**
     * 元素的数量
     */
    transient int size;
    
    /**
     * 修改次数,用于在迭代的时候执行快速失败策略
     */
    transient int modCount;
    
    /**
     * 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor
     */
    int threshold;
    
    /**
     * 装载因子
     */
    final float loadFactor;
    
    
    • 容量:容量为数组的长度,亦即桶的个数,默认为16 ,最大为2的30次方,当容量达到64时才可以树化。
    • 装载因子:装载因子用来计算容量达到多少时才进行扩容,默认装载因子为0.75。
    • 树化:树化,当容量达到64且链表的长度达到8时进行树化,当链表的长度小于6时反树化。

    Hashmap属性解释

    DEFAULT_INITIAL_CAPACITY

    集合的初始化容量(必须是 2 的 n 次幂):

    // 默认的初始容量是16	1 << 4 相当于 1*2的4次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    

    提问:为什么是2的次幂呢?如果输入值不是 2 的幂比如 10 会怎么样?

     /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
    
    • HashMap 构造方法可以指定集合的初始化容量大小,根据上述讲解我们已经知道,当向 HashMap 中添加一个元素的时候,需要根据 keyhash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现的关键就在把数据存到哪个链表中的算法。
    • 这个算法实际就是取模,hash % length,而计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash & (length - 1),而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是2 的 n 次幂。(这段话是摘抄传智播客锁哥的,这个解释确实很完美!)

    例如,数组长度为 8 的时候,3 & (8 - 1) = 3,2 & (8 - 1) = 2,桶的位置是(数组索引)3和2,不同位置上,不碰撞。
    再来看一个数组长度(桶位数)不是2的n次幂的情况:

    数组长度为9 hash为3

    00000011 3
    00001000 8
    ————————
    00000000 0

    数组长度为9 hash为5

    00000101 5
    00001000 8
    ————————
    00000000 0

    数组长度为9,hash为6

    00000101 5
    00001000 8
    ————————
    00000000 0

    由此可见,如果不是2的次幂,hash值很容易一模一样,这样会经常产生哈希碰撞,导致性能下降,所以,这里采用的是2的次幂

    为什么要用2的次幂小结:

    • 由上面可以看出,当我们根据key的hash确定其在数组的位置时,如果n为2的幂次方,可以保证数据的均匀插入,如果n不是2的幂次方,可能数组的一些位置永远不会插入数据,浪费数组的空间,加大hash冲突。
    • 另一方面,一般我们可能会想通过%求余来确定位置,这样也可以,只不过性能不如&运算。而且当n是2的幂次方时: hash & (length1) == hash % length
    • 因此,HashMap容量为2次幂的原因,就是为了数据的的均匀分布,减少hash冲突,毕竟hash冲突越大,代表数组中一个链的长度越大,这样的话会降低hashmap的性能

    如果创建HashMap对象时,输入的数组长度length是10,而不是2的n次幂会怎么样呢?

    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会采用一个tableSizeFor()方法,通过这个方法,把数组长度设置成最接近自己输入数组长度数量的2的次幂的数量例如如果我输入10,最后返回的就是16,我输入5,那么返回的便是8,我们复制一下这个方法,自己测试 一下

    public class Test01 {
        public static void main(String[] args) {
            System.out.println(tableSizeFor(12));
        }
    
        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 + 1;
        }
    }
    
    

    int n = cap - 1;为什么要减去1呢?

    防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂,又没有这个减 1 操作,则执行完后面的几条无符号操作之后,返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)。

    最后为什么有个 n + 1 的操作呢?

    如果 n 这时为 0 了(经过了cap - 1后),则经过后面的几次无符号右移依然是 0,返回0是肯定不行的,所以最后返回n+1最终得到的 capacity 是1。
    注意:容量最大也就是 32bit 的正数,因此最后 n |= n >>> 16;最多也就 32 个 1(但是这已经是负数了,在执行 tableSizeFor 之前,对 initialCapacity 做了判断,如果大于MAXIMUM_CAPACITY(2 ^ 30),则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY,会执行位移操作。所以这里面的位移操作之后,最大 30 个 1,不会大于等于 MAXIMUM_CAPACITY。30 个 1,加 1 后得 2 ^ 30)。

    完整例子

    在这里插入图片描述

    DEFAULT_LOAD_FACTOR

    负载因子:默认为0.75

    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    

    MAXIMUM_CAPACITY

    static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂
    
    

    集合最大容量:为2的30次方

    TREEIFY_THRESHOLD

    当桶(bucket)上的结点数大于这个值时会转为红黑树

    // 当桶(bucket)上的结点数大于这个值时会转为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    

    为什么 Map 桶中结点个数超过 8 才转为红黑树?

    8这个阈值定义在HashMap中,针对这个成员变量,在源码的注释中只说明了 8 是 bin( bucket 桶)从链表转成树的阈值,但是并没有说明为什么是 8。

    在 HashMap 中有一段注释说明:

    Because TreeNodes are about twice the size of regular nodes, we use them only when bins
    contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too
    small (due to removal or resizing) they are converted back to plain bins.  In usages with
    well-distributed user hashCodes, tree bins are rarely used.  Ideally, under random hashCodes, 
    the frequency of nodes in bins follows a Poisson distribution 
    (http://en.wikipedia.org/wiki/Poisson_distribution) 
    with a parameter of about 0.5 on average for the default resizing
    threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, 
    the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
    
    翻译:因为树结点的大小大约是普通结点的两倍,所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
    当它们变得太小(由于删除或调整大小)时,就会被转换回普通的桶。在使用分布良好的用户 hashCode 时,很少使用树箱。
    理想情况下,在随机哈希码下,箱子中结点的频率服从泊松分布。
    默认调整阈值为0.75,平均参数约为0.5,尽管由于调整粒度的差异很大。忽略方差,列表大小k的预朗出现次数是(exp(-0.5)*pow(0.5, k) / factorial(k)
    第一个值是:
    
    0:    0.60653066
    1:    0.30326533
    2:    0.07581633
    3:    0.01263606
    4:    0.00157952
    5:    0.00015795
    6:    0.00001316
    7:    0.00000094
    8:    0.00000006
    more: less than 1 in ten million
    
    

    一句话概括:
    hashCode 算法下所有 桶 中结点的分布频率会遵循泊松分布,这时一个桶中链表长度超过 8 个元素的槪率非常小,权衡空间和时间复杂度,所以选择 8 这个数宇。

    UNTREEIFY_THRESHOLD

    当链表长度低于6会从红黑树转化成链表

    // 当桶(bucket)上的结点数小于这个值,树转为链表 
    static final int UNTREEIFY_THRESHOLD = 6;
    
    

    MIN_TREEIFY_CAPACITY

    当 Map 里面的数量超过这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4*TREEIFY_THRESHOLD(8)

    // 桶中结构转化为红黑树对应的数组长度最小的值 
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    

    table(重点)

    table 用来初始化(必须是二的n次幂)

    // 存储元素的数组 
    transient Node<K,V>[] table;
    
    

    在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry<K,V> 类型。从 jdk1.8 之后是 Node<K,V> 类型。只是换了个名字,都实现了一样的接口:Map.Entry<K,V>。负责存储键值对数据的。

    entrySet

    用来放缓存

    // 存放具体元素的集合
    transient Set<Map.Entry<K,V>> entrySet;
    
    

    size(重点)

    HashMap 中存放元素的个数

    // 存放元素的个数,注意这个不等于数组的长度
     transient int size;
    
    

    size 为 HashMap 中 K-V 的实时数量,不是数组 table 的长度。

    modCount

    用来记录 HashMap 的修改次数

    // 每次扩容和更改 map 结构的计数器
     transient int modCount;  
    
    

    threshold(重点)

    用来调整大小下一个容量的值计算方式为(容量*负载因子)

    // 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
    int threshold;
    
    

    loadFactor(重点)

    哈希表的负载因子

    // 负载因子
    final float loadFactor;// 0.75f
    
    

    说明:

    • oadFactor 是用来衡量 HashMap 满的程度,表示HashMap的疏密程度,影响 hash 操作到同一个数组位置的概率,计算HashMap 的实时负载因子的方法为:size/capacity,而不是占用桶的数量去除以 capacity。capacity是桶的数量,也就是 table 的长度 length。
    • loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f是官方给出的一个比较好的临界值。
    • 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap
      太挤了,需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能。所以开发中尽量减少扩容的次数,可以通过创建HashMap 集合对象时指定初始容量来尽量避免。
    • 在 HashMap 的构造器中可以定制 loadFactor。
    // 构造方法,构造一个带指定初始容量和负载因子的空HashMap
    HashMap(int initialCapacity, float loadFactor);
    
    

    为什么负载因子loadFactor 设置为0.75,初始化临界值threshold是12?

    loadFactor 越趋近于1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于0,数组中存放的数据(entry)也就越少,也就越稀疏。
    在这里插入图片描述
    如果希望链表尽可能少些,要提前扩容。有的数组空间有可能一直没有存储数据,负载因子尽可能小一些。

    例举:

    例如:负载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。
    	 负载因子是0.9。 那么16*0.9--->14 那么这样就会导致链表有点多了,导致查找元素效率低。
    
    

    所以既兼顾数组利用率又考虑链表不要太多,经过大量测试 0.75 是最佳方案。

    threshold 计算公式:capacity(数组长度默认16) * loadFactor(负载因子默认0.75)==12。

    这个值是当前已占用数组长度的最大值。当 Size >= threshold(12) 的时候,那么就要考虑对数组的 resize(扩容),也就是说,这个的意思就是 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍。

    HashMap扩容机制

     /**
         * Initializes or doubles table size.  If null, allocates in
         * accord with initial capacity target held in field threshold.
         * Otherwise, because we are using power-of-two expansion, the
         * elements from each bin must either stay at same index, or move
         * with a power of two offset in the new table.
         *
         * @return the table
         */
        final Node<K,V>[] resize() {
            //把旧的table 赋值个一个变量
            Node<K,V>[] oldTab = table;
            //获取旧的tabel的长度
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 旧的阈值
            int oldThr = threshold;
            int newCap, newThr = 0;
        
            if (oldCap > 0) {
                //判断数组的长度是否大约等于最大值
                if (oldCap >= MAXIMUM_CAPACITY) {
                    //如果数组的长度达到了最大值,那么就不在进行扩容,直接返回,不管了任由hash冲突
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                //把旧的数组长度左移一位(也就是乘以2),然后判断是否小于最大值,并且判断旧的数组长度是否大于等于默认的长度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 {               // 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;
            @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;
                        //如果没有子元素那么说明是下面不是一个链表,直接通过 hash&(新的数组长度-1)计算出新的位置,把就的数据放入新的位置
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        //如果该节点为红黑树结构,就进行树的操作
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            //有多个数据并且不是树那么该节点上放的是链表
                            //这里是java1.8很精妙的地方,如果 e.hash& 旧的数组长度 如果等于0
                            那么该数据的位置没有发生变化,还在原来的索引位置上,如果不等于0 那么就在该值就在 (原来的索引位置+旧的数组长度)的位置上,
                            这里重新创建了两个节点,在原来位置上的放入loHead中,在新的位置上的放入
    hiHead 中,最后把这两组数据放入新的数组中即可。(这里的精妙之处是不用重新计算每一个数据的hash,就可以把旧的数据放入新的数组中去)
                            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;
        }
    

    在这里插入图片描述

    内部类

    Node内部类

    Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;// hash用来存储key计算得来的hash值
        final K key;// 键
        V value;// 值
        Node<K,V> next;// 下一个node节点
        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() {// 调用底层c++ 返回Key/Value的哈希码值,如果此对象为null,则返回0
            return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule
        }
        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;
        }
    }
    
    

    HashMap构造方法

    HashMap()

    构造一个空的HashMap,默认初始容量(16)和默认负载因子(0.75)。

    public HashMap() {
       // 将默认的负载因子0.75赋值给loadFactor,并没有创建数组
       this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    

    HashMap(int initialCapacity)

    构造一个具有指定的初始容量和默认负载因子(0.75)HashMap 。

    // 指定“容量大小”的构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    

    HashMap(int initialCapacity,float loadFactor)构造方法

    构造一个具有指定的初始容量和负载因子的 HashMap。

    /*
    	 指定“容量大小”和“负载因子”的构造函数
    	 initialCapacity:指定的容量
    	 loadFactor:指定的负载因子
    */
    public HashMap(int initialCapacity, float loadFactor) {
        	// 判断初始化容量initialCapacity是否小于0
            if (initialCapacity < 0)
                // 如果小于0,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
            if (initialCapacity > MAXIMUM_CAPACITY)
                // 如果超过MAXIMUM_CAPACITY,会将MAXIMUM_CAPACITY赋值给initialCapacity
                initialCapacity = MAXIMUM_CAPACITY;
        	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                // 如果满足上述其中之一,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
         	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
            this.loadFactor = loadFactor;// 一般不建议修改默认的负载因子
            this.threshold = tableSizeFor(initialCapacity);
        }
    	// 最后调用了tableSizeFor,来看一下方法实现:
         /*
         	返回比指定cap容量大的最小2的n次幂数:
         	前面第一遍讲述的应该有些小伙伴难以理解,这里我在举例解析一下:
         	-------------------------------------------------------
         	首先假定传入的cap = 10
         	则,n = 10 -1 => 9
         	n |= n >>> 1 就等同于 n = (n | n >>> 1),所以:
         	(位运算不懂的可以去看我的《Java基础提高之位运算》这篇文章)
         	9 => 0b1001    9 >>> 1 => 0b0100 
         	n |= n >>> 1;  ===>  0b1001 | 0b0100 => 0b1101
         	n |= n >>> 2;  ===>  0b1101 | 0b0011 => 0b1111
            n |= n >>> 4;  ===>  0b1111 | 0b0000 => 0b1111
            n |= n >>> 8;  ===>  0b1111 | 0b0000 => 0b1111
            n |= n >>> 16; ===>  0b1111 | 0b0000 => 0b1111
            得到:
            0b1111 => 15
            返回:
            return 15 + 1 => 16
            -------------------------------------------------------
            如果cap 不减去1,即直接使n等于cap的话,int n = cap;
            我们继续用上边返回的cap => 16 传入tableSizeFor(int cap):
            
            cap = 16
            n = 16
            16 => 0b10000  16 >>> 1 => 0b01000
            n |= n >>> 1;  ===>  0b10000 | 0b01000 => 0b11000
            n |= n >>> 2;  ===>  0b11000 | 0b00110 => 0b11110
            n |= n >>> 4;  ===>  0b11110 | 0b00001 => 0b11111
            n |= n >>> 8;  ===>  0b11111 | 0b00000 => 0b11111
            n |= n >>> 16; ===>  0b11111 | 0b00000 => 0b11111
            得到:
            0b11111 => 31
            返回 return 31 +1 => 32
            
            而实际情况是应该传入cap = 16 , n = cap -1 = 15
            15 => 0b1111 
            
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            经过上面运算后得到:还是15
            
            返回结果:
            return 15 + 1 = 16
            所以我们得出结果:
            防止 cap 已经是 2 的幂数情况下。没有这个减 1 操作,
            则执行完几条无符号位移或位运算操作之后,返回的cap(32)将是实际所需cap(16)的 2倍。
         */
        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;
        }
    
    
    

    说明:
    对于this.threshold = tableSizeFor(initialCapacity); 疑问?
    tableSizeFor(initialCapacity)**判断指定的初始化容量是否是2的n次幂,如果不是那么会变为比指定初始化容量大的最小的2的n次幂。

    但是注意,在tableSizeFor方法体内部将计算后的数据返回给调用这里了,并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写:
    this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

    这样才符合threshold的意思(当HashMap的size到达threshold这个阈值时会扩容)

    但是请注意,在jdk8以后的构造方法中,并没有对table这个成员变量进行初始化,table的初始化被推迟到了put方法中,在put方法中会对threshold重新计算。

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

    包含另一个 “Map” 的构造函数

    // 构造一个映射关系与指定 Map 相同的新 HashMap。
    public HashMap(Map<? extends K, ? extends V> m) {
        	// 负载因子loadFactor变为默认的负载因子0.75
             this.loadFactor = DEFAULT_LOAD_FACTOR;
             putMapEntries(m, false);
     }
    
    

    最后调用了 putMapEntries(),来看一下方法实现:

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取参数集合的长度
        int s = m.size();
        if (s > 0) {//判断参数集合的长度是否大于0
            if (table == null) { // 判断table是否已经初始化
                    // 未初始化,s为m的实际元素个数
                    float ft = ((float)s / loadFactor) + 1.0F;// 得到新的扩容阈值
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 新的扩容阈值float自动向下转型为int
                
                    // 计算得到的t大于阈值,则初始化阈值,将其变为符合要求的2的n次幂数
                    if (t > threshold)
                        threshold = tableSizeFor(t);
            }
            // 如果table已初始化过了,并且m元素个数大于阈值,进行扩容处理
            else if (s > threshold)
                resize();
            // 将m中的所有元素添加至HashMap中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 得到的key 和 value 放入 hashmap
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    
    

    注意:

    float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?

    (float)s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数(为了效率,应当尽量减少扩容的次数)。所以 + 1.0F 是为了获取更大的容量。
    例如:原来集合的元素个数是 6 个,那么 6/0.75 是8,由于8是 2 的n次幂,那么
    if (t > threshold) threshold = tableSizeFor(t);执行过后,新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。

    展开全文
  • ArrayList底层实现原理

    2021-02-27 17:45:04
    ArrayList底层实现原理ArrayList 的实现原理ArrayList 概述ArrayList 可以理解为动态数组,用 MSDN 中的说法,就是 Array 的复杂版本。与 Java 中的数组相比,它的容量能动态增长。ArrayList 是 List 接口的可变数组...

    ArrayList底层实现原理

    ArrayList 的实现原理

    ArrayList 概述

    ArrayList 可以理解为动态数组,用 MSDN 中的说法,就是 Array 的复杂版本。与 Java 中的数组相比,它的容量能动态增长。ArrayList 是 List 接口的可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于 Vector 类,除了此类是不同步的。)

    每个 ArrayList 实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向 ArrayList 中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造 ArrayList 时指定其容量。在添加大量元素前,应用程序也可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量,这可以减少递增式再分配的数量。

    注意,此实现不是同步的。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)

    我们先学习了解其内部的实现原理,才能更好的理解其应用。

    ArrayList 的实现

    对于 ArrayList 而言,它实现 List 接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析 ArrayList 的源代码:

    实现的接口

    public class ArrayList extends AbstractList

    implements List, RandomAccess, Cloneable, java.io.Serializable

    {

    }

    ArrayList 继承了 AbstractList,实现了 List。它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能。

    ArrayList 实现了 RandmoAccess 接口,即提供了随机访问功能。RandmoAccess 是 java 中用来被 List 实现,为 List 提供快速访问功能的。在 ArrayList 中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问。

    ArrayList 实现了 Cloneable 接口,即覆盖了函数 clone(),能被克隆。 ArrayList 实现 java.io.Serializable 接口,这意味着 ArrayList 支持序列化,能通过序列化去传输。

    底层使用数组实现

    /**

    * The array buffer into which the elements of the ArrayList are stored.

    * The capacity of the ArrayList is the length of this array buffer.

    */

    private transient Object[] elementData;

    构造方法

    /**

    * Constructs an empty list with an initial capacity of ten.

    */

    public ArrayList() {

    this(10);

    }

    /**

    * Constructs an empty list with the specified initial capacity.

    *

    * @param initialCapacity the initial capacity of the list

    * @throws IllegalArgumentException if the specified initial capacity

    * is negative

    */

    public ArrayList(int initialCapacity) {

    super();

    if (initialCapacity < 0)

    throw new IllegalArgumentException("Illegal Capacity: "+

    initialCapacity);

    this.elementData = new Object[initialCapacity];

    }

    /**

    * Constructs a list containing the elements of the specified

    * collection, in the order they are returned by the collection's

    * iterator.

    *

    * @param c the collection whose elements are to be placed into this list

    * @throws NullPointerException if the specified collection is null

    */

    public ArrayList(Collection extends E> c) {

    elementData = c.toArray();

    size = elementData.length;

    // c.toArray might (incorrectly) not return Object[] (see 6260652)

    if (elementData.getClass() != Object[].class)

    elementData = Arrays.copyOf(elementData, size, Object[].class);

    }

    ArrayList 提供了三种方式的构造器:

    public ArrayList()可以构造一个默认初始容量为10的空列表;

    public ArrayList(int initialCapacity)构造一个指定初始容量的空列表;

    public ArrayList(Collection extends E> c)构造一个包含指定 collection 的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。

    存储

    ArrayList 中提供了多种添加元素的方法,下面将一一进行讲解:

    1.set(int index, E element):该方法首先调用rangeCheck(index)来校验 index 变量是否超出数组范围,超出则抛出异常。而后,取出原 index 位置的值,并且将新的 element 放入 Index 位置,返回 oldValue。

    /**

    * Replaces the element at the specified position in this list with

    * the specified element.

    *

    * @param index index of the element to replace

    * @param element element to be stored at the specified position

    * @return the element previously at the specified position

    * @throws IndexOutOfBoundsException {@inheritDoc}

    */

    public E set(int index, E element) {

    rangeCheck(index);

    E oldValue = elementData(index);

    elementData[index] = element;

    return oldValue;

    }

    /**

    * Checks if the given index is in range. If not, throws an appropriate

    * runtime exception. This method does *not* check if the index is

    * negative: It is always used immediately prior to an array access,

    * which throws an ArrayIndexOutOfBoundsException if index is negative.

    */

    private void rangeCheck(int index) {

    if (index >= size)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    2.add(E e):该方法是将指定的元素添加到列表的尾部。当容量不足时,会调用 grow 方法增长容量。

    /**

    * Appends the specified element to the end of this list.

    *

    * @param e element to be appended to this list

    * @return true (as specified by {@link Collection#add})

    */

    public boolean add(E e) {

    ensureCapacityInternal(size + 1); // Increments modCount!!

    elementData[size++] = e;

    return true;

    }

    private void ensureCapacityInternal(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    grow(minCapacity);

    }

    private void grow(int minCapacity) {

    // overflow-conscious code

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    elementData = Arrays.copyOf(elementData, newCapacity);

    }

    3.add(int index, E element):在 index 位置插入 element。

    /**

    * Inserts the specified element at the specified position in this

    * list. Shifts the element currently at that position (if any) and

    * any subsequent elements to the right (adds one to their indices).

    *

    * @param index index at which the specified element is to be inserted

    * @param element element to be inserted

    * @throws IndexOutOfBoundsException {@inheritDoc}

    */

    public void add(int index, E element) {

    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1); // Increments modCount!!

    System.arraycopy(elementData, index, elementData, index + 1,

    size - index);

    elementData[index] = element;

    size++;

    }

    4.addAll(Collection extends E> c) 和 addAll(int index, Collection extends E> c):将特定 Collection 中的元素添加到 Arraylist 末尾。

    /**

    * Appends all of the elements in the specified collection to the end of

    * this list, in the order that they are returned by the

    * specified collection's Iterator. The behavior of this operation is

    * undefined if the specified collection is modified while the operation

    * is in progress. (This implies that the behavior of this call is

    * undefined if the specified collection is this list, and this

    * list is nonempty.)

    *

    * @param c collection containing elements to be added to this list

    * @return true if this list changed as a result of the call

    * @throws NullPointerException if the specified collection is null

    */

    public boolean addAll(Collection extends E> c) {

    Object[] a = c.toArray();

    int numNew = a.length;

    ensureCapacityInternal(size + numNew); // Increments modCount

    System.arraycopy(a, 0, elementData, size, numNew);

    size += numNew;

    return numNew != 0;

    }

    /**

    * Inserts all of the elements in the specified collection into this

    * list, starting at the specified position. Shifts the element

    * currently at that position (if any) and any subsequent elements to

    * the right (increases their indices). The new elements will appear

    * in the list in the order that they are returned by the

    * specified collection's iterator.

    *

    * @param index index at which to insert the first element from the

    * specified collection

    * @param c collection containing elements to be added to this list

    * @return true if this list changed as a result of the call

    * @throws IndexOutOfBoundsException {@inheritDoc}

    * @throws NullPointerException if the specified collection is null

    */

    public boolean addAll(int index, Collection extends E> c) {

    rangeCheckForAdd(index);

    Object[] a = c.toArray();

    int numNew = a.length;

    ensureCapacityInternal(size + numNew); // Increments modCount

    int numMoved = size - index;

    if (numMoved > 0)

    System.arraycopy(elementData, index, elementData, index + numNew,

    numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);

    size += numNew;

    return numNew != 0;

    }

    在 ArrayList 的存储方法,其核心本质是在数组的某个位置将元素添加进入。但其中又会涉及到关于数组容量不够而增长等因素。

    读取

    这个方法就比较简单了,ArrayList 能够支持随机访问的原因也是很显然的,因为它内部的数据结构是数组,而数组本身就是支持随机访问。该方法首先会判断输入的index值是否越界,然后将数组的 index 位置的元素返回即可。

    /**

    * Returns the element at the specified position in this list.

    *

    * @param index index of the element to return

    * @return the element at the specified position in this list

    * @throws IndexOutOfBoundsException {@inheritDoc}

    */

    public E get(int index) {

    rangeCheck(index);

    return (E) elementData[index];

    }

    private void rangeCheck(int index) {

    if (index >= size)

    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    }

    删除

    ArrayList 提供了根据下标或者指定对象两种方式的删除功能。需要注意的是该方法的返回值并不相同,如下:

    /**

    * Removes the element at the specified position in this list.

    * Shifts any subsequent elements to the left (subtracts one from their

    * indices).

    *

    * @param index the index of the element to be removed

    * @return the element that was removed from the list

    * @throws IndexOutOfBoundsException {@inheritDoc}

    */

    public E remove(int index) {

    rangeCheck(index);

    modCount++;

    E oldValue = elementData(index);

    int numMoved = size - index - 1;

    if (numMoved > 0)

    System.arraycopy(elementData, index+1, elementData, index,

    numMoved);

    elementData[--size] = null; // Let gc do its work

    return oldValue;

    }

    /**

    * Removes the first occurrence of the specified element from this list,

    * if it is present. If the list does not contain the element, it is

    * unchanged. More formally, removes the element with the lowest index

    * i such that

    * (o==null ? get(i)==null : o.equals(get(i)))

    * (if such an element exists). Returns true if this list

    * contained the specified element (or equivalently, if this list

    * changed as a result of the call).

    *

    * @param o element to be removed from this list, if present

    * @return true if this list contained the specified element

    */

    public boolean remove(Object o) {

    if (o == null) {

    for (int index = 0; index < size; index++)

    if (elementData[index] == null) {

    fastRemove(index);

    return true;

    }

    } else {

    for (int index = 0; index < size; index++)

    if (o.equals(elementData[index])) {

    fastRemove(index);

    return true;

    }

    }

    return false;

    }

    注意:从数组中移除元素的操作,也会导致被移除的元素以后的所有元素的向左移动一个位置。

    调整数组容量

    从上面介绍的向 ArrayList 中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容有两个方法,其中开发者可以通过一个 public 的方法ensureCapacity(int minCapacity)来增加 ArrayList 的容量,而在存储元素等操作过程中,如果遇到容量不足,会调用priavte方法private void ensureCapacityInternal(int minCapacity)实现。

    public void ensureCapacity(int minCapacity) {

    if (minCapacity > 0)

    ensureCapacityInternal(minCapacity);

    }

    private void ensureCapacityInternal(int minCapacity) {

    modCount++;

    // overflow-conscious code

    if (minCapacity - elementData.length > 0)

    grow(minCapacity);

    }

    /**

    * Increases the capacity to ensure that it can hold at least the

    * number of elements specified by the minimum capacity argument.

    *

    * @param minCapacity the desired minimum capacity

    */

    private void grow(int minCapacity) {

    // overflow-conscious code

    int oldCapacity = elementData.length;

    int newCapacity = oldCapacity + (oldCapacity >> 1);

    if (newCapacity - minCapacity < 0)

    newCapacity = minCapacity;

    if (newCapacity - MAX_ARRAY_SIZE > 0)

    newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:

    elementData = Arrays.copyOf(elementData, newCapacity);

    }

    从上述代码中可以看出,数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的 1.5 倍(从int newCapacity = oldCapacity + (oldCapacity >> 1)这行代码得出)。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造 ArrayList 实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity 方法来手动增加 ArrayList 实例的容量。

    Fail-Fast 机制

    ArrayList 也采用了快速失败的机制,通过记录 modCount 参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。 关于 Fail-Fast 的更详细的介绍,我在之前将 HashMap 中已经提到。

    展开全文
  • map底层实现原理

    2021-06-10 03:23:34
    面试中如何回答HashMap的工作原理用过哪些Map类,都有什么区别,HashMap是线程安全的吗,并发下使用的Map是什么,他们 内部原理分别是...实现原理,如何保证HashMap的线程安全有2种办法让HashMap线程安全,分别如下:...

    面试中如何回答HashMap的工作原理

    用过哪些Map类,都有什么区别,HashMap是线程安全的吗,并发下使用的Map是什么,他们 内部原理分别是什么,比如存储方式,hashcode,扩容,默认容量等。 JAVA8的ConcurrentHashMap为什么放弃了分段锁,有什么问题吗,如果你来设计,你如何 设计。

    实现原理,如何保证HashMap的线程安全

    f89238f95bcd21d8a57cd2c2b6c1f7bd.png

    有2种办法让HashMap线程安全,分别如下: 方法一:通过Collections.synchronizedMap()返回一个新的Map,这个新的map就是线程安全的。 这个要CSS布局HTML小编今天和大家分享大家习惯基于接口编程,因为返回的并不是HashMap,而是一个Map的实现。 方法二:重新改写了HashMap。

    通过实现原理及源代码分析HashMap该怎么用

    HashMap ,都知道哪里要用 HashMap ,知道 Hashtable 和 HashMap 之间的区别 ,那么 为何这道面试题如此特殊呢?是因为这道题考察的深度很深。 这题经常出现在高级或中高级 面试中。投资银行更喜欢问这个问题,甚至会要CSS布局HTML小编今天和大家分享你实现 HashMap 来考察

    c++的map是什么原理?用纯C如何实现?

    map是 映射, 有一个对应表。 当A事件发生时代调用什么函数处理 当B事件发生时代调用什么函数处理 当..事件发生时代调用什么函数处理 MFC 的例子: BEGIN_MESSAGE_MAP(CXxxView, CScrollView) //{{AFX_MSG_MAP(CXxxView) ON_COMMAND(ID_FORMAT_FO

    hashtable和hashmap的区别及实现原理

    Hashtable是线程安全的,HashMap是非线程安全的。Hashtable是基于老的Diactionary类实现的,HashMap是Java 1.2引进Map接口后的重新实现。Hashtable的方法,进行了锁同步,可以支行于多线程环境。HashMap需要编程人员自在己为其提供同步。

    请问java中HashMap是怎么实现的,还有treeMap的实参考资料的网页上有比较的代码,你可以仔细看下~~~ java中HashMap,LinkedHashMap,TreeMap,HashTable的区别 java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap Map主要用于存

    同步的数据结构,例如concurrenthashmap的源码理解nized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的

    本文结合jdk1.7和jdk1.8的区别,深入探讨hashmap的本文结合jdk1.7和jdk1.8的区别,深入探讨hashmap的结构实现和功能原理 ...本文结合jdk1.7和jdk1.8的区别,深入探讨hashmap的结构实现和功能原理 搜索资料

    mapreduce实现原理是怎样的

    map 根据输入的映射函数,将一个集合映射为另一个集合,比如: 输入集合为 {1,2,3,4,5},输入的函数为 f(x) = x^2,那么输出的集合就是 {1,4,9,16,25}。 reduce 就是根据输入的归约函数,将集合(一般指map输出的集合)归约。

    hashmap数据结构及实现原理,其链表是用来解决什么...Hashmap实际上是一个数组和链表的结合体 (在数据结构中,一般称之为“链表散列“) 希望能帮到你。

    展开全文
  • java集合底层实现原理

    2021-03-05 16:29:26
    3.2.1 底层实现 3.2.2扩容 3.2.3 线程安全性 3.2.4 vector与ArrayList比较 3.3 LinkedList 3.3.1 底层实现 3.3.2 容量问题 3.3.3 使用问题 3.3.4 线程安全性 4. Set接口 4.1 HashSet 4.
  • 一、HashMap的工作原理 HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当...
  • 概述文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类...存在以下特点:不能保证元素的顺序,元素是无序的HashSet不是同步的,需要外部保持线程之间的同步问题集合元素值允许为null数据结构ja...
  • 五、实现协程的核心:跳转(协程切换) 无论协程怎么被创建,底层都要分配执行栈和控制信息。 让出执行权时候,都要保存执行现场,以便后续恢复。 每个协程都有自己的执行栈,可以保存自己的执行现场。 可以由用户程序...
  • CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的。 CAS是如何保证线程安全的? 线程在读取数据时不进行加锁,在准备写回数据时,先
  • HashMap底层实现原理

    2021-01-08 16:16:23
    HashMap底层实现原理 对于HashSet而言,它是基于HashMap实现的,底层采用的HashMap来存储元素 概述 HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用NULL建和NULL值,因为key允许重复,因此只能有一个...
  • 1. 概述上次讨论了HashMap的结构,原理实现,本文来对Map家族的另外一个常用集合HashTable进行介绍。HashTable和HashMap两种集合非常相似,经常被各种面试官问到两者的区别。对于两者的区别,主要有以下几点:...
  • 重量级锁 5、锁消除 6、锁粗化 五、锁升级场景: 转自: java锁升级过程 synchronized底层实现原理及锁优化 一、概述 1、synchronized作用 原子性:synchronized保证语句块内操作是原子的 可见性:synchronized保证...
  • (一)、实现原理 可以看到,第三种形式是JAVA提供的语法糖,这里我们剖析一下,这种增强for循环底层是如何实现的。 我们对以下代码进行反编译: for (Integer i : list) { System.out.println(i); } 反编译后: ...
  • 实现原理是new出一个paintEvent,调用 QApplication::postEvent(),将其放入Qt的消息队列中,等待依次被处理。 3、Send事件 由Qt或应用程序产生,但它们被直接发送到目标对象。 调用QApplication::sendEvent()...
  • JAVA 同步实现原理

    千次阅读 2021-03-08 09:21:19
    原标题:JAVA 同步实现原理Synchronized的基本使用Synchronized是Java中解决并发问题的一种最常用的方法,也是最简单的一种方法。Synchronized的作用主要有三个:确保线程互斥的访问同步代码保证共享变量的修改能够...
  • TreeSet实现了SortedSet接口,它是一个有序的集合类,TreeSet的底层是通过TreeMap实现的。TreeSet并不是根据插入的顺序来排序,而是根据实际的值的大小来排序。TreeSet也支持两种排序方式:自然排...
  • JVM中的同步是基于进入与退出监视器对象(管程对象)(Monitor)来实现的,每个对象实例都会有一个Monitor对象,Monitor对象会和Java对象一同创建并销毁。Monitor对象是由C++来实现的。 每个对象都存在着一个 monitor ...
  • python底层原理

    千次阅读 2021-02-10 10:51:18
    Python多线程原理实现 Date: 2019-06-04 Author: Sun Python多线程原理与实战 目的: (1)了解python线程执行原理 (2)掌握多线程编程与线程同步 (3)了解线程池的使用 1 线程基本 ... Docker底层原理介绍 1.docker...
  • java并发机制与底层实现原理volatilevolatile是轻量级的synchronize,它在多处理器开发中保证了共享变量的“可见性”,因为它不会引起线程上下文的切换和调度,所以比synchronize的使用和执行成本更底。为了提高处理...
  • MySQL事务ACID的底层实现原理
  • ②可见性:synchronized 保证可见性(通过“在执行unlock之前,必须先把此变量同步回主内存”实现)。 ③有序性:synchronized 保证有序性(通过“一个变量在同一时刻只允许一条线程对其进行lock操作”)。 ...
  • volatile的实现原理及应用 volatile 可看做是轻量级的synchronized,它在多处理器开发中保证了发发发发发发付共享变量的***可见性***,所谓 synchronized的实现原理及应用
  • 2.1.2 volatile定义和实现原理 a 定义:为了确保共享变量能被准确和一致性的更新,线程应该确保通过排他锁单独的获得这个变量 b CPU术语的定义: 1)内存屏障(memory barriers) 处理指令 用于实现内存操作的顺序...
  • 同步的基本思想为了保证共享数据在同一时刻只被一个线程使用,我们有一种很简单的实现思想,就是在共享数据里保存一个锁,当没有线程访问时,锁是空的。当有第一个线程访问时,就在锁里保存这个线程的标识并允许这个...
  • synchronized底层实现 在Java里面,最基本的互斥同步手段是synchronized (1)原理 synchronized关键字经过反编译之后,会在同步块的前后分别形成 monitorenter和monitorexit这两个字节码指令。这两个字节码指令都...
  • 线程池的底层原理 b. 四种引用类型 c. JAVA GC d. Sychornized关键字 e. 静态同步函数 f. 可不可以调用Abstrut 父类的super方法 g. HTTP协议中POST,GET 的区别 h. TCP/IP协议栈 i. TCP和UDP的区别
  • 下面两个方式,本质上都是通过监视器锁(monitor)来控制同步代码块是通过 monitorenter 和monitorexit 指令获取线程的执行权同步方法通过加ACC_SYNCHRONIZED 标识实现线程的执行权的控制"同步代码块"的原理我们先通过...
  • 通常 Synchronized 实现同步锁的方式有两种,一种是修饰方法,一种是修饰方法块。 通过反编译看下具体字节码的实现,运行以下反编译命令,就可以输出我们想要的字节码: javap -v SyncTest.class // 再通过 javap ...
  • synchronized实现原理 面试百度的时候,面试官问我synchronzied,尴尬没有看过,不会,哈哈哈,便恶补synchronzied,顺便还有线程池,在我的另外一篇博客里面。 基本上写的博客比较少,很多东西都写的不是很规范,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 139,240
精华内容 55,696
关键字:

同步的底层实现原理