摘要：也就是说，红黑树是一种相对平衡的查找二叉树，这使他不仅便于查找，也便于插入和删除，这对于既需要插入也需要查找的是非常有利的下一节数据哈希值的计算和在中的存储位置
在jdk8中，HashMap是用了数组和链表以及红黑树这三种数据结构
首先，在hashmap类中，都有一个table数组，我们在存储数据时，对这个数据的hash值进行一系列的计算 计算出它在Table中的位置(下标)，并将它存放进去
然而，我们在hashmap是什么 中提到，不同的对象的Hash值可能相同，那么相同的Hash值会导致不同的数据在数组中有相同的存储位置，我们虽然创造了一系列的解决办法，但并不能完全的避免这种冲突，那么，当产生冲突时，hashmap是怎样解决的呢？
当产生冲突时，如data1和data2 ,我们把data2放在data1后的列表中，这样就不会因为哈希值的冲突而对数据产生影响。
1.时间复杂度
我们知道，当某条链表的长度大于8时，就会将其转换为红黑树。遍历一条链表的时间复杂度O(n),当一条链表过长时，遍历这条链表可能会花很长时间，而遍历一颗红黑树的时间复杂度为O（logn）,从而减少了插入或查找的时间
2.红黑树
简单总结下红黑树是什么：一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
也就是说，红黑树是一种相对平衡的查找二叉树，这使他不仅便于查找，也便于插入和删除，这对于既需要插入也需要查找的HashMap是非常有利的
下一节：数据哈希值的计算和在table中的存储位置
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/69986.html
摘要：当一个值中要存储到的时候会根据的值来计算出他的，通过哈希来确认到数组的位置，如果发生哈希碰撞就以链表的形式存储在源码分析中解释过，但是这样如果链表过长来的话，会把这个链表转换成红黑树来存储。 正文开始 注:JDK版本为1.8 HashMap1.8和1.8之前的源码差别很大 目录 简介 数据结构 类结构 属性 构造方法 增加 删除 修改 总结 1.HashMap简介 H...
摘要：源码解析的数据存储结构中的都是存在数组中的数据节点的数据结构是一个单向的链表，，实现了的接口，即实现了，，等这些函数，这些都是基本的读取修改值的函数。的作用是判断是否包含的作用是判断是否包含值为的元素 HashMap源码解析 hashmap的数结构 （1）在Java中，数据结构分为两种，一种是数组，另一个是模型指针即引用，所有的数据结构都可以用这两种基本结构所构造，HashMap就是一...
摘要：则使用了拉链式的散列算法，并在中引入了红黑树优化过长的链表。如果大家对红黑树感兴趣，可以阅读我的另一篇文章红黑树详细分析。构造方法构造方法分析的构造方法不多，只有四个。 1.概述 本篇文章我们来聊聊大家日常开发中常用的一个集合类 - HashMap。HashMap 最早出现在 JDK 1.2中，底层基于散列算法实现。HashMap 允许 null 键和 null 值，在计算哈键的哈希值...
摘要：加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行操作即重建内部数据结构，从而哈希表将具有大约两倍的桶数。 showImg(https://upload-images.jianshu.io/upload_images/4565148-98b22ba5ae7d9723.jpg?imageMogr2/auto-...
摘要：根据的重新计算值。如果这两个的通过比较返回，新添加的将覆盖集合中原有的，但不会覆盖。如果这两个的通过比较返回，新添加的将与集合中原有形成链，而且新添加的位于链的头部具体说明继续看方法的说明。 关于hashCode hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的. 1.hashcode是用来...
阅读 3333·2023-04-25 15:52
阅读 355·2021-11-19 09:40
阅读 1960·2021-09-26 09:47
阅读 826·2021-09-22 15:17
阅读 3388·2021-08-13 13:25
阅读 1931·2019-08-30 15:56
阅读 3360·2019-08-30 13:56
阅读 1901·2019-08-30 11:27
