小节

Updated on with 0 views and 0 comments

HashMap

这里HashMap更倾向于1.7,因为红黑树结构我暂时不熟悉,无法梳理~

简单来说,HashMap 由数组 + 链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前 entry 的 next 指向 null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为 O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过 key 对象的 equals 方法逐一比对查找。所以,性能考虑,HashMap 中的链表出现越少,性能才会越好。

结构图如下:
image.png

//实际存储的 key-value 键值对的个数
transient int size;
//阈值,当 table == {}时,该值为初始容量(初始容量默认为 16);当 table 被填充了,也就是为 table 分配内存空间后,threshold 一般为 capacity*loadFactory。HashMap 在进行扩容时需要参考 threshold,后面会详细谈到
int threshold;
//负载因子,代表了 table 的填充度有多少,默认是 0.75
final float loadFactor;
//用于快速失败,由于 HashMap 非线程安全,在对 HashMap 进行迭代时,如果期间其他线程的参与导致 HashMap 的结构发生变化了(比如 put,remove 等操作),需要抛出异常 ConcurrentModificationException
transient int modCount;

先对 HashMap 的简单总结

HashMap 是基于拉链法实现的一个散列表,内部由数组和链表。

  1. 数组的初始容量为 16,而容量是以 2 的次方扩充的,一是为了提高性能使用足够大的数组,二是为了能使用位运算代替取模预算(据说提升了 5~8 倍)。
  2. 数组是否需要扩充是通过负载因子判断的,如果当前元素个数为 数组容量* 0.75 时,就会扩充数组。这个 0.75 就是默认的负载因子,可由构造传入。我们也可以设置大于 1 的负载因子,这样数组就不会扩充,牺牲性能,节省内存。
  3. 为了解决碰撞,数组中的元素是单向链表类型。当链表长度到达一个阈值时(7 或 8),会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时(6),又会将红黑树转换回单向链表提高性能,这里是一个平衡点。

HashMap.put(k,v)

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

// onlyIfAbsent:当存入键值对时,如果该key已存在,是否覆盖它的value。false为覆盖,true为不覆盖 参考putIfAbsent()方法。
// evict:用于子类LinkedHashMap。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    HashMap.Node<K,V>[] tab; // tab:内部数组
    HashMap.Node<K,V> p;   // p:hash对应的索引位中的首节点
    int n, i;  // n:内部数组的长度    i:hash对应的索引位
    
    // 首次put时,内部数组为空,扩充数组。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算数组索引,获取该索引位置的首节点,如果为null,添加一个新的节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {   
        HashMap.Node<K,V> e; K k;
        // 如果首节点的key和要存入的key相同,那么直接覆盖value的值。
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果首节点是红黑树的,将键值对插添加到红黑树
        else if (p instanceof HashMap.TreeNode)
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 此时首节点为链表,如果链表中存在该键值对,直接覆盖value。
        // 如果不存在,则在末端插入键值对。然后判断链表是否大于等于7,尝试转换成红黑树。
        // 注意此处使用“尝试”,因为在treeifyBin方法中还会判断当前数组容量是否到达64,
        // 否则会放弃次此转换,优先扩充数组容量。
        else {
            // 走到这里,hash碰撞了。检查链表中是否包含key,或将键值对添加到链表末尾
            for (int binCount = 0; ; ++binCount) {
                // p.next == null,到达链表末尾,添加新节点,如果长度足够,转换成树结构。
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    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;
            }
        }

        // 覆盖value的方法。
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; // fail-fast机制
    
    // 如果元素个数大于阈值,扩充数组。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

细心看注释部分,总结来说就是以下几个步骤:

1.检查数组是否为空,执行 resize()扩充;

2.通过 hash 值计算数组索引,获取该索引位的首节点。

3.如果首节点为 null** (没发生碰撞) ,直接添加节点到该索引位 (bucket)

4.如果首节点不为 null (发生碰撞) ,那么有 3 种情况 ① key 和首节点的 key 相同,覆盖 old value (保证key的唯一性) **;否则执行 ②或 ③ ② 如果首节点是红黑树节点(TreeNode),将键值对添加到红黑树。 ③ 如果首节点是链表,将键值对添加到链表。添加之后会判断链表长度是否到达 TREEIFY_THRESHOLD - 1 这个阈值,“尝试”将链表转换成红黑树。

5.最后判断当前元素个数是否大于 threshold,扩充数组。

HashMap 在 jdk1.8 之后引入了红黑树的概念,表示若桶中链表元素超过 8 时,会自动转化成红黑树;若桶中元素小于等于 6 时,树结构还原成链表形式。

扩充数组不单单只是让数组长度翻倍,将原数组中的元素直接存入新数组中这么简单。

