本站提供最佳星光博客源码服务,欢迎转载和分享。

【音频光纤源码】【javaweb抽奖系统源码】【装b利器源码】hashmap(1.8)源码

2024-12-25 08:58:49 来源:员工签到小程序源码怎么做 分类:探索

1.HashMap为什么不安全?
2.hashmap底层实现原理
3.Java面试问题:HashMap的底层原理
4.JDK成长记7:3张图搞懂HashMap底层原理!
5.HashMap不明白?来看看这篇文章吧!

hashmap(1.8)源码

HashMap为什么不安全?

       åŽŸå› ï¼š

       JDK1.7 中,由于多线程对HashMap进行扩容,调用了HashMap#transfer(),具体原因:某个线程执行过程中,被挂起,其他线程已经完成数据迁移,等CPU资源释放后被挂起的线程重新执行之前的逻辑,数据已经被改变,造成死循环、数据丢失。

       JDK1.8 中,由于多线程对HashMap进行put操作,调用了HashMap#putVal(),具体原因:假设两个线程A、B都在进行put操作,并且hash函数计算出的插入下标是相同的,当线程A执行完第六行代码后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,从而线程不安全。

       æ”¹å–„:

       æ•°æ®ä¸¢å¤±ã€æ­»å¾ªçŽ¯å·²ç»åœ¨åœ¨JDK1.8中已经得到了很好的解决,如果你去阅读1.8的源码会发现找不到HashMap#transfer(),因为JDK1.8直接在HashMap#resize()中完成了数据迁移。

       2、HashMap线程不安全的体现:

       JDK1.7 HashMap线程不安全体现在:死循环、数据丢失

       JDK1.8 HashMap线程不安全体现在:数据覆盖

       äºŒã€HashMap线程不安全、死循环、数据丢失、数据覆盖的原因

       1、JDK1.7 扩容引发的线程不安全

       HashMap的线程不安全主要是发生在扩容函数中,其中调用了JDK1.7 HshMap#transfer():

