首页 > 编程知识 正文

hashmap红黑树扩容(hashmap链表转红黑树)

时间:2023-05-03 18:43:52 阅读:94531 作者:4003

首先,HashMap是Map的实现类,Map存储格式是键-值对(key,value )。 可以看作是一个个的进入。 Entry的保管场所由key决定。

Map中的key无序且不可重复,所有的key都可以看作一个set集合。 如果Map中出现了key,但它是自定义类的对象,则必须重写hashCode和equals方法。 如果不重写,则使用Object类中的hashCode和equals方法,因此要进行比较的不是内存地址值。

Map中的value是无序的、可重复的,所有的value都可以看作是集合,如果Map中的value是自定义类的对象,则必须重写equals方法。

要说改写hashCode和equals分别做什么好,用hashMap的基本原理来说:

在HashMap中存储元素(k1,v1 )时,首先根据k1的hashCode方法确定数组中存储的位置。

如果该位置没有其他元素,则将[k1,v1]直接放入节点型数组中。 此数组的初始化容量为16,缺省加载系数为0.75。 也就是说,将元素添加到12后,下面的层次将扩展到原来的两倍。 如果该位置已经有其他元素(k2,v2 ),则调用k1的equals方法比较是否与k2相同,如果结果为true,则表示两个元素相同,将v2替换为v1,如果返回值为false,则为2个元素不同,则为rie

但是,由于链表的数据过多会降低查询效率,因此在JDK 1.8版之后进行了升级。 如果链表的元素达到8个,元素数超过64个,则hashmap在将链表替换为红黑树进行树化时,将链表替换为红黑树以提高检索效率。 因为在检索、插入、删除操作很多的情况下,使用红黑的树会更有效率。

因为,红黑树是一种特殊的二叉树,二叉树所有节点的左侧的树都比该节点小,所有节点的右侧的树都比该节点大,通过大小比较关系可以进行高速检索。

在红黑树中插入或删除节点后,红黑树会发生变化,可能不满足红黑树的五个性质。 也就是说,不是红黑的树,而是普通的树,通过左旋和右旋,可以使这棵树再次成为红黑的树。 红木的五个性质(根节点为黑色,各节点为黑色或红色,各叶节点为黑色。 节点为红色时,其子节点必须为黑色,从节点到其后代的外部节点的所有路径中包含相同数量的黑点) ) )。

而这种二叉树结构常见的使用场景是Mysql两种引擎的索引,Myisam使用b树,InnoDB使用b树。

首先,b树中的每个节点都是Key.value的二元组,key从左到右按升序排序,value中存储数据。 此模式具有单独的索引文件,有三个Myisam存储文件, frm是表的结构文件, MYD是数据文件, MYI是索引文件,因此具有良好的数据读取性能但是,由于Myisam只支持表级锁定,不支持行级锁定,也不支持事务、外键等,因此通常用于大数据存储。

在实际使用HashMap时,还可能会出现线程安全问题。

HashMap的线程不安全。 在多线程环境中,使用HashMap进行put操作时会发生死区,CPU使用率接近100%。 此外,还会抛出并发修改异常。 原因是同时获取线程资源和修改数据。 一个线程正在写入,一个线程来争夺,线程的写入过程被另一个线程中断,从而导致数据不一致。

虽然HashTable是线程安全的,但是实现成本太大了,简单粗暴。 所有与get/put相关的操作都是已同步的。 这相当于给整个散列表上一个很大的锁。 对于多线程访问,如果一个线程访问或操作该对象,则其他线程只能被阻止,这与序列化所有操作一样,在竞争激烈的并发场景中性能会非常差。

ConcurrentHashMap利用大量的volatile、CAS等技术来解决并发环境中的hashmap焦虑,从而减轻锁定竞争对性能的影响

响。

在 JDK1.7 版本中 ConcurrentHashMap 避免了对全局加锁,改成了局部加锁(分段锁),分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。

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

所以在 JDK1.8 版本中 CurrentHashMap 内部中的 value 使用 volatile 修饰,保证并发的可见性以及禁止指令重排,只不过 volatile 不保证原子性,使用为了确保原子性,采用 CAS(比较交换)这种乐观锁来解决。

CAS 操作包含三个操作数 —— 内存位置(V)、预期原值(A)和新值(B)。

如果内存地址里面的值和 A 的值是一样的,那么就将内存里面的值更新成 B。CAS 是通过无限循环来获取数据的,如果在第一轮循环中,a 线程获取地址里面的值被 b 线程修改了,那么 a 线程需要自旋,到下次循环才有可能机会执行。

volatile 有三个特性:可见性,不保证原子性,禁止指令重排。

可见性:线程 1 从主内存中拿数据 1 到自己的线程工作空间进行操作(假设是加 1)这个时候数据 1 已经改为数据 2 了,将数据 2 写回主内存时通知其他线程(线程 2,线程 3),主内存中的数据 1 已改为数据 2 了,让其他线程重新拿新的数据(数据 2)。

不保证原子性:线程 1 从主内存中拿了一个值为 1 的数据到自己的工作空间里面进行加 1的操作,值变为 2,写回主内存,然后还没有来得及通知其他线程,线程 1 就被线程 2 抢占了,CPU 分配,线程 1 被挂起,线程 2 还是拿着原来主内存中的数据值为 1 进行加 1,值变成 2,写回主内存,将主内存值为 2 的替换成 2,这时线程 1 的通知到了,线程 2 重新去主内存数值为 2 的数据。

禁止指令重排:首先指令重排是程序执行的时候不总是从上往下执行的,就像高考答题,可以先做容易的题目再做难的,这时做题的顺序就不是从上往下了。禁止指令重排就杜绝了这种情况。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。