因为元素的索引是通过 hash&(n - 1)得到的,那么数组的长度由 n 变为 2n,重新计算的索引就可能和原来的不一样了。

在 jdk1.7 中,是通过遍历每一个元素,每一个节点,重新计算他们的索引值,存入新的数组中,称为 rehash 操作。

HashMap.get(k)

 public V get(Object key) {
         //如果key为null,则直接去table[0]处去检索即可。
            if (key == null)
                return getForNullKey();
            Entry<K,V> entry = getEntry(key);
            return null == entry ? null : entry.getValue();
     }

get 方法通过 key 值返回对应 value,如果 key 为 null,直接去 table[0]处检索。我们再看一下 getEntry 这个方法
可以看出,get 方法的实现相对简单,key(hashcode)-->hash-->indexFor--> 最终索引位置,找到对应位置 table[i],再查看是否有链表,遍历链表,通过 key 的 equals 方法比对查找对应的记录。要注意的是,有人觉得上面在定位到数组位置之后然后遍历链表的时候,e.hash == hash 这个判断没必要,仅通过 equals 判断就可以。其实不然,试想一下,如果传入的 key 对象重写了 equals 方法却没有重写 hashCode,而恰巧此对象定位到这个数组位置,如果仅仅用 equals 判断可能是相等的,但其 hashCode 和当前对象不一致,这种情况,根据 Object 的 hashCode 的约定,不能返回当前对象,而应该返回 null,后面的例子会做出进一步解释。

##问答

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

image.png

因为 String、Integer 等包装类是 final 类型的,具有不可变性,而且已经重写了 equals() 和 hashCode() 方法。不可变性保证了计算 hashCode() 后键值的唯一性和缓存特性,不会出现放入和获取时哈希码不同的情况且读取哈希值的高效性,此外官方实现的 equals() 和 hashCode() 都是严格遵守相关规范的,不会出现错误。
例子如下:

class Item {

        public String name;

        public int age;


        @Override

        public int hashCode() {

            return this.name.hashCode() + this.age;

        }


        public Item(String name, int age) {

            this.name = name;

            this.age = age;

        }

    }


    public class Demo {

        public static void main(String[] args) {  

            Item item1 = new Item("android", 4);

            Item item2 = new Item("java", 3);

            Map<Item, Item> map = new HashMap<Item, Item>();

            map.put(item1, item1);

            map.put(item2, item2);

            item2.name = "unix c";

            Item value = map.get(item2);

            System.out.println("value="+value);

        }

    }

HashMap 中的 key 若 Object 类型, 则需实现哪些方法?

image.png
需实现 hashCode()和 equals()方法,hashCode()方法就算需要存储数据的储存位置,实现不恰当会导致严重的 Hash 碰撞,equals()方法主要就是
包装键 key 在 hash 表中的唯一性。

哈希表如何解决 Hash 冲突?

image.png

HashMap 的加载因子是多少,如果这个加载因子越大或加载因子越小有什么优缺点?
默认的加载因子是 0.75,HashMap 的初始化容量为 16,也就是当 HashMap 中的元素 > 容量 x ${加载因子}时就会触发扩容,扩容后的容量为原来容量的 2 倍
如果加载因子大于 0.75,优点:容量的填满的元素越多,链表变长,空间利用率高,缺点:hashcode 冲突的概率加大,查找的效率变低。
如果加载因子越小,优点:键值的 hashcode 冲突概率就低,链表短 查询的速度就越快。缺点:填满容量的的元素就少,空间利用率就低。
默认因子为 0.75 是一个容量利用率和避免 hashcode 碰撞的折中值。

HashMap 和 Hashtable 的区别

HashMap 和 Hashtable 都实现了 Map 接口,主要区别有:线程安全性,同步(synchronization),以及速度。

  1. HashMap 几乎等价于 Hashtable,除了 HashMap 是非线程安全的,并且可以接受 null(HashMap 可以接受为 null 的键值(key)
    和值(value),而 Hashtable 不行)。
  2. HashMap 是非线程安全的,而 Hashtable 是线程安全的,这意味着 Hashtable 是线程安全的,多个线程可以共享一个 Hashtable;
    而如果没有正确的同步的话,多个线程是不能共享 HashMap 的。Java5 提供了 ConcurrentHashMap,它是 Hashatable 的替代,比 Hashtable
    的扩展性更好。

Hashtable 线程安全的实现方式是利用 synchronized

HashMap 多线程下的问题

当两个线程同时进行 put 操作时,基本同时会达到 HashMap 的存储阈值,所以也就会并发进行 resize,那么这里可能会发生数据错乱,各自有一个新的 table[] 数组,但是老的数组是同一个