void transfer(Entry[] newTable, boolean rehash) {

          int newCapacity = newTable.length;

          for (Entry<K,V> e : table) {

              while(null != e) {

                  Entry<K,V> next = e.next;

                  if (rehash) {

                      e.hash = null == e.key ? 0 : hash(e.key);

                  }

                  int i = indexFor(e.hash, newCapacity);

                  e.next = newTable[i];

                  newTable[i] = e;

                  e = next;

              }

          }

       }

       å¤åˆ¶ä»£ç 

       è¿™æ®µä»£ç æ˜¯HashMap的扩容操作,重新定位每个桶的下标,并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转,这也是形成死循环的关键点。理解了头插法后再继续往下看是如何造成死循环以及数据丢失的。

       2、扩容造成死循环和数据丢失

       å‡è®¾çŽ°åœ¨æœ‰ä¸¤ä¸ªçº¿ç¨‹A、B同时对下面这个HashMap进行扩容操作:

       æ­£å¸¸æ‰©å®¹åŽçš„结果是下面这样的:

       ä½†æ˜¯å½“线程A执行到上面transfer函数的第行代码时,CPU时间片耗尽,线程A被挂起。即如下图中位置所示:

       æ­¤æ—¶çº¿ç¨‹A中:e=3、next=7、e.next=null

       å½“线程A的时间片耗尽后,CPU开始执行线程B,并在线程B中成功的完成了数据迁移

       é‡ç‚¹æ¥äº†ï¼Œæ ¹æ®Java内存模式可知,线程B执行完数据迁移后,此时主内存中newTable和table都是最新的,也就是说:7.next=3、3.next=null。

       éšåŽçº¿ç¨‹A获得CPU时间片继续执行newTable[i] = e,将3放入新数组对应的位置,执行完此轮循环后线程A的情况如下:

       æŽ¥ç€ç»§ç»­æ‰§è¡Œä¸‹ä¸€è½®å¾ªçŽ¯ï¼Œæ­¤æ—¶e=7,从主内存中读取e.next时发现主内存中7.next=3,此时next=3,并将7采用头插法的方式放入新数组中,并继续执行完此轮循环,结果如下:

       æ­¤æ—¶æ²¡ä»»ä½•é—®é¢˜ã€‚

       ä¸Šè½®next=3,e=3,执行下一次循环可以发现,3.next=null,所以此轮循环将会是最后一轮循环。

       æŽ¥ä¸‹æ¥å½“执行完e.next=newTable[i]即3.next=7后,3和7之间就相互连接了,当执行完newTable[i]=e后,3被头插法重新插入到链表中,执行结果如下图所示:

       ä¸Šé¢è¯´äº†æ­¤æ—¶e.next=null即next=null,当执行完e=null后,将不会进行下一轮循环。到此线程A、B的扩容操作完成,很明显当线程A执行完后,HashMap中出现了环形结构,当在以后对该HashMap进行操作时会出现死循环。

       å¹¶ä¸”从上图可以发现,元素5在扩容期间被莫名的丢失了,这就发生了数据丢失的问题。

       3、JDK1.8中的线程不安全

       ä¸Šé¢çš„扩容造成的数据丢失、死循环已经在在JDK1.8中已经得到了很好的解决,如果你去阅读1.8的源码会发现找不到HashMap#transfer(),因为JDK1.8直接在HashMap#resize()中完成了数据迁移。

       ä¸ºä»€ä¹ˆè¯´ JDK1.8会出现数据覆盖的情况? æˆ‘们来看一下下面这段JDK1.8中的put操作代码:

       å…¶ä¸­ç¬¬å…­è¡Œä»£ç æ˜¯åˆ¤æ–­æ˜¯å¦å‡ºçŽ°hash碰撞,假设两个线程A、B都在进行put操作,并且hash函数计算出的插入下标是相同的,当线程A执行完第六行代码后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,从而线程不安全。

       é™¤æ­¤ä¹‹å‰ï¼Œè¿˜æœ‰å°±æ˜¯ä»£ç çš„第行处有个++size,我们这样想,还是线程A、B,这两个线程同时进行put操作时,假设当前HashMap的zise大小为,当线程A执行到第行代码时,从主内存中获得size的值为后准备进行+1操作,但是由于时间片耗尽只好让出CPU,线程B快乐的拿到CPU还是从主内存中拿到size的值进行+1操作,完成了put操作并将size=写回主内存,然后线程A再次拿到CPU并继续执行(此时size的值仍为),当执行完put操作后,还是将size=写回内存,此时,线程A、B都执行了一次put操作,但是size的值只增加了1,所有说还是由于数据覆盖又导致了线程不安全。

       ä¸‰ã€å¦‚何使HashMap在多线程情况下进行线程安全操作?

       ä½¿ç”¨ Collections.synchronizedMap(map),包装成同步Map,原理就是在HashMap的所有方法上synchronized。

       ä¾‹å¦‚:Collections.SynchronizedMap#get()

