有关Java的HashMap的各种问题都在这里

傷城~ 2022-11-29 05:53 166阅读 0赞

### 文章目录 ###

*   *   *  1. HashMap是怎么get元素的?
         *  2. HashMap是怎么put元素的？
         *  3. HashMap的底层实现
         *  4. HashMap多线程操作导致的死循环问题
         *  5. HashMap 的⻓度为什么是2的幂次⽅？
         *  6.HashMap的key可以是任何对象吗？
         *  7. 为什么HashMap采用使用数组+链表的形式？
         *  8. 我⽤LinkedList代替数组结构可以吗？
         *  9. HashMap的扩容机制
         *  10. HashMap与HashTable的区别？
         *  11. HashMap与HashSet的区别

### 1. HashMap是怎么get元素的? ###

（1）首先计算key的hashCode，通过hashCode找到数组中的某一个元素  
（2）然后通过key的equals方法在对应位置的链表中找到key对应的value

### 2. HashMap是怎么put元素的？ ###

（1）先根据key的hash值得到这个元素在数组中的位置（即下标），然后就可以把这个元素放到对应的位置中了。  
（2）如果这个元素所在的位置上已经有了其他的元素，那么同一个位置上的元素将以链表的形式进行存放，这里采用的是头插的形式（具体原因是认为后边加入的元素使用的次数较多）。  
（3）如果计算的哈希位置有值，且key一样，则会覆盖原有的值value，并返回原值value。

### 3. HashMap的底层实现 ###

*  详细介绍：[传送门][Link 1]
 *  JDK1.8之前  
    （1）**JDK1.8之前HashMap底层是数组和链表结合在一起使用，也就是链表散列。HashMap通过key的hashCode经过扰动函数处理后得到hash值，然后通过（n-1）&hash判断当前元素存放的位置（这里的n指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同的话就通过拉链发解决冲突。**  
    （2）扰动函数值的是HashMap的hash方法，使用hash方法也就是扰动函数为了防止一些实现比较差的hashCode()方法，换句话说使用扰动函数之后可以减少哈希碰撞。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]  
    相比JDK1.8的hash方法，JDK1.7的hash方法的性能会稍差一点，因为毕竟扰动了4次。  
    （3）“拉链法”指的是：将链表和数组相结合，也就是创建一个链表数组，数组中的每一格就是一个链表，若遇到hash冲突，则将冲突的值加入到链表中。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]
 *  JDK1.8之后  
    （1）**相较于之前的版本，JDK1.8之后在解决hash冲突时有了较大的变化，当链表的长度大于阈值（默认为8）且总的数据量大于64的时候，将链表转化为红黑树，以减少搜索的时间。**  
    TreeMap、TreeSet以及JDK1.8之后的HashMap底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉查找树的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结构。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 3]

### 4. HashMap多线程操作导致的死循环问题 ###

*  更多详细介绍：[传送门][Link 2]
 *  **主要的原因在于并发下的Rehash会造成元素之间会形成一个循环列表**。不过在JDK1.8后解决了这个问题，但是还是不建议在多线程下使用HashMap，因为多线程下使用HashMap还存在其他的问题，比如数据丢失等等，**并发环境下推荐使用ConcurrentHashMap。**

### 5. HashMap 的⻓度为什么是2的幂次⽅？ ###

*  为了能让 HashMap 存取⾼效，尽量减少碰撞，也就是要尽量把数据分配均匀。我们上⾯也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得⽐较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。（n代表数组⻓度）。这也就解释了 HashMap 的⻓度为什么是2的幂次⽅。
 *  这个算法应该如何设计呢？  
    我们⾸先可能会想到采⽤%取余的操作来实现。但是，重点来了：**“取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作（也就是说 hash%lengthdehash&(length-1)的提是 length 是2的n 次⽅；）。” 并且采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓度为什么是2的幂次⽅。**
 *  这里我们也就得知为什么Table数组的长度要一直都为2的n次方，只有这样，减一进行相与时候，才能够达到最大的n-1值。

更多参考此链接 [传送门][Link 3]

### 6.HashMap的key可以是任何对象吗？ ###

*  HashMap的key可以是任何类型的对象，但是在存储对象的时候，相应的我们也要重写它的hashCode方法和equals方法，在改写equals方法的时候需要满足一下三点：  
    (1) 自反性：就是说a.equals(a)必须为true。  
    (2) 对称性：就是说a.equals(b)=true的话，b.equals(a)也必须为true。  
    (3) 传递性：就是说a.equals(b)=true，并且b.equals（c）=true的话，a.equals（c）也必须为true。

