首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

【JavaP6大纲】Java基础篇:HashMap底层原理

HashMap是Map的一个实现类,它是以键值对存储数据的,Key-Value都是Map.Entry中的属性。当我们向HashMap中存放一个元素(k1,v1),先根据k1的hashCode方法来决定在数组中存放的位置。如果这个位置没有其它元素,将(k1,v1)直接放入一个Node类型的数组中,当元素加到12的时候,底层会进行扩容,扩容为原来的2倍。如果该位置已经有其它元素(k2,v2),那就调用k1的equals方法和k2进行比较二个元素是否相同,如果结果为true,说明二个元素是一样的,用v1替换v2,如果返回值为false,二个元素不一样,就用链表的形式将(k1,v1)存放。不过当链表中的数据较多时,查询的效率会下降,所以在JDK1.8版本后做了一个升级,HashMap存储数据结构链表长度超过8且数组长度大于64时数据结构,会将链表替换成红黑树才会树化时,会将链表替换成红黑树,来提高查找效率。因为对于搜索,插入,删除操作多的情况下,使用红黑树的效率要高一些。因为红黑树是一种特殊的二叉查找树,二叉查找树所有节点的左子树都小于该节点,所有节点的右子树都大于该节点,就可以通过大小比较关系来进行快速的检索。在红黑树上插入或者删除一个节点之后,红黑树就发生了变化,但它不再是一颗红黑树时,可以通过左旋和右旋,保证每次插入最多只需要三次旋转就能达到平衡,因为红黑树强制约束了从根到叶子的最长的路径不多于最短的路径的两倍长,插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。

02

HashMap底层原理?

HashMap是Map的一个实现类,它是以键值对存储数据的,Key-Value都是Map.Entry中的属性。当我们向HashMap中存放一个元素(k1,v1),先根据k1的hashCode方法来决定在数组中存放的位置。如果这个位置没有其它元素,将(k1,v1)直接放入一个Node类型的数组中,当元素加到12的时候,底层会进行扩容,扩容为原来的2倍。如果该位置已经有其它元素(k2,v2),那就调用k1的equals方法和k2进行比较二个元素是否相同,如果结果为true,说明二个元素是一样的,用v1替换v2,如果返回值为false,二个元素不一样,就用链表的形式将(k1,v1)存放。不过当链表中的数据较多时,查询的效率会下降,所以在JDK1.8版本后做了一个升级,HashMap存储数据结构链表长度超过8且数组长度大于64时数据结构,会将链表替换成红黑树才会树化时,会将链表替换成红黑树,来提高查找效率。因为对于搜索,插入,删除操作多的情况下,使用红黑树的效率要高一些。因为红黑树是一种特殊的二叉查找树,二叉查找树所有节点的左子树都小于该节点,所有节点的右子树都大于该节点,就可以通过大小比较关系来进行快速的检索。在红黑树上插入或者删除一个节点之后,红黑树就发生了变化,但它不再是一颗红黑树时,可以通过左旋和右旋,保证每次插入最多只需要三次旋转就能达到平衡,因为红黑树强制约束了从根到叶子的最长的路径不多于最短的路径的两倍长,插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的。

02

C/C++ 常见数组排序算法

本文介绍了几种常见的排序算法的实现,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序和快速排序。冒泡排序通过多次遍历数组,比较并交换相邻元素,逐步将较小元素“浮”到数组顶端,时间复杂度为O(n^2)。选择排序通过选择未排序部分的最小元素进行交换,逐步完成整个数组排序,同样具有O(n^2)的时间复杂度。插入排序将数组分为已排序和未排序部分,逐个插入未排序元素到已排序部分的合适位置,时间复杂度为O(n^2)。希尔排序是插入排序的改进版本,通过分组插入排序,最终得到有序数组,时间复杂度在O(n log n)到O(n^2)之间。归并排序采用分治策略,递归拆分和合并数组,时间复杂度始终为O(n log n),但需要额外空间。最后,快速排序通过选择基准值划分数组,并递归排序子数组,平均时间复杂度为O(n log n),但最坏情况下为O(n^2)。这些算法各有特点,适用于不同场景。

01
领券