public V get(Object key) {

          synchronized (mutex) {

              return m.get(key);

          }

       }

       å¤åˆ¶ä»£ç 

       å››ã€æ€»ç»“

       1、HashMap线程不安全原因:

       åŽŸå› ï¼š

       JDK1.7 中,由于多线程对HashMap进行扩容,调用了HashMap#transfer(),具体原因:某个线程执行过程中,被挂起,其他线程已经完成数据迁移,等CPU资源释放后被挂起的线程重新执行之前的逻辑,数据已经被改变,造成死循环、数据丢失。

       JDK1.8 中,由于多线程对HashMap进行put操作,调用了HashMap#putVal(),具体原因:假设两个线程A、B都在进行put操作,并且hash函数计算出的插入下标是相同的,当线程A执行完第六行代码后由于时间片耗尽导致被挂起,而线程B得到时间片后在该下标处插入了元素,完成了正常的插入,然后线程A获得时间片,由于之前已经进行了hash碰撞的判断,所有此时不会再进行判断,而是直接进行插入,这就导致了线程B插入的数据被线程A覆盖了,从而线程不安全。

       æ”¹å–„:

       æ•°æ®ä¸¢å¤±ã€æ­»å¾ªçŽ¯å·²ç»åœ¨åœ¨JDK1.8中已经得到了很好的解决,如果你去阅读1.8的源码会发现找不到HashMap#transfer(),因为JDK1.8直接在HashMap#resize()中完成了数据迁移。

       2、HashMap线程不安全的体现:

       JDK1.7 HashMap线程不安全体现在:死循环、数据丢失

       JDK1.8 HashMap线程不安全体现在:数据覆盖

hashmap底层实现原理

       hashmap底层实现原理是SortedMap接口能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。

       å¦‚果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

       Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable

       ä»Žç»“构实现来讲,HashMap是:数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的。

扩展资料

       ä»Žæºç å¯çŸ¥ï¼ŒHashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组。Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对),除了K,V,还包含hash和next。

       HashMap就是使用哈希表来存储的。哈希表为解决冲突,采用链地址法来解决问题,链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。

       å¦‚果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,其实就是在根据实际情况确定哈希桶数组的大小,并在此基础上设计好的hash算法减少Hash碰撞。

