关于对Java集合类的一些总结（三）

傷城~ 2022-11-29 05:56 95阅读 0赞

## Map接口下的实现类主要有HashMap、HashTable、ConcurrentHashMap、TreeMap ##

### 一、HashMap ###

底层数据结构是数组+链表/红黑树，HashMap的主干是Node数组(JDK1.8之前是Entry)，**数组是HashMap的主体，链表是为了解决哈希冲突的。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center]

transient Node<K,V>[] table;

Node是HashMap的一个静态内部类，Node节点中包括key的hash值、key和value值，链表中指向下一个Node节点的指针。

static class Node<K,V> implements Map.Entry<K,V> { 
    	final int hash;
    	final K key;
    	V value;
    	Node<K,V> next;

其他的一些参数：

//hashmap中实际的元素个数
    transient int size;
    
    //负载因子，默认为0.75，即当元素个数占总容量的75%时就触发扩容机制
    final float loadFactor;
    
    //loadFactor*capacity
    int threshold;
    
    //抛出ConcurrentModificationException异常
    transient int modCount;

指定容量和负载因子的构造器：

public HashMap(int initialCapacity, float loadFactor) { 
    		//当指定大小小于0抛出异常
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            //当指定负载因子小于0抛出异常
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }

我们发现，在初始化hashmap时并没有为table分配空间，其实`创建table[]数组是在put操作时发生的。`

public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }
    ...
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
                
    ...
    final Node<K,V>[] resize() { 
    	//声明新的容量和阈值为0
    	int newCap, newThr = 0;
    	else {  
    	    //容量=16
    	    newCap = DEFAULT_INITIAL_CAPACITY;
    	    //阈值=16*0.75
    	    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
             }
     
        threshold = newThr;
        //创建一个大小为16的Node数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //table指向大小为16的数组
        table = newTab;

通过`put()`、`putVal()`、`resize()`三个方法之后才成功创建出`table[]`数组。

**HashMap的存储方式：**

HashMap通过Key的`hash值`计算出存储在数组中的位置，如果当前位置没有元素，则添加成功，如果有，则比较二者的`hashcode`,不同则以链表的形式添加成功，相同则调用`equals()`，如果不同，则以链表的形式添加，相同则覆盖之前的元素。

当数组中添加的元素达到阈值需要扩容时，会创建一个大小是原来2倍的数组，将原来的元素重新计算存放位置，并重新插入，因此扩容是一个比较耗费资源的操作。

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
    ...
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

***当table数组长度大于64且链表中的长度大于8时，就转换为红黑树进行存储，提高了查询速度(链表为O(n)，红黑树为O(logn))***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 二、HashTable ###

HashTable底层数据结构是数组+链表，也是key-value键值对，线程安全，这里主要说一下HashTable和HashMap的区别：  
1、`继承类不同`：HashMap继承自AbstractMap类，HashTable继承自Dictionary类，但二者都实现了Map接口  
2、`线程安全`：HashTable线程安全。它的一些方法经过Synchronized修饰  
3、`扩容方式`：扩容方式不同，HashTable默认初始大小为11，达到阈值0.75时扩容为原来的2n+1。HashTable初始化时如果给定大小，会直接使用给定的值，HashMap会将其扩充为2的幂次方大小  
4、`存储null值`：HashMap中key、value可以 存放null值，HashTable不可以，会报空指针异常  
5、`数据结构`:JDK1.8之后，HashMap在某种情况下会将链表转换为红黑树存储。

### 三、ConcurrentHashMap ###

ConcurrentHashMap也是用来存储键值对的，线程安全，这里主要说一下它与HashTable的区别  
**底层数据结构**：ConcurrentHashMapJDK1.7及以前采用`分段数组`\+`链表`的形式，JDK1.8及以后采用和HashMap一样的`数组`\+`链表/红黑树`.

**线程安全的实现**：ConcurrentHashMap在JDK1.7及以前采用对整个桶数据进行分段分割(`Sgment`)，每把锁只锁容器中的一部分数据，多线程访问不同数据段的数据时，不存在锁竞争，提高了并发量。ConcurrentHashMap由`Segment数组`和`HashEntry数组`组成，Segment是一个可重入锁，继承于`ReentrantLock`，一个Segment就是一把锁，里面包含了一个HashEntry数组，一个HashEntry是一个`链表`结构的元素。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center 2]

JDK1.8及以后采用`CAS+Synchronized`形式控制并发访问，在更新时会锁住要更新的数组中的那个节点数据，不会锁全表，同步读取操作则是完全非阻塞的。HashTable则采用Synchronized`全表锁`控制并发访问，当一个线程对一个同步方法进行put操作时，另一个线程不可以对这个同步方法进行get操作，进入阻塞状态，效率非常低下。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/0e4f01dc569a4867a3d8361d2e95ac7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/46fb33d1bce841128b6ba33d3ccd3032.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/f1a5e1c03f0142a39625bd21a9a25a6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk3Mzk2MQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/a58e0484170c422f9aaeff909d8a8854.png