南宁建设厅网站是什么,西部数码空间的网站访问统计,室内装修设计软件哪个最好,智能免费建站一.hashmap的数据结构 HashMap采取数组加链表的存储方式(哈希表)来实现。亦即数组#xff08;散列桶#xff09;中的每一个元素都是链表 二.hashmap的构造函数 HashMap()#xff1a;构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。 HashMap(int initia… 一.hashmap的数据结构 HashMap采取数组加链表的存储方式(哈希表)来实现。亦即数组散列桶中的每一个元素都是链表 二.hashmap的构造函数 HashMap()构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。 HashMap(int initialCapacity)构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。 HashMap(int initialCapacity, float loadFactor)构造一个带指定初始容量和加载因子的空 HashMap。 三.hashmap的存取实现 Entry是HashMap的内部类。包含四个值nextkeyvaluehash其中next是一个指向 Entry的指针key相当于上面节点的值 value对应要保存的值hash值由key产生hashmap中要找到某个元素需要根据hash值来求得对应数组中的位置然后在由key来在链表中找Entry的位置。 1.Put方法的原理 调用Put方法的时候发生了什么呢 比如调用 hashMap.put(apple, 0) 插入一个Key为“apple的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置index index Hash“apple” 假定最后计算出的index是2那么结果如下 但是因为HashMap的长度是有限的当插入的Entry越来越多时再完美的Hash函数也难免会出现index冲突的情况。比如下面这样 这时候该怎么办呢我们可以利用链表来解决。 HashMap数组的每一个元素不止是一个Entry对象也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时只需要插入到对应的链表即可 需要注意的是新来的Entry节点插入链表时使用的是“头插法”。至于为什么不插入链表尾部后面会有解释。 2.Get方法的原理 使用Get方法根据Key来查找Value的时候发生了什么呢 首先会把输入的Key做一次Hash映射得到对应的index index Hash“apple” 由于刚才所说的Hash冲突同一个位置有可能匹配到多个Entry这时候就需要顺着对应链表的头节点一个一个向下来查找。假设我们要查找的Key是“apple” 第一步我们查看的是头节点Entry6Entry6的Key是banana显然不是我们要找的结果。 第二步我们查看的是Next节点Entry1Entry1的Key是apple正是我们要找的结果。 之所以把Entry6放在头节点是因为HashMap的发明者认为后插入的Entry被查找的可能性更大。 四.hashmap的初始大小 table初始大小并不是构造函数中的initialCapacity而是 initialCapacity的2的n次幂 index HashCodeKey Length - 1 长度16或者其他2的幂Length-1的值是所有二进制位全为1这种情况下index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀Hash算法的结果就是均匀的。 五.初始容量、扩容和加载因子 在这里提到了两个参数初始容量加载因子。这两个参数是影响HashMap性能的重要参数其中容量表示哈希表中桶的数量初始容量是创建哈希表时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度它衡量的是一个散列表的空间的使用程度负载因子越大表示散列表的装填程度越高反之愈小。 因此如果负载因子越大对空间的利用更充分然而后果是查找效率的降低 如果负载因子太小那么散列表的数据将过于稀疏对空间造成严重浪费。系统默认负载因子为0.75一般情况下我们是无需修改的 为了保证HashMap的效率系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数那么预设元素的个数能够有效的提高HashMap的性能。 扩容总结: 1.Hashmap在插入元素过多的时候需要进行ResizeResize的条件是 HashMap.Size Capacity * LoadFactor。 2.Hashmap的Resize包含扩容和ReHash两个步骤ReHash在并发的情况下可能会形成链表环。 六.hashmap与treemap的区别 TreeMap与HashMap的不同表象上时TreeMap可以对Key进行排序原因时TreeMap使用的时“红黑树”的二叉树结构储存Entry也就是排序二叉树左边恒放比此值小的数右边恒放比此值大的树按照当前节点值与传入查询值的比较进行判断决定其存放位置/查询其数值 图片来自:https://mp.weixin.qq.com/s?__bizMzIxMjE5MTE1Nwmid2653191907idx1sn876860c5a9a6710ead5dd8de37403ffcchksm8c990c39bbee852f71c9dfc587fd70d10b0eab1cca17123c0a68bf1e16d46d71717712b91509scene21#wechat_redirect ------------------------------------------------------------------------------------------------------------------------------------------- 七、jdk1.7和1.8的区别 1.8引入了红黑树当链表长度大于8的时候会自动转化为红黑树 转载于:https://www.cnblogs.com/JavaZhangXu/p/10037986.html