Java面试问题:HashMap的底层原理

       JDK1.8中HashMap的put()和get()操作的过程

       put操作:

       ①首先判断数组是否为空,如果数组为空则进行第一次扩容(resize)

       ②根据key计算hash值并与上数组的长度-1(int index = key.hashCode()&(length-1))得到键值对在数组中的索引。

       ③如果该位置为null,则直接插入

       ④如果该位置不为null,音频光纤源码则判断key是否一样(hashCode和equals),如果一样则直接覆盖value

       ⑤如果key不一样,则判断该元素是否为 红黑树的节点,如果是,则直接在 红黑树中插入键值对

       ⑥如果不是 红黑树的节点,则就是 链表,遍历这个 链表执行插入操作,如果遍历过程中若发现key已存在,直接覆盖value即可。

       如果 链表的长度大于等于8且数组中元素数量大于等于阈值,则将 链表转化为 红黑树,(先在 链表中插入再进行判断)

       如果 链表的长度大于等于8且数组中元素数量小于阈值,则先对数组进行扩容,不转化为 红黑树。

       ⑦插入成功后,判断数组中元素的个数是否大于阈值(threshold),超过了就对数组进行扩容操作。

       get操作:

       ①计算key的hashCode的值,找到key在数组中的位置

       ②如果该位置为null,就直接返回null

       ③否则,根据equals()判断key与当前位置的值是否相等,如果相等就直接返回。

       ④如果不等,再判断当前元素是否为树节点,如果是树节点就按 红黑树进行查找。

       ⑤否则,按照 链表的方式进行查找。

       3.HashMap的扩容机制

       4.HashMap的初始容量为什么是?

       1.减少hash碰撞 (2n ,=2^4)

       2.需要在效率和内存使用上做一个权衡。这个值既不能太小,也不能太大。

       3.防止分配过小频繁扩容

       4.防止分配过大浪费资源

       5.HashMap为什么每次扩容都以2的整数次幂进行扩容?

       因为Hashmap计算存储位置时,使用了(n - 1) & hash。只有当容量n为2的幂次方,n-1的二进制会全为1,位运算时可以充分散列,避免不必要的哈希冲突,所以扩容必须2倍就是为了维持容量始终为2的幂次方。

       6.HashMap扩容后会重新计算Hash值吗?

       ①JDK1.7

       JDK1.7中,javaweb抽奖系统源码HashMap扩容后,所有的key需要重新计算hash值,然后再放入到新数组中相应的位置。

       ②JDK1.8

       在JDK1.8中,HashMap在扩容时,需要先创建一个新数组,然后再将旧数组中的数据转移到新数组上来。

       此时,旧数组中的数据就会根据(e.hash & oldCap),数据的hash值与扩容前数组的长度进行与操作,根据结果是否等于0,分为2类。

       1.等于0时,该节点放在新数组时的位置等于其在旧数组中的位置。

       2.不等于0时,该节点在新数组中的位置等于其在旧数组中的位置+旧数组的长度。

       7.HashMap中当 链表长度大于等于8时,会将 链表转化为 红黑树,为什么是8?

       如果 hashCode 分布良好,也就是 hash 计算的结果离散好的话,那么 红黑树这种形式是很少会被用到的,因为各个值都均匀分布,很少出现 链表很长的情况。在理想情况下, 链表长度符合泊松分布,各个长度的命中概率依次递减,当长度为 8 的时候,概率仅为 0.。这是一个小于千万分之一的概率,通常我们的 Map 里面是不会存储这么多的数据的,所以通常情况下,并不会发生从 链表向 红黑树的转换。

       8.HashMap为什么线程不安全?

       1.在JDK1.7中,当并发执行扩容操作时会造成死循环和数据丢失的情况。

       在JDK1.7中,在多线程情况下同时对数组进行扩容,需要将原来数据转移到新数组中,在转移元素的过程中使用的是头插法,会造成死循环。

       2.在JDK1.8中,在并发执行put操作时会发生数据覆盖的情况。

       如果线程A和线程B同时进行put操作,装b利器源码刚好这两条不同的数据hash值一样,并且该位置数据为null,所以这线程A、B都会通过判断,将执行插入操作。

       假设一种情况,线程A进入后还未进行数据插入时挂起,而线程B正常执行,从而正常插入数据,然后线程A获取CPU时间片,此时线程A不用再进行hash判断了,问题出现:线程A会把线程B插入的数据给覆盖,发生线程不安全。

       9.为什么HashMapJDK1.7中扩容时要采用头插法,JDK1.8又改为尾插法?

       JDK1.7的HashMap在实现resize()时,新table[ ]的列表队头插入。

       这样做的目的是:避免尾部遍历。

       避免尾部遍历是为了避免在新列表插入数据时,遍历到队尾的位置。因为,直接插入的效率更高。

       对resize()的设计来说,本来就是要创建一个新的table,列表的顺序不是很重要。但如果要确保插入队尾,还得遍历出 链表的队尾位置,然后插入,是一种多余的损耗。

       直接采用队头插入,会使得 链表数据倒序。

       JDK1.8采用尾插法是避免在多线程环境下扩容时采用头插法出现死循环的问题。

       .HashMap是如何解决哈希冲突的?

       拉链法(链地址法)

       为了解决碰撞,数组中的元素是单向 链表类型。当 链表长度大于等于8时,会将 链表转换成 红黑树提高性能。

       而当 链表长度小于等于6时,又会将 红黑树转换回单向 链表提高性能。

       .HashMap为什么使用 红黑树而不是B树或 平衡二叉树AVL或二叉查找树?

       1.不使用二叉查找树

       二叉 排序树在极端情况下会出现线性结构。例如:二叉 排序树左子树所有节点的值均小于根节点,如果我们添加的元素都比根节点小,会导致左子树线性增长,这样就失去了用树型结构替换 链表的apk平台源码下载初衷,导致查询时间增长。所以这是不用二叉查找树的原因。

       2.不使用 平衡二叉树

       平衡二叉树是严格的平衡树, 红黑树是不严格平衡的树, 平衡二叉树在插入或删除后维持平衡的开销要大于 红黑树。

       红黑树的虽然查询性能略低于 平衡二叉树,但在插入和删除上性能要优于 平衡二叉树。

       选择 红黑树是从功能、性能和开销上综合选择的结果。

       3.不使用B树/B+树

       HashMap本来是数组+ 链表的形式, 链表由于其查找慢的特点,所以需要被查找效率更高的树结构来替换。

       如果用B/B+树的话,在数据量不是很多的情况下,数据都会“挤在”一个结点里面,这个时候遍历效率就退化成了 链表。

       .HashMap和Hashtable的异同?

       ①HashMap是⾮线程安全的,Hashtable是线程安全的。

       Hashtable 内部的⽅法基本都经过 synchronized 修饰。

       ②因为线程安全的问题,HashMap要⽐Hashtable效率⾼⼀点。

       ③HashMap允许键和值是null,而Hashtable不允许键或值是null。

       HashMap中,null 可以作为键,这样的键只有 ⼀个,可以有 ⼀个或多个键所对应的值为 null。

       HashTable 中 put 进的键值只要有 ⼀个 null,直接抛出 NullPointerException。

       ④ Hashtable默认的初始 大小为,之后每次扩充,容量变为原来的2n+1。

       HashMap默认的初始 大⼩为,之后每次扩充,容量变为原来的2倍。

       ⑤创建时如果给定了容量初始值,那么 Hashtable 会直接使⽤你给定的 ⼤⼩, ⽽ HashMap 会将其扩充为2的幂次⽅ ⼤⼩。

       ⑥JDK1.8 以后的 HashMap 在解决哈希冲突时当 链表⻓度 大于等于8时,将 链表转化为红⿊树,以减少搜索时间。Hashtable没有这样的delphi 服务程序源码机制。

       Hashtable的底层,是以数组+ 链表的形式来存储。

       ⑦HashMap的父类是AbstractMap,Hashtable的父类是Dictionary

       相同点:都实现了Map接口,都存储k-v键值对。

       .HashMap和HashSet的区别?

       HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码⾮常⾮常少,因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet ⾃⼰不得不实现之外,其他⽅法都是直接调用 HashMap 中的⽅法)

       1.HashMap实现了Map接口,HashSet实现了Set接口

       2.HashMap存储键值对,HashSet存储对象

       3.HashMap调用put()向map中添加元素,HashSet调用add()方法向Set中添加元素。

       4.HashMap使用键key计算hashCode的值,HashSet使用对象来计算hashCode的值,在hashCode相等的情况下,使用equals()方法来判断对象的相等性。

       5.HashSet中的元素由HashMap的key来保存,而HashMap的value则保存了一个静态的Object对象。

       .HashSet和TreeSet的区别?

       相同点:HashSet和TreeSet的元素都是不能重复的,并且它们都是线程不安全的。

       不同点:

       ①HashSet中的元素可以为null,但TreeSet中的元素不能为null

       ②HashSet不能保证元素的排列顺序,TreeSet支持自然 排序、定制 排序两种 排序方式

       ③HashSet底层是采用 哈希表实现的,TreeSet底层是采用 红黑树实现的。

       ④HashSet的add,remove,contains方法的时间复杂度是 O(1),TreeSet的add,remove,contains方法的时间复杂度是 O(logn)

       .HashMap的遍历方式?

       ①通过map.keySet()获取key,根据key获取到value

       ②通过map.keySet()遍历key,通过map.values()遍历value

       ③通过Map.Entry(String,String) 获取,然后使用entry.getKey()获取到键,通过entry.getValue()获取到值

       ④通过Iterator

