二、HashMap底层原理

柔光的暖阳◎ 2022-09-12 10:50 247阅读 0赞

## 一、HashMap底层原理： ##

> **1. HaspMap的实现原理 以及 Hash碰撞**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAS2FyZW5fOTk5OQ_size_20_color_FFFFFF_t_70_g_se_x_16]  
**HaspMap的实现原理：** HashMap是 数组+链表+红黑树（JDK1.8增加了红黑树部分） 实现的，基于 Hash算法，通过 put(key,value)存储，get(key)来获取。当传入 key时，HashMap会根据 key.hashCode()计算出 hash值，根据 hash值将 value保存在 bucket里。当计算的 hash值相同时，我们称之为 Hash冲突（Hash碰撞），当发生 Hash碰撞 时，HashMap再用 equals()来比较 key是否相同：如果 hash相同， key也相同，value直接覆盖；如果 hash相同，key不同， HashMap的做法是用链表和红黑树存储相同 hash值的 value，当 hash冲突的个数比较少，先在相应的桶中形成一个链表结构，使用链表进行存储，否则使用红黑树。

**JDK1.8 引入红黑树：** 当拉链过长时，会严重影响 HashMap的性能，于是在 JDK1.8中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过 8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高 HashMap的性能。

**详细参考一：[源码分析—HashMap中链表和红黑树的转换阈值][HashMap]**

**Hash碰撞：** 对象（即 key）的 hashCode相同。发生 Hash碰撞即对象的 hashCode相同时，HashMap再用 equals()来比较 key是否相同：如果 hash相同， key也相同，value直接覆盖；如果 hash相同，key不同，HashMap的做法是用链表和红黑树存储相同 hash值的 value，当 hash冲突的个数比较少，先在相应的桶中形成一个链表结构，使用链表进行存储，否则使用红黑树。（因为 HashMap的 key唯一，如果添加相同的 key值，value会被覆盖）（HashMap很少用到 equals()，只有当发生哈希碰撞时才会执行）（key是由 hashCode和 equals两者来判断是否相同）。  
**map使用 keySet() 取键集合，values() 取值集合；使用 entrySet() 取全部映射，再getKey()\\getValue()；如下 eg：**

Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    for(Map.Entry<Integer,Integer>  entry：map.entrySet()){ 
       System.out.pringln(entry.getKey(),entry.getValue());
    }

若只需要 map中的键或值，通过 map.keySet()/map.values()：

Map<Integer,Integer> map=new HashMap<Integer,Integer>();
    for(Integer key：map.keySet()){ 
       System.out.pringln(key);
    }
    for(Integer value：map.values()){ 
       System.out.pringln(values);
    }

**【1】HashTable为什么是线程安全的？：** 因为 HashTable内部为所有的操作都加了同步锁（synchronized）；  
**【2】为什么加了 synchronized锁会导致效率降低？：** 因为 加了同步锁时其他线程再访问，必须等到前一个线程释放了锁才能使用；  
**【3】公司有些大数据量需要用到 HashTable，但又想保证执行效率怎么办？：** 用 ConcurrentHashMap；

--------------------

> **2. ConcurrentHashMap的实现原理**

**【1】ConcurrentHashMap的实现原理：** ConcurrentHashMap的内部实现进行了锁分离（或锁分段），将数据分段存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，比如 size()和 containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁，所以它的锁粒度小于同步的 HashMap；同时，ConcurrentHashMap的 get() 操作也是无锁的。除非读到的值是空的才会加锁重读，我们知道 HashTable容器的 get方法是需要加锁的，那么ConcurrentHashMap的 get操作是如何做到不加锁的呢？原因是它的 get方法里将要使用的共享变量都定义成 volatile。（在 HashMap的基础上，将数据分段存储，ConcurrentHashMap由多个 Segment组成，每个 Segment都有把锁（）Segment下包含很多 Node，也就是我们的键值对了））  
**【2】ConcurrentHashMap是如何保证线程安全的？：** 使用分段锁 segment；  
**【3】为什么使用分段锁比同步锁效率高？：** 分段锁就是把 map分成多个 segment去处理，进行 put操作时，根据 hashcode找到对应的锁，彼此间不受影响，所以效率高；而同步锁锁住的是整个 hashTable，所以效率低。

--------------------

> **3. 高并发下使用 ConcurrentHashMap**

**总结与思考：**  
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的**Segment+ReentrantLock+HashEntry**，到JDK1.8版本中**Synchronized+CAS+HashEntry+红黑树**,相对而言，总结如下思考：  
**1. JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）；**  
**2. JDK1.8版本的数据结构变得更加简单，** 使得操作也更加清晰流畅，**因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了**，由于粒度的降低，实现的复杂度也增加了；  
3. JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档；  
4. JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，我觉得有以下几点：**①因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了；** ②JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然；③在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据；

