石家庄网站推广方案,做wordpress总结,网站浮窗代码,网站建设 硬件HashMap 背诵版 1. HashMap、Hashtable 和 ConcurrentHashMap 的区别#xff1f;1.1 线程安全#xff1a;1.2 继承关系#xff1a;1.3 允不允许null值#xff1a; 2. HashMap 的数据结构2.1 什么是hash表#xff1f;2.2 HashMap 的数据结构 3. 什么是hash冲突#xff0c;… HashMap 背诵版 1. HashMap、Hashtable 和 ConcurrentHashMap 的区别1.1 线程安全1.2 继承关系1.3 允不允许null值 2. HashMap 的数据结构2.1 什么是hash表2.2 HashMap 的数据结构 3. 什么是hash冲突怎么解决3.1 什么是hash冲突3.2 为什么不能完全避免hash冲突3.2 hash冲突怎么解决1开放定址法再散列法2再哈希法3建立公共溢出区4链地址法 4. 为什么在 JDK8 中 HashMap 要转成红黑树4.1 为什么不继续使用链表?4.2 为什么是红黑树1二叉树2二叉平衡树3红黑树自平衡二叉查找树 1. HashMap、Hashtable 和 ConcurrentHashMap 的区别
1.1 线程安全
HashMap 是非线程安全的。
Hashtable 中的方法是同步的所以它是线程安全的。
ConcurrentHashMap 在 JDK1.8 之前使用分段锁以在保证线程安全的同时获得更大的效率。JDK1.8 开始舍弃了分段锁使用 自旋 CAS synchronized 来实现同步。官方的解释中一是节省内存空间 二是分段锁需要更多的内存空间而大多数情况下并发粒度达不到设置的粒度竞争概率较小反而导致更新的长时间等待因为锁定一段后整个段就无法更新了三是提高GC效率。
1.2 继承关系
HashTable 是基于陈旧的 Dictionary 类继承来的。
HashMap 继承的抽象类 AbstractMap 实现了 Map 接口。
ConcurrentHashMap 同样继承了抽象类 AbstractMap并且实现了 ConcurrentMap 接口。
1.3 允不允许null值
HashTable 中key 和 value 都不允许出现 null 值否则会抛出 NullPointerException 异常。
HashMap 中null 可以作为 key、value 都可以。
ConcurrentHashMap 中key、value 都不允许为 null。
2. HashMap 的数据结构
2.1 什么是hash表
哈希表Hash Table是一种常见的数据结构也被称为散列表。它通过使用哈希函数将键映射到存储桶中以实现高效的键值对存储和查找操作。
哈希表的基本原理是通过将键key作为输入经过哈希函数的计算得到一个对应的哈希码hash code。这个哈希码通常是一个整数用于确定键在哈希表中的存储位置。
哈希表内部由一个数组数组的每个元素称为桶和哈希函数组成。当需要存储一个键值对时哈希函数计算出键的哈希码并将其映射到对应的桶中。如果多个键具有相同的哈希码即发生哈希冲突常见的解决方法是使用链表或开放地址法来处理冲突。
在哈希表中通过键的哈希码可以快速定位到对应的桶从而实现快速的查找和插入操作。哈希表的平均时间复杂度为 O(1)即常数时间但在最坏情况下哈希冲突较多时时间复杂度可能会退化为 O(n)其中n是存储的键值对数量。
哈希表在实际应用中被广泛使用例如在编程语言中的字典Dictionary或映射Map数据结构中用于高效地存储和查找键值对。
2.2 HashMap 的数据结构
在 Java 中保存数据有两种比较简单的数据结构数组和链表。
数组的特点是寻址容易插入和删除困难而链表的特点是寻址困难插入和删除容易。 JDK1.8 以前 HashMap 内部数据结构使用 数组 链表 进行存储。了解即可 JDK1.8 以后 HashMap 内部数据结构使用 数组 链表 红黑树 进行存储。 3. 什么是hash冲突怎么解决
3.1 什么是hash冲突
哈希表内部由一个数组数组的每个元素称为桶和哈希函数组成。当需要存储一个键值对时哈希函数计算出键的哈希码并将其映射到对应的桶中。如果多个不同键具有相同的哈希码即发生哈希冲突
比如对应不同的 key 可能获得相同的 hash code即 key1 ≠ key2但是H(key1) H(key2)。
3.2 为什么不能完全避免hash冲突 哈希函数是从关键字集合和地址集合的映像通常关键字集合为无限大、长度不受限制密码、或者文件都可以作为关键字而地址集合却有限无限量映射到有限量上肯定是存在重合的部分这就是冲突。 哈希函数的复杂性设计一个完全避免冲突的哈希函数是非常困难的。哈希函数需要具备均匀地将输入映射到输出空间的特性但在实际情况下很难找到一个完美的哈希函数尤其是当输入数据的特征和分布较为复杂时。
尽管无法完全避免哈希冲突但我们可以通过合理选择和设计哈希函数、调整哈希表的大小和负载因子等方法来降低冲突的概率。此外使用解决冲突的方法如链表法或开放地址法可以处理哈希冲突并保证数据的正确性和高效性。
3.2 hash冲突怎么解决
1开放定址法再散列法
开放定址法就是一旦发生了冲突就去寻找下一个空的散列地址只要散列表足够大空的散列地址总能找到并将记录存入。
2再哈希法
当哈希地址发生冲突用其他的函数计算另一个哈希函数地址直到冲突不再产生为止。
3建立公共溢出区
将哈希表分为基本表和溢出表两部分发生冲突的元素都放入溢出表中。
4链地址法
HashMap 把冲突的这些 key 组成一个单向链表然后采用尾插法把这样一个 key 保存到链表的尾部另外为了避免链表过长影响查询效率在链表长度大于 8并且数组长度大于等于 64 的时候HashMap 会把当前链表转化为红黑树从而减少链表查询时间复杂度的问题来提升查询效率。
4. 为什么在 JDK8 中 HashMap 要转成红黑树
4.1 为什么不继续使用链表?
HashMap 解决hash冲突是通过链地址法完成的在 JDK8 之前如果产生冲突就会把新增的元素增加到当前桶所在的链表中。
这样就会产生一个问题当某个 bucket 冲突过多的时候其指向的链表就会变得很长这样如果 put 或者 get 该 bucket 上的元素时复杂度就无限接近于O(N)这样显然是不可以接受的。
所以在 JDK1.7 的时候在元素 put 之前做 hash 的时候就会充分利用扰动函数将不同 key 的 hash 尽可能的分散开。不过这样做起来效果还不是太好所以当链表过长的时候我们就要对其数据结构进行修改。
4.2 为什么是红黑树
1二叉树
所谓的二叉查找树一定是 left root right这样我们遍历的时间复杂度就会由链表的 O(N) 变为二叉查找树的 O(logN)二叉查找树如下所示 二叉搜索树通过增加了一条搜索路径提高了查询效率查找的效率取决于树的深度高度。但是对于极端情况当子节点都比父节点大或者小的时候二叉查找树又会退化成链表查询复杂度会重新变为 O(N)如下所示 2二叉平衡树
二叉平衡树会在每次插入操作时来检查每个节点的左子树和右子树的高度差至多等于1如果 1就需要进行左旋或者右旋操作使其查询复杂度一直维持在 O(logN)。
但是这样就万无一失了吗其实并不然我们不仅要保证查询的时间复杂度还需要保证插入的时间复杂度足够低因为平衡二叉树要求高度差最多为 1非常严格导致每次插入都需要左旋或者右旋极大的消耗了插入的时间。 对于那些插入和删除比较频繁的场景AVL树显然是不合适的。为了保证查询和插入的时间复杂度维持在一个均衡的水平上所以就引入了红黑树。
3红黑树自平衡二叉查找树
在红黑树中所有的叶子节点都是黑色的的空节点也就是叶子节点不存数据任何相邻的节点都不能同时为红色红色节点是被黑色节点隔开的每个节点从该节点到达其可达的叶子节点的所有路径都包含相同数目的黑色节点。
我们可以得到如下结论红黑树不会像 AVL树 一样追求绝对的平衡它的插入最多两次旋转删除最多三次旋转在频繁的插入和删除场景中红黑树的时间复杂度是优于AVL树的。 综上所述这就是HashMap选择红黑树的原因。