JDK成长记7:3张图搞懂HashMap底层原理!

       一句话讲, HashMap底层数据结构,JDK1.7数组+单向链表、JDK1.8数组+单向链表+红黑树。

       在看过了ArrayList、LinkedList的底层源码后,相信你对阅读JDK源码已经轻车熟路了。除了List很多时候你使用最多的还有Map和Set。接下来我将用三张图和你一起来探索下HashMap的底层核心原理到底有哪些?

       首先你应该知道HashMap的核心方法之一就是put。我们带着如下几个问题来看下图:

       如上图所示,put方法调用了putVal方法,之后主要脉络是:

       如何计算hash值?

       计算hash值的算法就在第一步,对key值进行hashCode()后,对hashCode的值进行无符号右移位和hashCode值进行了异或操作。为什么这么做呢?其实涉及了很多数学知识,简单的说就是尽可能让高和低位参与运算,可以减少hash值的冲突。

       默认容量和扩容阈值是多少?

       如上图所示,很明显第二步回调用resize方法,获取到默认容量为,这个在源码里是1<<4得到的,1左移4位得到的。之后由于默认扩容因子是0.,所以两者相乘就是扩容大小阈值*0.=。之后就分配了一个大小为的Node[]数组,作为Key-Value对存放的数据结构。

       最后一问题是,如何进行hash寻址的?

       hash寻址其实就在数组中找一个位置的意思。用的算法其实也很简单,就是用数组大小和hash值进行n-1&hash运算,这个操作和对hash取模很类似,只不过这样效率更高而已。hash寻址后,就得到了一个位置,可以把key-value的Node元素放入到之前创建好的Node[]数组中了。

       当你了解了上面的三个原理后,你还需要掌握如下几个问题:

       还是老规矩,看如下图:

       当hash值计算一致,比如当hash值都是时,Key-Value对的Node节点还有一个next指针,会以单链表的形式,将冲突的节点挂在数组同样位置。这就是数据结构中所提到解决hash 的冲突方法之一:单链法。当然还有探测法+rehash法有兴趣的人可以回顾《数据结构和算法》相关书籍。

       但是当hash冲突严重的时候,单链法会造成原理链接过长,导致HashMap性能下降,因为链表需要逐个遍历性能很差。所以JDK1.8对hash冲突的算法进行了优化。当链表节点数达到8个的时候,会自动转换为红黑树,自平衡的一种二叉树,有很多特点,比如区分红和黑节点等,具体大家可以看小灰算法图解。红黑树的遍历效率是O(logn)肯定比单链表的O(n)要好很多。

       总结一句话就是,hash冲突使用单链表法+红黑树来解决的。

       上面的图,核心脉络是四步,源码具体的就不粘出来了。当put一个之后,map的size达到扩容阈值,就会触发rehash。你可以看到如下具体思路:

       情况1:如果数组位置只有一个值:使用新的容量进行rehash,即e.hash & (newCap - 1)

       情况2:如果数组位置有链表,根据 e.hash & oldCap == 0进行判断,结果为0的使用原位置,否则使用index + oldCap位置,放入元素形成新链表,这里不会和情况1新的容量进行rehash与运算了,index + oldCap这样更省性能。

       情况3:如果数组位置有红黑树,根据split方法,同样根据 e.hash & oldCap == 0进行树节点个数统计,如果个数小于6,将树的结果恢复为普通Node,否则使用index + oldCap,调整红黑树位置,这里不会和新的容量进行rehash与运算了,index + oldCap这样更省性能。

       你有兴趣的话,可以分别画一下这三种情况的图。这里给大家一个图,假设都出发了以上三种情况结果如下所示:

       上面源码核心脉络,3个if主要是校验了一堆,没做什么事情,之后赋值了扩容因子,不传递使用默认值0.,扩容阈值threshold通过tableSizeFor(initialCapacity);进行计算。注意这里只是计算了扩容阈值,没有初始化数组。代码如下:

       竟然不是大小*扩容因子?

       n |= n >>> 1这句话,是在干什么?n |= n >>> 1等价于n = n | n >>>1; 而|表示位运算中的或,n>>>1表示无符号右移1位。遇到这种情况,之前你应该学到了,如果碰见复杂逻辑和算法方法就是画图或者举例子。这里你就可以举个例子:假设现在指定的容量大小是,n=cap-1=,那么计算过程应该如下:

       n是int类型,java中一般是4个字节,位。所以的二进制: 。

       最后n+1=,方法返回,赋值给threshold=。再次注意这里只是计算了扩容阈值,没有初始化数组。

       为什么这么做呢?一句话,为了提高hash寻址和扩容计算的的效率。

       因为无论扩容计算还是寻址计算,都是二进制的位运算,效率很快。另外之前你还记得取余(%)操作中如果除数是2的幂次方则等同于与其除数减一的与(&)操作。即 hash%size = hash & (size-1)。这个前提条件是除数是2的幂次方。

       你可以再回顾下resize代码,看看指定了map容量,第一次put会发生什么。会将扩容阈值threshold,这样在第一次put的时候就会调用newCap = oldThr;使得创建一个容量为threshold的数组,之后从而会计算新的扩容阈值newThr为newCap*0.=*0.=。也就是说map到了个元素就会进行扩容。

       除了今天知识,技能的成长,给大家带来一个金句甜点,结束我今天的分享:坚持的三个秘诀之一目标化。

       坚持的秘诀除了上一节提到的视觉化,第二个秘诀就是目标化。顾名思义,就是需要给自己定立一个目标。这里要提到的是你的目标不要定的太高了。就比如你想要增加肌肉,给自己定了一个目标,每天5组,每次个俯卧撑,你看到自己胖的身形或者海报,很有刺激,结果开始前两天非常厉害,干劲十足,特别奥利给。但是第三天,你想到要个俯卧撑,你就不想起床,就算起来,可能也会把自己撅死过去......其实你的目标不要一下子定的太大,要从微习惯开始,比如我媳妇从来没有做过俯卧撑,就让她每天从1个开始,不能多,我就怕她收不住,做多了。一开始其实从习惯开始,先变成习惯,再开始慢慢加量。量太大养不成习惯,量小才能养成习惯。很容易做到才能养成,你想想是不是这个道理?

       所以,坚持的第二个秘诀就是定一个目标,可以通过小量目标,养成微习惯。比如每天你可以读五分钟书或者5分钟成长记,不要多,我想超过你也会睡着了的.....

       最后,大家可以在阅读完源码后,在茶余饭后的时候问问同事或同学,你也可以分享下,讲给他听听。