**【1】并发 Map：** 在多线程环境下使用Map，一般也可以使用 Collections.synchronizedMap()方法得到一个线程安全的 Map。但是在高并发的情况下，这个Map的性能表现不是最优的。由于 Map 是使用相当频繁的一个数据结构，因此 JDK 中便提供了一个专用于高并发的 Map 实现 ConcurrentHashMap。  
**【2】为什么不能在高并发下使用HashMap？**  
HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。  
**【3】ConcurrentHashMap的优势：**  
ConcurrentHashMap的内部实现进行了锁分离（或锁分段），将数据分段存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁，  
所以它的锁粒度小于同步的 HashMap；同时，ConcurrentHashMap的 get() 操作也是无锁的。除非读到的值是空的才会加锁重读，我们知道HashTable容器的get方法是需要加锁的，那么ConcurrentHashMap的get操作是如何做到不加锁的呢？原因是它的get方法里将要使用的共享变量都定义成 **volatile**。（在 HashMap的基础上，将数据分段存储，ConcurrentHashMap由多个 Segment组成，每个 Segment都有把锁（Segment下包含很多 Node，也就是我们的键值对了））  
**锁分离：** 首先将数据分段存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。  
**【4】volatile和 synchronized的区别：**  
① volatile本质是在告诉jvm当前变量在寄存器（工作内存）中的值是不确定的，需要从主存中读取； synchronized则是锁定当前变量，只有当前线程可以访问该变量，其他线程被阻塞住。（volatile关键字就是要告诉编译器，这个变量是经常改变的，而且编译时不要进行代码优化，所以每次读写的时候都要到它所在的地址去读取）  
② volatile仅能使用在变量级别；synchronized则可以使用在变量、方法、和类级别的（volatile是变量修饰符，synchronized是修饰类、方法、代码段）  
③ volatile不会造成线程的阻塞；synchronized可能会造成线程的阻塞。  
④ volatile标记的变量不会被编译器优化；synchronized标记的变量可以被编译器优化  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAS2FyZW5fOTk5OQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]

> **4. HashSet和TreeSet的区别？**

**参考一：[HashSet和TreeSet的区别][HashSet_TreeSet]  
参考二：[HashSet和TreeSet有什么区别][HashSet_TreeSet 1]**

## 二、删除List集合中的元素： ##

**参考一：[如何在循环中删除List集合中的元素][List]  
参考二：[Java中List 删除元素方法參考][Java_List]  
参考三：[java中List元素移除元素的那些坑][java_List]**

总结：不用参考一中的for循环、增强for循环，用 **迭代器删除或者lambda表达式直接删除**，如下：

public static void main(String[] args) { 
            List<String> list = new ArrayList<String>();
            list.add("a");
            list.add("a");
            list.add("b");
            list.add("c");
            System.out.println("删除前list的size："+ list.size());
            System.out.println("删除前list的所有元素："+list);
    
            /*法一：常用迭代器删除iterator Iterator<String> iterator = list.iterator(); while (iterator.hasNext()){ if (iterator.next().equals("a")) iterator.remove(); }*/
    
            //法二：jdk1.8的写法
            //list.removeIf(item -> "a".equals(item));
    
            System.out.println("删除后list的size："+ list.size());
            System.out.println("删除前list的所有元素："+list);
    
            //法三：jdk1.8的lambda表达式
            List<String> collect = list.stream().filter(s -> s != "a").collect(Collectors.toList());
            System.out.println("删除后list的size："+ collect.size());
            System.out.println("删除前list的所有元素："+collect);
        }

## 三、删除map集合中的元素：（同二用迭代器iterator） ##

**参考一：[删除map元素][map]**

public Map processMap(Map list) { 
       Map map = list;
       Iterator iterator = map.keyset().iterator;
       while(iterator.hasNext()) { 
           double key = iterator.next();
           if (key > 5) { 
               // map.remove(key); // java.util.ConcurrentModificationException
               iterator.remove(key);  // OK
           }
       }
       return map;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAS2FyZW5fOTk5OQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7c014597d8ea4e7799aa3344282da475.png
[HashMap]: https://blog.csdn.net/cg2258911936/article/details/103402684
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAS2FyZW5fOTk5OQ_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/eb6f3465b0284f96bdb10e41ef263709.png
[HashSet_TreeSet]: https://www.cnblogs.com/williamjie/p/11164123.html
[HashSet_TreeSet 1]: https://blog.csdn.net/xiangyuenacha/article/details/84255629
[List]: https://blog.csdn.net/qq_34198877/article/details/90699815
[Java_List]: https://blog.csdn.net/kang1011/article/details/108167930
[java_List]: https://blog.csdn.net/javageektech/article/details/96668890
[map]: https://blog.csdn.net/weixin_39667801/article/details/114815504