皮皮网

1.java面试精讲，对比Hashtable、HashMap、TreeMap有什么不同？
2.结合源码探究HashMap初始化容量问题
3.HashMap为什么不安全？

java面试精讲，对比Hashtable、HashMap、网上陵园源码TreeMap有什么不同？

       面试中经常被问及的Java核心数据结构问题之一是对比Hashtable、HashMap和TreeMap的区别。这三种Map类型在Java集合框架中扮演着重要角色，尤其是HashMap，因其广泛使用而备受关注。

       Hashtable是早期Java提供的哈希表实现，同步但不支持null键值对，imac android 源码其同步特性导致性能较低，现今已较少推荐。HashMap相比之下，更受欢迎，是非同步的，支持null键值对，其put和get操作通常能达到常数时间，是键值对存储和访问的首选，比如用户ID与信息的关联。

       TreeMap则是基于红黑树的有序Map，get、put、天网搜索源码remove操作的时间复杂度为O(log(n))，顺序由Comparator或键的自然顺序决定。这对于需要保持特定顺序的场景，如资源池的自动释放策略，是有用的。

       面试时，可能会询问HashMap的设计实现细节，如并发问题、容量和负载因子的影响，以及HashMap和LinkedHashMap的区别，比如插入顺序和访问顺序。HashMap的网页病毒源码底层是数组和链表结构，容量和负载因子决定了性能，当链表过长时，会进行树化以提高查询效率。

       理解Map的整体结构，以及hashCode和equals的使用规则至关重要，比如LinkedHashMap的遍历顺序和TreeMap的键值顺序依赖于Comparator。同时，了解HashMap源码，包括resize、树化和容量调整等，是面试中不可忽视的部分。

       总结来说，dr指标源码面试中会考察你对这些Map类型特性的掌握，以及在实际编程中的应用和理解，确保你能够正确处理并发场景，并根据需求选择合适的Map实现。

结合源码探究HashMap初始化容量问题

       探究HashMap初始化容量问题

       在深入研究HashMap源码时，有一个问题引人深思：为何在知道需要存储n个键值对时，我们通常会选择初始化容量为capacity = n / 0. + 1？

       本文旨在解答这一疑惑，适合具备一定HashMap基础知识的读者。请在阅读前，思考以下问题：

       让我们通过解答这些问题，逐步展开对HashMap初始化容量的深入探讨。

       源码探究

       让我们从实际代码出发，通过debug逐步解析HashMap的初始化逻辑。

       举例：初始化一个容量为9的HashMap。

       执行代码后，我们发现初始化容量为，且阈值threshold设置为。

       解析

       通过debug，我们首先关注到构造方法中的初始化逻辑。注意到，初始化阈值时，实际调用的是`tabliSizeFor(int n)`方法，它返回第一个大于等于n的2的幂。例如，`tabliSizeFor(9)`返回，`tabliSizeFor()`返回，`tabliSizeFor(8)`返回8。

       继续解析

       在构造方法结束后，我们通过debug继续追踪至`put`方法，直至`putVal`方法。

       在`putVal`方法中，我们发现当第一次调用`put`时，table为null，从而触发初始化逻辑。在初始化过程中，关键在于`resize()`方法中对新容量`newCap`的初始化，即等于构造方法中设置的阈值`threshold`()。

       阈值更新

       在初始化后，我们进一步关注`updateNewThr`的代码逻辑，发现新的阈值被更新为新容量乘以负载因子，即 * 0.。

       案例分析

       举例：初始化一个容量为8的HashMap。

       解答：答案是8，因为`tableSizeFor`方法返回大于等于参数的2的幂，而非严格大于。

       扩容问题

       举例：当初始化容量为时，放入9个不同的entry是否会引发扩容。

       解答：不会，因为扩容条件与阈值有关，当map中存储的键值对数量大于阈值时才触发扩容。根据第一问，初始化容量是，阈值为 * 0. = 9，我们只放了9个，因此不会引起扩容。

       容量选择

       举例：已知需要存储个键值对，如何选择合适的初始化容量。

       解答：初始化容量的目的是减少扩容次数以提高效率并节省空间。选择容量时，应考虑既能防止频繁扩容又能充分利用空间。具体选择取决于实际需求和预期键值对的数量。

       总结

       通过本文的探讨，我们深入了解了HashMap初始化容量背后的逻辑和原因。希望这些解析能够帮助您更深入地理解HashMap的内部工作原理。如果您对此有任何疑问或不同的见解，欢迎在评论区讨论。

       最后，如有帮助，欢迎点赞分享。

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线程不安全体现在：数据覆盖