HashMap不明白?来看看这篇文章吧!

       面试中常遇问题:简单谈谈HashMap。

       通过四个问题来深入探讨HashMap。

       1. HashMap是什么?

       2. HashMap的底层数据结构?

       3. HashMap1.7与1.8的区别?

       4. HashMap的扩容机制?

       HashMap是Java集合,用于存储键值对,非线程安全。

       上图展示简易的HashMap结构:存储Key和对应的Value。

       注意,HashMap中Key唯一,不允重复。

       允许存储Null的Key和Value,但Null作为键只能有一个。

       初始容量为2的次幂,设置为时,实际容量为。

       putVal()源码显示,通过(n-1)&hash定位元素位置。

       Hash冲突解决:链表+红黑树结构。

       1.8中,当链表节点超过8个时,转为红黑树。

       红黑树节点小于等于6个时,转回链表。

       扩容机制:1.7死循环问题,1.8采用尾插法解决。

       正常扩容情况:找到元素,记录next节点,链接至扩容数组。

       并发扩容问题:线程一记录元素,线程二完成扩容。

       线程一执行扩容,记录元素位置,继续执行线程一的扩容。

       此时形成死循环。

       1.8中使用尾插法,解决并发问题,但数据丢失。

       扩容考虑:容量和加载因子,默认容量为,加载因子为0.。

       数组大小小于,链表长度超过8,也会进行扩容。

       每次扩容扩大原数组的两倍。

       以上内容,希望对理解HashMap有所帮助。

【本文网址:http://04.net.cn/html/48e332696625.html 欢迎转载】

copyright © 2016 powered by 皮皮网   sitemap