关于Map的知识整理

绝地灬酷狼 2022-01-26 02:17 219阅读 0赞

俗话说所有的上层建筑都是建立在基础之上的，所以今天给大家分享一下。

## Map家族 ##

Java为数据结构中的映射定义了一个接口**java.util.Map;它有四个实现类,分别是HashMap** **Hashtable** **LinkedHashMap** 和**TreeMap**.如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70] **Map**的主要特点是键值对的形式，一一对应，且一个**key**只对应1个**value**。  
**1、Map家族之一 ------ HashMap**  
使用位桶和链表实现（最近的jdk1.8改用红黑树存储而非链表），它是线程不安全的**Map**，方法上都没有**synchronize**关键字修饰，具体如下  
**①.JDK1.7**  
HashMap是Java中大家最常用的一个map实现类，其为键值对也就是key-value的形式。他的数据结构则是采用的位桶和链表相结合的形式完成了，即拉链法。具体如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 1] HashMap里面存储的是静态内部类Entry的对象，这个对象其实也是一个key-value的结构。以下是Entry的源码：

static class Entry<K,V> implements Map.Entry<K,V> {
            final K key;
            V value;
            /** 指向下一个元素的引用 */
            Entry<K,V> next;
            int hash;
    
            /**
             * 构造方法为Entry赋值
             */
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
            ...
            ...
     }

**②.HashMap的存取过程**

// 存储时:
    int hash = key.hashCode(); // 1个key对应一个固定的hash值
    int index = hash % Entry[].length;
    Entry[index] = value;
    
    // 取值时:
    int hash = key.hashCode();
    int index = hash % Entry[].length;
    
    return Entry[index];
    
        如果两个key通过int index = hash % Entry[].length得到了相同的index，就会跟在之间那个entry连接在后面，也就是按照顺序存储在后面的链表中，也就是解决hash冲突的拉链法。