1.多线程 put,get 时出现死循环,导致 CPU 利用率过高
2:多线程 put,可能导致元素丢失
3:put 非 null 元素后 get 出来的却是 null

1.7ConcurrentHashMap 的实现原理

在 JDK1.7 中 ConcurrentHashMap 采用了数组 +Segment+ 分段锁的方式实现。

1.Segment(分段锁)

ConcurrentHashMap 中的分段锁称为 Segment,它即类似于 HashMap 的结构,即内部拥有一个 Entry 数组,数组中的每个元素又是一个链表,同时又是一个 ReentrantLock(Segment 继承了 ReentrantLock)。

2.内部结构

ConcurrentHashMap 使用分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。如下图是 ConcurrentHashMap 的内部结构图:

image.png

从上面的结构我们可以了解到,ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作。

第一次 Hash 定位到 Segment,第二次 Hash 定位到元素所在的链表的头部。

3.该结构的优劣势

坏处

这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长

好处

写操作的时候可以只对元素所在的 Segment 进行加锁即可,不会影响到其他的 Segment,这样,在最理想的情况下,ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作(刚好这些写操作都非常平均地分布在所有的 Segment 上)。

所以,通过这一种结构,ConcurrentHashMap 的并发能力可以大大的提高。

永久代会不会导致内存溢出?
会,
回答这个问题,我们先要知道方法区里存放哪些数据,

  • 已经被虚拟机加载的类信息
  • 常量
  • 静态变量
  • 即时编译器编译后的代码
    永久代溢出可以分为两种情况
    第一种是常量池溢出,第二种是方法区溢出。
    方法区存放 Class 的相关信息,下面借助 CGLib 直接操作字节码,生成大量的动态类。
    绝大部分 Java 程序员应该都见过 "java.lang.OutOfMemoryError: PermGen space "这个异常。这里的 “PermGen space”其实指的就是方法区内存异常。

(11)浅复制和深复制?怎样实现深复制?
浅拷贝是按位拷贝对象,它会创建一个新对象,这个对象有着原始对象属性值的一份精确拷贝。* 如果属性是基本类型,拷贝的就是基本类型的值;如果属性是内存地址(引用类型),拷贝的就是内存地址 ,因此如果其中一个对象改变了这个地址,就会影响到另一个对象。

深拷贝会拷贝所有的属性,并拷贝属性指向的动态分配的内存。当对象和它所引用的对象一起拷贝时即发生深拷贝。深拷贝相比于浅拷贝速度较慢并且花销较大。
深拷贝出的对象是个独立的对象和被拷贝对象没啥关系了。

(13)CAS是一种什么样的同步机制?
(compare and swap),简称 CAS,提到 CAS 我就想到了悲观锁,乐观锁的概念,悲观锁是 MySQL 的机制是独占锁,排它锁,而 synchronized 也是一种独占锁,synchronized 会导致其他未持有锁的线程阻塞,必须等待持有锁的线程释放锁资源,所谓乐观锁就是,每次不加锁而是假设没有冲突而去完成某项操作,如果因为冲突失败就重试,直到成功为止。而乐观锁用到的机制就是 CAS。Compare And Set(或 Compare And Swap),CAS 是解决多线程并行情况下使用锁造成性能损耗的一种机制,CAS 操作包含三个操作数——位置(V)、原始值(A)、预设新值(B)。
简单描述下 MySQL 乐观锁的实现吧比如
下单操作吧包括 3 步骤:

1.查询出商品信息

select (商品信息,销量,version) from t_goods where id=#{id}

2.根据商品信息生成订单

3.修改商品 销量 为 2

update t_goods

set 销量 =2,version=version+1

where id=#{id} and version=#{version};
如果发现更新失败,那么这里可以加入重试

(36)线程的生命周期
线程的生命周期包含 5 个阶段,包括:新建、就绪、运行、阻塞、销毁。

  • 新建:就是刚使用 new 方法,new 出来的线程;
  • 就绪:就是调用的线程的 start()方法后,这时候线程处于等待 CPU 分配资源阶段,谁先抢的 CPU 资源,谁开始执行;
  • 运行:当就绪的线程被调度并获得 CPU 资源时,便进入运行状态,run 方法定义了线程的操作和功能;
  • 阻塞:在运行状态的时候,可能因为某些原因导致运行状态的线程变成了阻塞状态,比如 sleep()、wait()之后线程就处于了阻塞状态,这个时候需要其他机制将处于阻塞状态的线程唤醒,比如调用 notify 或者 notifyAll()方法。唤醒的线程不会立刻执行 run 方法,它们要再次等待 CPU 分配资源进入运行状态;
  • 销毁:如果线程正常执行完毕后或线程被提前强制性的终止或出现异常导致结束,那么线程就要被销毁,释放资源;
    Java 线程池管理类(ThreadPoolExecutor)