### 7. 为什么HashMap采用使用数组+链表的形式？ ###

答：因为我们的数组的值是限制死的，我们在对key值进行散列取到下标以后，放入到数组中时，难免出现两个key值不同，但是却放入到下标相同的格子中，此时我们就可以使用链表来对其进行链式的存放。

### 8. 我⽤LinkedList代替数组结构可以吗？ ###

Entry[] table=new Entry[capacity];
    // entry就是一个链表的节点
    //现在进行替换，进行如下的实现
    List<Entry> table=new LinkedList<Entry>();

是否可以行得通？ 答案当然是肯定的。  
**那既然可以使用进行替换处理，为什么有偏偏使用到数组呢？**

*  因为⽤数组效率最⾼！ 在HashMap中，定位节点的位置是利⽤元素的key的哈希值对数组⻓度取模得到。此时，我们已得到节点的位置。显然数组的查 找效率⽐LinkedList⼤（底层是链表结构）。

**那ArrayList，底层也是数组，查找也快啊，为啥不⽤ArrayList?**

*  因为采⽤基本数组结构，扩容机制可以⾃⼰定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率⾼。 ⽽ArrayList的扩容机制是1.5倍扩容。

### 9. HashMap的扩容机制 ###

内容过多，我们新开辟一片文章进行讲解：[传送门][Link 4]

### 10. HashMap与HashTable的区别？ ###

*  线程是否安全：HashMap线程不安全，HashTable线程安全，如果想保证线程安全的话就使用ConcurrentHashMap。这里为什么不推荐用HashTable呢？  
    （1）具体保证线程安全的方式，包括有从简单的 synchronize 方式，比如HashTable；到基于更加精细化的，比如基于分离锁实现的 ConcurrentHashMap。  
    （2）Hashtable 本身比较低效，因为它的实现基本就是将 put、get、size 等各种方法加上“synchronized”。简单来说，这就导致了所有并发操作都要竞争同一把锁，一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操作的效率。  
    （3）ConcurrentHashMap在JDK1.8之后使用的是锁分离思想，只是锁住的是一个node，而锁住Node之前的操作是基于在volatile和CAS之上无锁并且线程安全的。  
    数据存储利用 volatile 来保证可见性。  
    使用 CAS 等操作，在特定场景进行无锁并发操作。  
    使用 Unsafe、LongAdder 之类底层手段，进行极端情况的优化。
 *  效率：因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被淘汰，不要在代码中使⽤它；
 *  对Null key和对Null value的支持：HashMap中，null可以作为键，但是只能有一个，可以一个或有多个键对应的值为null；但是在HashTable中是不允许有键为空的，会抛出空指针异常。
 *  初始容量大小和每次扩充容量大小的不同：  
    （1）HashTable默认的初始大小是11，之后的每次扩充，容量会变为原来的2n+1；HashMap默认的大小是16，之后的每次扩充，容量会变为原来的2倍。  
    （2）创建时的不同：创建时如果给定了初始值，那么HashTable会直接使用你给定的大小；但是HashMap会将其扩充为2的幂次方大小（下个问题告诉你），有他的tableSizeFor()方法进行保证。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 4]
 *  底层的数据机构：JDK1.8以后的HashMap在解决哈希冲突有了较大的变化，当链表的长度大于阈值（默认为8）时，会将链表转化为红黑树，以减少搜索时间；HashTable没有这样的机制。

### 11. HashMap与HashSet的区别 ###

*  HashSet底层是基于HashMap实现的，除了clone(),writeObject(),readObject()是HashSet自己实现的，其他的都是直接调用HashMap的方法。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 5]

[Link 1]: https://zhuanlan.zhihu.com/p/21673805
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: /images/20221124/757219fe8d8c427982f60b8d3de4cc55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]: /images/20221124/1d39893eb73c41ac8d32c136f4ae4ade.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]: /images/20221124/57ba8ab341b246d89c66ae6b67198db8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 3]: /images/20221124/89f3a22af36843f7abecd981ea2e8fa4.png
[Link 2]: https://coolshell.cn/articles/9606.html
[Link 3]: https://blog.csdn.net/MaxwellOcean/article/details/107435082
[Link 4]: https://blog.csdn.net/qq_44840148/article/details/108103786
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 4]: /images/20221124/02dbf02794b94272ba670f0ff0e5b1ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 5]: /images/20221124/53d0b6aedfdd40628cb520243d7bf005.png