**③.HashMap的get() 方法**  
由于可能会出现的**Hash**冲突，所以**Java**采用了链地址法来处理冲突，首先会通过**HashCode**来查到对应的Entry对象，如果找到了之后发现这个链表上链接了多个**Entry**对象，则再调用**equals**方法对value进行逐一比较。但是如果当链表过长后，**HashMap**就会自动将链表转化为**红黑树**，**以提高查找效率**。  
当链表数组的容量超过初始长度的**0.75**之后，**再散列就会将该链表再扩大2倍**，**创建一个新的2倍长的链表，然后再讲数据逐个搬迁复制到新链表中去。**  
**④.扩容时调用resize(）**  
其默认的大小是**16**，一旦>**0.75\*16**之后，就会调用**resize(）进行扩容，扩容非常耗时，所以如果需要保存较多的话，最好在创建一开始就制定好HashMap**的初始容量。

**②.JDK1.8**  
采用的是位桶数组，其底层采用红黑树。

transient Node<k,v>[] table;//存储（位桶）的数组</k,v>

默认的加载因子是**0.75**，如果不扩容，链表就会越来越长，查找起来因为**要逐一equals**进行比对，所以会慢很多。当然现在因为又**采用了红黑树**，相对来说比**JDK1.7**要好一些。扩容之后，会将原本的链表数组中的**每个链表分为奇偶两个**，**分别挂在新链表的数组下的对应的散列位置。减少查找时间，提高效率**。  
**①. jdk1.8的最大区别就在于底层的红黑树策略。**  
相对于JDK1.7，HashMap处理hash冲突时，会首先存放在链表中去，但是一旦链表中的数据较多(即>8个)之后，就会转用红黑树来进行存储，优化存储速度。O(lgn)。如果是链表。一定是O(n)。

**2、Map家族之一 -------- HashTable**  
**HashTable**是线程安全的一个map实现类，它实现线程安全的方法是在各个方法上添加了synchronize关键字。但是现在已经不再推荐使用**HashTable**了，因为现在有了**ConcurrentHashMap**这个专门用于多线程场景下的**Map**实现类，其大大优化了多线程下的性能。  
**3、Map家族之一 ------ ConcurrentHashMap**  
这个map实现类是在**JDK1.5**中加入的，其在**JDK1.6/1.7**中的主要实现原理是**segment段锁**，它不再使用和**HashTable**一样的**synchronize**一样的关键字对整个方法进行枷锁，而是转而**利用segment段落锁来对其进行加锁，以保证Map的多线程安全**。

*  一个ConcurrentHashMap是由多个HashTable组成，所以它允许获取不用段锁的线程同时持有该资源，segment有多少个，理论上就可以同时有多少个线程来持有它这个资源。  
    *其默认的segment是一个数组，默认长度为16。也就是说理论商可以提高16倍的性能。*  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 2]  
    在JAVA的***JDK1.8中则对ConcurrentHashMap又再次进行了大的修改\*\*\*，取消了segment段锁字段，采用了**CAS*\*+**Synchronize**技术来保障线程安全。**底层采用数组+链表+红黑树的存储结构**，也就是和HashMap一样。这里注意Node其实就是保存一个键值对的最基本的对象。其中Value和next都是使用的volatile关键字进行了修饰，以确保线程安全。  
    ![在这里插入图片描述][20190527213957855.png] 同hashMap一样，在JDK1.8中，如果链表中存储的Entry超过了8个则就会自动转换链表为红黑树，提高查询效率。  
    **4、Map家族之一 -------- TreeMap**  
    TreeMap也是一个很常用的map实现类，因为他具有一个很大的特点就是会对Key进行排序，使用了TreeMap存储键值对，再使用iterator进行输出时，会发现其默认采用key由小到大的顺序输出键值对，如果想要按照其他的方式来排序，需要重写也就是override 它的compartor接口。此处引用一下其他大神的代码：

import java.util.Comparator;
    import java.util.Iterator;
     import java.util.Set;
     import java.util.TreeMap;
     
     public class Compare {
    		 public static void main(String[] args) {
    		TreeMap<String,Integer> map = new TreeMap<String,Integer>(new xbComparator());
    		 map.put("key_1", 1);
    		 map.put("key_2", 2);
    		 map.put("key_3", 3);   
    		 Set<String> keys = map.keySet();
    		 Iterator<String> iter = keys.iterator();
    		 
    		 while(iter.hasNext()) {
    				 String key = iter.next();
    				 System.out.println(" "+key+":"+map.get(key));
    		    	  }
    		  	}
    		}
    		 class xbComparator implements Comparator {
    				 public int compare(Object o1,Object o2) {
    						 String i1=(String)o1;
    						 String i2=(String)o2;
    						return -i1.compareTo(i2);
    		 }
     }

另外，TreeMap底层的存储结构也是一颗红黑树。大笑是不是发现好多都是红黑树，没错因为红黑树查找效率高，只有O（lgn）。它是一种自平衡的二叉查找树。在每次插入和删除节点时，都可以自动调节树结构，以保证树的高度是lgn。  
**5、Map家族之一 --------- LinkedHashMap**  
LinkedHashMap它的特点主要在于linked，带有这个字眼的就表示底层用的是链表来进行的存储。相对于其他的无序的map实现类，还有像TreeMap这样的排序类，linkedHashMap最大的特点在于有序，但是它的有序主要体现在先进先出FIFIO上。没错，LinkedHashMap主要依靠双向链表和hash表来实现的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 3] 这里虽然在计算hashcode时还是发生了hash冲突，采用了链地址法解决了冲突，但是这里的Entry对象是采用双向链表保存的，每个Entry都有一个after和before的属性。当插入一个entry时，如果发生了冲突，就可以将新的Entry插入Entry链表中的头部，但是按照双向链表的角度来说，又会将该Entry插入到双向链表的尾部。

**6、weakHashMap**  
首先，weakHashMap它是一个“弱键”，它的Key值和Value都可以是null，而且其Map中如果这个Key值指向的对象没被使用，此时触发了GC，该对象就会被回收掉的。其原理主要是使用的WeakReference和ReferenceQueue实现的，其key就是weakReference，而ReferenceQueue中保存了被回收的 Key-Value。  
如果当其中一个Key-Value不再使用被回收时，就将其加入ReferenceQueue队列中。当下次再次调用该WeakHashMap时，就会去更新该map,比如ReferenceQueue中的key-value，将其中包含的key-value全部删除掉。这就是所谓的“自动删除”。

## 总结和思考 ##

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言，总结如下思考

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70]: /images/20220126/040d2b2abe8942bda5183ab6ee2a7f4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 1]: /images/20220126/0673b0231059447886ab12b3e1be53d2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 2]: /images/20220126/0930053e18e542c2a7f2bd90cc021bf3.png
[20190527213957855.png]: /images/20220126/1fcf395a9844481795aebcf5586b50c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MjE1NDc0_size_16_color_FFFFFF_t_70 3]: /images/20220126/2f0541b2ce7c4f2db83352a0d039e275.png