Java类加载机制,你理解了吗?
当我们的 Java 代码编译完成后,会生成对应的 class 文件。接着我们运行 代码的时候,我们其实是启动了 JVM 虚拟机执行 class 字节码文件的内容。而 JVM 虚拟机执行 class 字节码的过程可以分为七个阶段:加载、验证、准备、解析、初始化、使用、卸载。

其实可以一句话来解释:类的加载指的是将类的。class 文件中的二进制数据读入到内存中,将其放在运行时数据区的方法区内,然后在堆区创建一个 java.lang.Class 对象,用来封装类在方法区内的数据结构。

类加载器
Bootstrap ClassLoader :最顶层的加载类,主要加载核心类库
Extention ClassLoader :扩展的类加载器
Appclass Loader:也称为 SystemAppClass。 加载当前应用的 classpath 的所有类。
这三种类加载器的加载顺序是什么
image.png
image.png

双亲委派原则

他的工作流程是: 当一个类加载器收到类加载任务,会先交给其父类加载器去完成,因此最终加载任务都会传递到顶层的启动类加载器,只有当父类加载器无法完成加载任务时,才会尝试执行加载任务。

采用双亲委派的一个好处是比如加载 java.lang.Object,不管是哪个类加载器加载这个类,最终都是委托给顶层的启动类加载器进行加载,这样就保证了使用不同的类加载器最终得到的都是同样一个 Object 对象。双亲委派原则归纳一下就是:

优点是可以避免重复加载,父类已经加载了,子类就不需要再次加载更加安全,很好的解决了各个类加载器的基础类的统一问题,如果不使用该种方式,那么用户可以随意定义类加载器来加载核心 API,会带来相关隐患。

RocketMQ 事务方案

RocketMq 消息中间件把消息分为两个阶段预备阶段确认阶段 Prepared 阶段

预备阶段 主要发一个消息到 rocketmq,但该消息只储存在 commitlog 中但 consumeQueue 中不可见,也就是消费端(订阅端)无法看到此消息

commit/rollback 阶段(确认阶段)该阶段主要是把 预备 消息保存到 consumeQueue 中,即让消费端可以看到此消息,也就是可以消费此消息
图文说明
image.png
流程描述一下

  1. 在扣款之前,先发送预备消息
  2. 发送预备消息成功后,执行本地扣款事务
  3. 扣款成功后,再发送确认消息
  4. 消息端(加钱业务)可以看到确认消息,消费此消息,进行加钱
    上面的确认消息可以为 commit 消息,可以被订阅者消费;也可以是 Rollback 消息,即执行本地扣款事务失败后,提交 rollback 消息,即删除那个预备消息,订阅者无法消费。

我们来分析一下异常场景

**异常 1:**如果发送预备消息失败,下面的流程不会走下去;**这个是正常的

异常 2:**如果发送预备消息成功,但执行本地事务失败;这个也没有问题,**因为此预备消息不会被消费端订阅到,消费端不会执行业务。

异常 3:**如果发送预备消息成功,执行本地事务成功,但发送确认消息失败;这个就有问题了,因为用户 A 扣款成功了,但加钱业务没有订阅到确认消息,无法加钱。这里出现了数据不一致。

解决异常 3 的情况我们是利用 rocketmq 的 状态回查 解决的,也就是 RocketMq 会定时遍历 commitlog 中的预备消息,因为预备消息最终肯定会变为 commit 消息或 Rollback 消息,所以遍历预备消息去回查本地业务的执行状态,如果发现本地业务没有执行成功就 rollBack,如果执行成功就发送 commit 消息。
上面的异常 3,发送预备消息成功,本地扣款事务成功,但发送确认消息失败;因为 RocketMq 会进行回查预备消息,在回查后发现业务已经扣款成功了,就补发“发送 commit 确认消息”;这样加钱业务就可以正常接收到这个消息了。

回查判断业务是否成功

小伙伴们在回查业务中,如何判断本地事务是否执行成功

如果本地事务执行了很多张表,那是不是我们要把那些表都要进行判断是否执行成功呢?这样是不是太麻烦了,而且和业务很耦合。

有没有更好的方式呢?就是设计一张 Transaction 表,将业务表和 Transaction 绑定在同一个本地事务中,如果扣款本地事务成功时,Transaction 中应当已经记录该 TransactionId 的状态为「已完成」。当 RocketMq 回查时,只需要检查对应的 TransactionId 的状态是否是「已完成」就好,而不用关心具体的业务数据。


标题:小节
作者:liqitian3344
地址:https://liqitian.com/articles/2020/02/20/1582208221041.html