数据结构
2021-09-06 21:45:42 0 举报
AI智能生成
登录查看完整内容
数据结构
作者其他创作
大纲/内容
数组+链表
1.7
防止发生hash冲突,链表长度过长,将时间复杂度由`O(n)`降为`O(logn)`;
更新原因?
putVal() TreeifyBin()
容量>=64 且 单个位置链表长度>=8
转红黑树
split()
单个位置链表长度<=6 将红黑树转化会链表
转链表
因为经过计算,在hash函数设计合理的情况下,发生hash碰撞8次的几率为百万分之6,概率说话。。因为8够用了,至于为什么转回来是6,因为如果hash碰撞次数在8附近徘徊,会一直发生链表和红黑树的互相转化,为了预防这种情况的发生。
这两个阈值如何确定的
数组+链表/红黑树
hashmap的13 个成员变量
1.8
内部结构
默认大小是16,负载因子是0.75,
如果自己传入初始大小k,初始化大小为 大于k的 2的整数次方,例如如果传10,大小为16
(n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
tableSizeFor()
HashMap的初始容量大小
计算key的hash值
hash函数是先拿到 key 的hashcode,是一个32位的int值,然后让hashcode的高16位和低16位进行异或操作。
所以key是null的时候自动分配到了数组的第一个位置
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
右移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。
bit操作效率也很高
为什么这样计算?
hash()
扩容位置不变或索引+旧容量大小;
根据key的hash值计算数组中的位置
h & (length-1)
indexFor()
构造方法
(tab = table) == null || (n = tab.length) == 0
判断数组是否为空,为空进行初始化;
(p = tab[i = (n - 1) & hash]) == null
不为空,计算 k 的 hash 值,通过(n - 1) & hash计算应当存放在数组中的下标 index;
查看 table[index] 是否存在数据,没有数据就构造一个Node节点存放在 table[index] 中;
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
p instanceof TreeNode
putTreeVal
如果不相等,判断当前节点类型是不是树型节点,如果是树型节点,创造树型节点插入红黑树中;
遍历到链表尾没有发现相同key的结点需要插入新节点
split方法中 <=6 就转换回链表
如果不是树型节点,创建普通Node加入链表中;判断链表长度是否大于等于8并且数组长度大于等于64, 大于的话链表转换为红黑树;
if (++size > threshold) resize();
插入完成之后判断当前节点数是否大于阈值,如果大于开始扩容为原数组的二倍。
插入过程
put
Get
resize()
数组+链表或红黑树
底层实现
假设有T1,T2两个线程同时对一个HashMap进行put操作,刚好,HashMap达到了扩容的条件,这是两个线程都会去对这个HashMap进行扩容链表A-->B,假设A B扩容后,计算的index依然相同,那么他们还会存放在同一链表中
多线程产生环
头插法
尾插法不会改变原有的next指向关系,所以他不会出现环
不产生环
尾插法
新节点插入链表位置
对原数组中的元素进行重新hash定位在新数组的位置,
1. 这是由于扩容是扩大为原数组大小的2倍,用于计算数组位置的掩码仅仅只是高位多了一个1,怎么理解呢?2. 扩容前长度为16,用于计算(n-1) & hash 的二进制n-1为0000 1111,扩容为32后的二进制就高位多了1,为0001 1111。3. 因为是& 运算,1和任何数 & 都是它本身,那就分二种情况,如下图:原数据hashcode高位第4位为0和高位为1的情况;4. 第四位高位为0,重新hash数值不变,第四位为1,重新hash数值比原来大16(旧数组的容量)
位置不变或索引+旧容量大小;
扩容元素的移动方式
先判断是否需要扩容,再插入
先进行插入,插入完成再判断是否需要扩容;
插入元素与判断扩容的顺序
1.8HashMap的优化
当A线程判断index位置为空后正好挂起,B线程开始往index位置写入数据,这时A线程恢复现场,执行赋值操作,就把A线程的数据给覆盖了;
数据覆盖问题
同时扩容
不安全
Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。
操作方法上加synchronized关键字,锁住整个数组,粒度比较大,
HashTable
使用Collections集合工具的内部类,通过传入Map封装出一个SynchronizedMap对象,内部定义了一个对象锁,方法内通过对象锁实现;
Collections.synchronizedMap
使用分段锁,降低了锁粒度,让并发度大大提高。
成员变量使用volatile 修饰,免除了指令重排序,同时保证内存可见性
使用CAS操作和synchronized结合实现赋值操作,多线程操作只会锁住当前操作索引的节点。
span style=\
怎么解决HashMap线程不安全的问题
HashMap的线程安全性
hashmap基于哈希表的 map接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。
新结点插入链表的尾部
HashMap的总结
HashMap
Segment 数组结构和 HashEntry 数组结构组成
哈希桶数组切分成小数组(Segment ),每个小数组有 n 个 HashEntry 组成。
Segment
volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next,保证了多线程环境下数据获取时的可见性!
HashEntry
Node数组+链表+红黑树结构
将锁的级别控制在了更细粒度的哈希桶数组元素级别,也就是说只需要锁住这个链表头节点(红黑树的根节点),就不会影响其他的哈希桶数组元素的读写,大大提高了并发度
synchronized 体现在 put操作 synchronized代码块将对应位置头结点当做锁对插入操作加锁
采用CAS + synchronized实现更加细粒度的锁。
synchronized 锁的实现引入了大量的优化,
并且 synchronized 有锁升级过程,会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
使用可重入锁来获得同步支持,那么每个节点都需要通过继承 AQS 来获得同步支持
并不是每个节点都需要获得同步支持的,只有链表的头节点(红黑树的根节点)需要同步,这无疑带来了巨大内存浪费。
减少内存开销
为什么使用内置锁 synchronized替换 可重入锁 ReentrantLock
首先会尝试获取锁,如果获取失败肯定就有其他线程存在竞争,则利用 scanAndLockForPut() 自旋获取锁。
1. 根据 key 计算出 hash 值;2. 判断是否需要进行初始化;3. 定位到 Node,拿到首节点 f,判断首节点 f: 1. 如果为 null ,则通过 CAS 的方式尝试添加; 2. 如果为 f.hash = MOVED = -1 ,说明其他线程在扩容,参与一起扩容; 3. 如果都不满足 ,synchronized 锁住 f 节点,判断是链表还是红黑树,遍历插入;4. 当在链表长度达到 8 的时候,数组扩容或者将链表转换为红黑树。
put()
根据 key 计算出 hash 值定位到具体的 Segment ,再根据 hash 值获取定位 HashEntry 对象,并对 HashEntry 对象进行链表遍历,由于 HashEntry 涉及到的共享变量都使用 volatile 修饰,volatile 可以保证内存可见性,所以每次获取时都是最新值。
1. 根据 key 计算出 hash 值,判断数组是否为空;2. 如果是首节点,就直接返回;3. 如果是红黑树结构,就从红黑树里面查询;4. 如果是链表结构,循环遍历判断。
get 方法不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的,在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。
哈希桶数组table用 volatile 修饰主要是保证在数组扩容的时候保证可见性。和get方法不需要加锁无关
是否需要加锁?
get()
put操作会判断 key==null value==null 并且抛出空指针异常
因为 ConcurrentHashMap 是用于多线程的 ,如果ConcurrentHashMap.get(key)得到了 null ,这就无法判断,是映射的value是 null ,还是没有找到对应的key而为 null ,就有了二义性。
而用于单线程状态的 HashMap 却可以用containsKey(key) 去判断到底是否包含了这个 null 。
反证法
不支持 key 或者 value 为 null 的原因
Segment[]的数组长度,默认是16
并发度
- 数据结构:取消了 Segment 分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。- 保证线程安全机制:JDK1.7 采用 Segment 的分段锁机制实现线程安全,其中 Segment 继承自 ReentrantLock 。JDK1.8 采用CAS+synchronized保证线程安全。- 锁的粒度:JDK1.7 是对需要进行数据操作的 Segment 加锁,JDK1.8 调整为对每个数组元素加锁(Node)。- 链表转化为红黑树:定位节点的 hash 算法简化会带来弊端,hash 冲突加剧,因此在链表节点数量大于 8(且数据总量大于等于 64)时,会将链表转化为红黑树进行存储。- 查询时间复杂度:从 JDK1.7的遍历链表O(n), JDK1.8 变成遍历红黑树O(logN)。
JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别
ConcurrentHashMap
数据结构
线程不安全
JDK1.7 采用 Segment 的分段锁机制实现线程安全,其中 Segment 继承自 ReentrantLock
JDK1.8 采用CAS+synchronized保证线程安全
如何保证线程安全
JDK1.7 是对需要进行数据操作的 Segment 加锁
JDK1.8 调整为对每个数组元素加锁(Node)。
锁的粒度
ConcurrentMap
线程安全
HashMap vs CourrentHashMap
通过红黑树实现
根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序
有序key-value集合
TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
介绍
- 1. 每个节点都只能是红色或者黑色 - 2. 根节点是黑色 - 3. 每个叶节点(NIL节点,空节点)是黑色的。 - 4. 如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。 - 5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
属性
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的
约束
红黑树
1. 以根节点为初始节点进行检索。2. 与当前节点进行比对,若新增节点值较大,则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。3. 循环递归2步骤知道检索出合适的叶子节点为止。4. 将新增节点与3步骤中找到的节点进行比对,如果新增节点较大,则添加为右子节点;否则添加为左子节点。
构建排序二叉树
fixAfterInsertion(e);
左旋:rotateLeft()
P.right ---> G. G.parent ---> P。
右旋:rotateRight()
在红黑树中,它是依靠节点的颜色来维持平衡的。
着色:setColor()
平衡二叉树
对该节点直接删除即可,不会影响树的结构
该节点为叶子节点它不可能存在子节点-----如子节点为黑,则违反黑节点数原则
无子节点(红色节点)
用子节点替代待删除节点,然后删除子节点即可
有一个子节点
需要找到一个替代待删除节点(N)来替代它,然后删除N即可
有两个子节点
delete()
TreeMap
将所有Entry节点链入一个双向链表的HashMap
HashMap+双向链表
LinkedHashMap是HashMap的子类,所以LinkedHashMap自然会拥有HashMap的所有特性
额外维护了一个双向链表用于保持迭代顺序。此外,LinkedHashMap可以很好的支持LRU算法
LinkedHashMap
Hashtable
作者不同
都实现了Map、Cloneable、Serializable三个接口。
HashMap继承自抽象类AbstractMap
HashTable继承自抽象类Dictionary。其中Dictionary类是一个已经被废弃的类
继承父类不同
elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上,contansValue() 就只是调用了一下contains() 方法
Hashtable比HashMap多提供了elments() 和contains() 两个方法。
对外接口不同
- 当get()方法返回null值时,可能是 HashMap中没有该键,也可能使该键所对应的值为null。- 因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。
既不支持Null key也不支持Null value
- 当key为Null时,调用put() 方法,key.hashCode()会报空指针异常- 当value为null值时,put()方法先判断value==null 直接报空指针异常
对Null key 和Null value的支持不同
HashMap不是线程安全的,在多线程并发的环境下,可能会产生死锁等问题。使用HashMap时就必须要自己增加同步处理,
Hashtable是线程安全的,它的每个方法中都加入了Synchronize方法。
Hashtable、HashMap都使用了 Iterator。而由于历史原因,Hashtable还使用了Enumeration的方式 。
HashMap的Iterator是fail-fast迭代器。当有其它线程改变了HashMap的结构(增加,删除,修改元素),将会抛出ConcurrentModificationException。
不过,通过Iterator的remove()方法移除元素则不会抛出ConcurrentModificationException异常
JDK8之前的版本中,Hashtable是没有fast-fail机制的。在JDK8及以后的版本中 ,HashTable也是使用fast-fail的
modcount可以理解为是当前hashtable的状态。每发生一次操作,状态就向前走一步。设置这个状态,主要是由于hashtable等容器类在迭代时,判断数据是否过时时使用的。
modCount
遍历方式的内部实现上不同
默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。
默认的初始大小为11,之后每次扩充,容量变为原来的2n+1
创建时,如果给定了容量初始值,那么Hashtable会直接使用你给定的大小,而HashMap会将其扩充为2的幂次方大小。
初始容量和每次扩充容量大小
为了得到元素的位置,首先需要根据元素的 KEY计算出一个hash值,然后再用这个hash值来计算得到最终的位置。
对象的hashCode 除以数组长度的余数得到在数组的位置
HashMap为了提高计算效率,将哈希表的大小设为2的幂,这样在取模预算时,不需要做除法,只需要做位运算。位运算比除法的效率要高很多。
HashMap通过扰动函数将高16位和低16异或 得到hash值
计算hash值的方法
HashMap vs Hashtable
HashMap vs 其他Map
HashSet
TreeSet
因为存入底层HashMap是通过存入元素的hashcode()找到放入HashMap的位置
集合元素有序 因为底层基于TreeMap实现
元素是否有序
null值的支持
都不是线程安全的
同理
为什么集合元素不重复
通过底层TreeMap的put方法实现
add()
调用底层Map的containsKey()
contains()
HashSet vs TreeSet
Arraylist 底层使用的是Object数组
LinkedList 底层使用的是双向链表数据结构;
ArrayList
LinkedList 采用链表存储,所以插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)
LinkedList
插入删除
快速随机访问就是通过元素的序号快速获取元素对象(对应于`get(int index)`方法)。
ArrayList 实现了RandmoAccess 接口,有随机访问功能。
LinkedList 不支持高效的随机元素访问,
快速访问
ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间
LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)。
内存空间占用
Arraylist与 LinkedList
Vector是线程安全的,ArrayList不是线程安全的。其中,Vector在关键性的方法前面都加了synchronized关键字,来保证线程的安全性
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍,Vector是扩展1倍,
ArrayList 与 Vector
- Array 可以包含基本类型和对象类型,ArrayList 只能包含对象类型。- Array 大小是固定的,ArrayList 的大小是动态变化的。- ArrayList 提供了更多的方法和特性,比如:addAll(),removeAll(),iterator() 等等。
Array 和 ArrayList
ArrayList扩容的本质就是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。默认情况下,新的容量会是原容量的1.5倍
判断是否可以容纳e,若能,则直接添加在末尾;若不能,则进行扩容,然后再把e添加在末尾
每次在add()一个元素时,arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力,经过处理之后将元素存储在数组elementData的尾部
过程
ArrayList 的扩容机制
ArrayList vs LinkedList vs Vector
它的作用是判断两个对象的地址是不是相等。即,判断两个对象是不是同一个对象。(基本数据类型 == 比较的是值,引用数据类型 == 比较的是内存地址)
==
它的作用也是判断两个对象是否相等。但它一般有两种使用情况:
情况1:类没有覆盖 equals() 方法。则通过 equals() 比较该类的两个对象时,等价于通过“==”比较这两个对象。
情况2:类覆盖了 equals() 方法。一般,我们都覆盖 equals() 方法来两个对象的内容相等;若它们的内容相等,则返回 true (即,认为这两个对象相等)。
equals()
String中的equals方法是被重写过的,因为object的equals方法是比较的对象的内存地址,而String的equals方法比较的是对象的值。
当创建String类型的对象时,虚拟机会在常量池中查找有没有已经存在的值和要创建的值相同的对象,如果有就把它赋给当前引用。如果没有就在常量池中重新创建一个String对象。
String中的equals方法
== 和 equals 的区别是什么
1.使用hashcode方法提前校验,可以避免每一次比对都调用equals方法,提高效率
2.保证是同一个对象,如果重写了equals方法,而没有重写hashcode方法,会出现equals相等的对象,hashcode不相等的情况,重写hashcode方法就是为了避免这种情况的出现。
为什么重写equals要重写hashcode
HashCode vs Equals
B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个)
B树相对于B+树的优点是,如果经常访问的数据离根节点很近,而B树的非叶子节点本身存有关键字其数据的地址,所以这种数据检索的时候会要比B+树快。
所有节点关键字是按递增次序排列,并遵循左小右大原则;
排序方式:
非叶节点的子节点数>1,且<=M ,且M>=2,空树除外
子节点数
枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);
关键字数
所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null
结构
获取根节点的关键字进行比较,当前根节点关键字为M,E<M(26个字母顺序),所以往找到指向左边的子节点
拿到关键字D和G,D<E<G 所以直接找到D和G中间的节点
拿到E和F,因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null);
查找
>阶数-1就需要拆分成两个
插入
<阶数/2 需要合并 先子后父
删除
B树
- B+树的层级更少:相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;- B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;- B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。- B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。
B+树
B*树是B+树的变种
B+树初始化的关键字初始化个数是cei(m/2),b*树的初始化个数为(cei(2/3*m))
B+树节点满时就会分裂,而B*树节点满时会检查兄弟节点是否满(因为每个节点都有指向兄弟的指针),如果兄弟节点未满则向兄弟节点转移关键字,如果兄弟节点已满,则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来;
B*树
1、相同思想和策略从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的,都是采用二分法和数据平衡策略来提升查找数据的速度;2、不同的方式的磁盘空间利用不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变,每一次演变都是为了让节点的空间更合理的运用起来,从而使树的层级减少达到快速查找数据的目的;
B树总结
B树 vs B+树
StringBuffer vs StringBuilder
它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时,有可能会产生fail-fast机制
假设存在两个线程(线程1、线程2),线程1通过Iterator在遍历集合A中的元素,在某个时候线程2修改了集合A的结构(是结构上面的修改,而不是简单的修改集合元素的内容),那么这个时候程序就会抛出 ConcurrentModificationException 异常,从而产生fail-fast机制。
什么是fast-fail
程序在对 collection 进行迭代时,某个线程对该 collection 在结构上对其做了修改,这时迭代器就会抛出 ConcurrentModificationException 异常信息,从而产生 fail-fast。
ArrayList中无论add、remove、clear方法只要是涉及了改变ArrayList元素的个数的方法都会导致modCount的改变。所以我们这里可以初步判断由于expectedModCount 得值与modCount的改变不同步,导致两者之间不等从而产生fail-fast机制
有两个线程(线程A,线程B),其中线程A负责遍历list、线程B修改list。线程A在遍历list过程的某个时候(此时expectedModCount = modCount=N),线程启动,同时线程B增加一个元素,这是modCount的值发生改变(modCount + 1 = N + 1)。线程A继续遍历执行next方法时,通告checkForComodification方法发现expectedModCount = N ,而modCount = N + 1,两者不等,这时就抛出ConcurrentModificationException 异常,从而产生fail-fast机制。
fail-fast产生原因
在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList,这样就可以解决。但是不推荐,因为增删造成的同步锁可能会阻塞遍历操作。
使用CopyOnWriteArrayList来替换ArrayList
所有可变操作(add、set 等等)都是通过对底层数组进行一次新的复制来实现的
1:在不能或不想进行同步遍历,但又需要从并发线程中排除冲突时。
2:当遍历操作的数量大大超过可变操作的数量时
适用场景
copy原来的array,再在copy数组上进行add操作,这样做就完全不会影响COWIterator中的array了。
- 任何对array在结构上有所改变的操作(add、remove、clear等),CopyOnWriterArrayList都会copy现有的数据,再在copy的数据上修改,- 这样就不会影响COWIterator中的数据了,修改完成之后改变原有数据的引用即可。- 同时这样造成的代价就是产生大量的对象,同时数组的copy也是相当有损耗的。
CopyOnWriteArrayList
fail-fast解决办法
fast-fail
被复制对象的所有变量都含有与原来的对象相同的值,而所有的对其他对象的引用仍然指向原来的对象。即对象的浅拷贝会对“主”对象进行拷贝,但不会复制主对象里面的对象。”里面的对象“会在原来的对象和它的副本之间共享。
浅拷贝
深拷贝把要复制的对象所引用的对象都复制了一遍。
深拷贝
深拷贝 vs 浅拷贝
0 条评论
回复 删除
下一页