一文学会Set与Map以及集合类的使用选取，HashMap底层源码解析

柔光的暖阳◎ 2024-04-07 14:57 54阅读 0赞

#### 1. Set接口 ####

##### 1.1 Set接口基本介绍 #####

1.  无序性（添加和取出的顺序不一致），没有索引。
2.  不允许重复元素，所以最多包含一个null。

##### 1.2 Set接口的常用方法 #####

和 List 接口一样, Set 接口也是 Collection 的子接口，因此，常用方法和 Collection 接口一样

##### 1.3 Set接口的遍历方式 #####

同Collection的遍历方式一样，因为Set接口是Collection接口的子接口，其遍历方式类似

1.  可以使用迭代器。
2.  增强for。
3.  **不能使用索引的方式来获取。**

##### 1.4 Set接口的常用方法演示 #####

Set set = new HashSet();
    set.add("john");
    set.add("lucy");
    set.add("john");//重复
    set.add("jack");
    set.add("tom");
    set.add("mary");
    set.add(null);//
    set.add(null);//再次添加 null

#### 2. HashSet ####

##### 2.1 HashSet特点 #####

1.  HashSet实现了Set接口
2.  HashSet实际上还是HashMap
3.  可以存放null值，但是只能有一个null
4.  HashSet不保证元素是有序的，取决与hash后，在确定索引的结果。（即不保证存放元素的顺序和取出顺序一致）
5.  不能有重复元素/对象，其实现了Set接口

> 为什么说HashSet实际上还是HashMap

![在这里插入图片描述][415a73b587314594a959fbd7ebb41e82.png]

##### 2.2 HashSet常用方法 #####

1、add(Object obj)：向Set集合中添加元素，添加成功返回true，否则返回false。

2、size()：返回Set集合中的元素个数。

3、remove(Object obj)： 删除Set集合中的元素，删除成功返回true，否则返回false。

4、isEmpty()：如果Set不包含元素，则返回 true ，否则返回false。

5、clear()： 移除此Set中的所有元素。

6、iterator()：返回在此Set中的元素上进行迭代的迭代器。

7、contains(Object o)：如果Set包含指定的元素，则返回 true，否则返回false。

HashSet hashSet = new HashSet();
    hashSet.add("java");//到此位置，第 1 次 add 分析完毕. hashSet.add("php");//到此位置，第 2 次 add 分析完毕
    hashSet.add("java");
    System.out.println("set=" + hashSet);

##### 2.3 HashSet扩容机制解密 #####

1.  HashSet的底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是16\*加载因子。
2.  如果table数组数组使用到了临界值 12，就会扩容到16\*2 = 32，新的临界值就是32 \* 0.75=24，依次类推
3.  在Java8中，如果一条链表的元素个数到达TREEIFY\_THRESHOLD（默认是8）并且table的大小>=MIN\_TREEIFY\_CAPACITY(默认64)，就会进行树化（红黑树），否则仍然采用数组扩容机制。

##### 2.4 HashSet源码解读 #####

> LinkedHashSet实现的底层就是HashSet，直接看LinkedHashSet的就可以，我们这里先看一下最关键的扩容机制

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
         //table 就是 HashMap 的一个数组，类型是 Node[]
    	//if 语句表示如果当前 table 是 null, 或者 大小=0
    	//就是第一次扩容，到 16 个空间
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
     //(1)根据 key，得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置
     //并把这个位置的对象，赋给 p
     //(2)判断 p 是否为 null
     //(2.1) 如果 p 为 null, 表示还没有存放元素, 就创建一个 Node 			(key="java",value=PRESENT)
     //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
     
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
        
            Node<K,V> e; K k;
            //如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash 值一样
    		//并且满足 下面两个条件之一:
    		//(1) 准备加入的 key 和 p 指向的 Node 结点的 key 是同一个对象
    		//(2) p 指向的 Node 结点的 key 的 equals() 和准备加入的 key 比较后相同
    		//就不能加入
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //再判断 p 是不是一颗红黑树, 
            //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        
                //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
    			// 注意在把元素添加到链表后，立即判断 该链表是否已经达到 8 个结点
    			// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
    			// 注意，在转成红黑树时，要进行判断, 判断条件
    			// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
    			// resize();
    			// 如果上面条件成立，先 table 扩容. // 只有上面条件不成立时，才进行转成红黑树
    			//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接 break
                for (int binCount = 0; ; ++binCount) {
        
                    if ((e = p.next) == null) {
        
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) {
         // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

#### 3. LinkedHashSet ####

##### 3.1 LinkedHashSet的特点 #####

1.  LinkedHashSet是HashSet的子类。
2.  LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表
3.  LinkedHashSet 根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
4.  LinkedHashSet 不允许添加重复元素。

##### 3.2 LinkedHashSet底层讲解 #####

1.  在LinkedHashSet中维护了一个hash表和双向链表。（LinkedHashSet有head和tail）
2.  在每一个节点有before 和 after 属性，这样可以形成双向链表。
3.  在添加一个元素时，先求hash值，再求索引，确定该元素再table的位置，然后将添加的元素加入到双向链表（如果已经存在，不添加\[原则和hashset一样\]）。
    
    tail.next = newElement  
    newElement.pre = tail  
    tail = newElement

##### 3.3 LinkedHashSet 源码解读 #####

> LinkedHashSet底层是一个LinkedHashMap，这点由构造器就可以看出

![在这里插入图片描述][466f93cc9e604107a4ddd284287a728d.png]

> 其add方法的本质是map的put方法

![在这里插入图片描述][39e7199160b74c1ea3f56fb4f5bf87e9.png]

> 以键值对方式进行存储

![在这里插入图片描述][0818d6fbfbcb4300809d13b1c0085a9a.png]

> 其hash值具体算法

h = key.hashCode()) ^ (h >>> 16)

> 其存储方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
         //table 就是 HashMap 的一个数组，类型是 Node[]
    	//if 语句表示如果当前 table 是 null, 或者 大小=0
    	//就是第一次扩容，到 16 个空间
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
         
         //(1)根据 key，得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置
    	 //并把这个位置的对象，赋给 p
    	 //(2)判断 p 是否为 null
    	 //(2.1) 如果 p 为 null, 表示还没有存放元素, 就创建一个 Node 			(key="java",value=PRESENT)
    	 //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
         
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
        
                Node<K,V> e; K k;
                //如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash 值一样
    			//并且满足 下面两个条件之一:
    			//(1) 准备加入的 key 和 p 指向的 Node 结点的 key 是同一个对象
    			//(2) p 指向的 Node 结点的 key 的 equals() 和准备加入的 key 比较后相同
    			//就不能加入
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //再判断 p 是不是一颗红黑树, 
                //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                    //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
    				// 注意在把元素添加到链表后，立即判断 该链表是否已经达到 8 个结点
    				// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
    				// 注意，在转成红黑树时，要进行判断, 判断条件
    				// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
    				// resize();
    				// 如果上面条件成立，先 table 扩容. // 只有上面条件不成立时，才进行转成红黑树
    				//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接 break
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

#### 4. Map接口 ####

##### 4.1 Map接口实现类的特点 #####

1.  Map与Collection并列存在，用于保存具有映射关系的数据：key-value。
2.  Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中。
3.  Map中的key不允许重复，原因的HashSet一样。
4.  Map中的value可以重复。
5.  Map的key 可以为 null，value也可以为 null，注意，key为null，只能有一个，value 为null，可以多个。
6.  常用String类作为Map的key
7.  key 和 value 之间存在单向一对一关系，即通过指定的key总能找到对应的value。
8.  Map存放数据的每一对k-v是放在HashMap$Node中的，又因为Node实现了Entry即接口，也存在一对k-v就是一个Entry的说法。

##### 4.2 Map接口常用方法（以HashMap演示） #####

**常见创建赋值**

Map map = new HashMap();
    map.put("no1", "周芷若");//k-v
    map.put("no2", "张无忌");//k-v
    map.put("no1", "张三丰");//当有相同的 k , 就等价于替换.
    map.put("no3", "张三丰");//k-v
    map.put(null, null); //k-v
    map.put(null, "abc"); //等价替换
    map.put("no4", null); //k-v
    map.put("no5", null); //k-v
    map.put(1, "赵敏");//k-v
    map.put(new Object(), "金毛狮王");//k-v
    // 通过 get 方法，传入 key ,会返回对应的 value
    System.out.println(map.get("no2"));//张无忌

**CRUD等常用方法**

Map map = new HashMap();
    map.put("邓超", new Book("一本书", 100));//OK
    map.put("邓超", "孙俪");//替换-> 一会分析源码
    map.put("黄晓明", "郑凯");//OK
    map.put("李晨", "郑凯");//OK
    map.put("陈赫", null);//OK
    map.put(null, "刘亦菲");//OK
    map.put("鹿晗", "关晓彤");//OK
    // remove:根据键删除映射关系
    map.remove(null);
    System.out.println("map=" + map);
    // get：根据键获取值
    Object val = map.get("李晨");
    System.out.println("val=" + val);//郑凯
    // size:获取元素个数
    System.out.println("k-v=" + map.size());
    // isEmpty:判断个数是否为 0
    System.out.println(map.isEmpty());//F
    // clear:清除 k-v
    //map.clear();
    System.out.println("map=" + map);
    // containsKey:查找键是否存在
    System.out.println("结果=" + map.containsKey("鹿晗"));//T

##### 4.3 Map接口遍历 #####

Map map = new HashMap();
    map.put("邓超", "孙俪");//
    map.put("黄晓明", "郑凯");//OK
    map.put("李晨", "郑凯");//OK
    map.put("陈赫", null);//OK
    map.put(null, "刘亦菲");//OK
    map.put("鹿晗", "关晓彤");//OK

**第一组: 先取出 所有的 Key , 通过 Key 取出对应的 Value**

> Set keyset = map.keySet();//取出所有的key

###### 增强for ######

System.out.println("-----第一种方式-------");
    for (Object key : keyset) {
        
    System.out.println(key + "-" + map.get(key));
    }

###### 迭代器 ######

System.out.println("----第二种方式--------");
    Iterator iterator = keyset.iterator();
    while (iterator.hasNext()) {
        
    Object key = iterator.next();
    System.out.println(key + "-" + map.get(key));
    }

**第二组: 把所有的 values 取出**

> Collection values = map.values();//取出所有value

###### 增强for ######

System.out.println("---取出所有的 value 增强 for----");
    for (Object value : values) {
        
    System.out.println(value);
    }

###### 迭代器 ######

System.out.println("---取出所有的 value 迭代器----");
    Iterator iterator2 = values.iterator();
    while (iterator2.hasNext()) {
        
    Object value = iterator2.next();
        System.out.println(value);
    }

**第三组: 通过 EntrySet 来获取 k-v**

> Set entrySet = map.entrySet();// EntrySet，获取所有的entry

###### 增强 for ######

System.out.println("----使用 EntrySet 的 for 增强(第 3 种)----");
    for (Object entry : entrySet) {
        
    	//将 entry 转成 Map.Entry
    	Map.Entry m = (Map.Entry) entry;
    	System.out.println(m.getKey() + "-" + m.getValue());
    }

###### 迭代器 ######

System.out.println("----使用 EntrySet 的 迭代器(第 4 种)----");
    Iterator iterator3 = entrySet.iterator();
    while (iterator3.hasNext()) {
        
    	Object entry = iterator3.next();
    	//System.out.println(next.getClass());//HashMap$Node -实现-> Map.Entry (getKey,getValue)
    	//向下转型 Map.Entry
    	Map.Entry m = (Map.Entry) entry;
    	System.out.println(m.getKey() + "-" + m.getValue());
    }

#### 5. HashMap ####

##### 5.1 HashMap特点 #####

1.  Map接口的常用实现类：HashMap，Hashtable和Properties。其中HashMap的使用频率最高
2.  HashMap是以key-val对的方式来存储数据（HashMap$Node类型）。
3.  key不能重复，但是值可以重复，允许使用null键和null值。
4.  如果添加相同的key，则会覆盖原来的key-val，等同与修改（key不会改变，但value会替换，保留最后一次的值）。
5.  与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的。
6.  HashMap没有实现同步，因此线程是不安全的，方法没有做同步互斥的操作，没有synchronized。

> HashMap存储结构示意图

![在这里插入图片描述][e3ecfcfbbd554a4ab1d76a85bba7bfea.png]

##### 5.2 HashMap底层机制 #####

> HashMap的扩容机制和HashSet相同，不再讲解。

> 以键值对的形式存储数据

![在这里插入图片描述][410a3fa770f74e129184b6639efa2f37.png]

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
         //table 就是 HashMap 的一个数组，类型是 Node[]
    	//if 语句表示如果当前 table 是 null, 或者 大小=0
    	//就是第一次扩容，到 16 个空间
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
         
         //(1)根据 key，得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置
    	 //并把这个位置的对象，赋给 p
    	 //(2)判断 p 是否为 null
    	 //(2.1) 如果 p 为 null, 表示还没有存放元素, 就创建一个 Node 			(key="java",value=PRESENT)
    	 //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)
         
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
        
                Node<K,V> e; K k;
                //如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash 值一样
    			//并且满足 下面两个条件之一:
    			//(1) 准备加入的 key 和 p 指向的 Node 结点的 key 是同一个对象
    			//(2) p 指向的 Node 结点的 key 的 equals() 和准备加入的 key 比较后相同
    			//就不能加入
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //再判断 p 是不是一颗红黑树, 
                //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                    //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
    				// 注意在把元素添加到链表后，立即判断 该链表是否已经达到 8 个结点
    				// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
    				// 注意，在转成红黑树时，要进行判断, 判断条件
    				// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
    				// resize();
    				// 如果上面条件成立，先 table 扩容. // 只有上面条件不成立时，才进行转成红黑树
    				//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接 break
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

#### 6. HashTable ####

##### 6.1 HashTable特点介绍 #####

1.  存放的元素是键值对：即k-v。
2.  HashTable的键和值都不能为null，否则会抛出空指针异常。
3.  HashTable的使用方法基本上和HashMap一样。
4.  HashTable是线程安全的（synchronized），而HashMap是线程不安全的。

##### 6.2 HashTable使用举例 #####

Hashtable hashtable = new Hashtable();
            hashtable.put("john",100);//ok
            hashtable.put(null,100);//异常
            hashtable.put("john",null);//异常
            hashtable.put("lucy",100);//ok
            hashtable.put("lic",100);//ok
            hashtable.put("lic",99);//替换

#### 7. Properties ####

##### 7.1 Properties特点 #####

1.  Properties类继承自HashTable类并实现了Map接口，也是使用一种键值对的形式来保存数据。
2.  其使用特点和HashTable类似。
3.  Properties 还可以用于从properties文件中加载数据到Properties类对象，并进行读取和修改。（与io流有关，有兴趣可以了解一下）。

##### 7.2 Properties基本使用 #####

Properties properties = new Properties();
    //properties.put(null, "abc");//抛出 空指针异常
    //properties.put("abc", null); //抛出 空指针异常
    properties.put("john", 100);//k-v
    properties.put("lucy", 100);
    properties.put("lic", 100);
    properties.put("lic", 88);//如果有相同的 key ， value 被替换
    //通过 k 获取对应值
    System.out.println(properties.get("lic"));//88
    //删除
    properties.remove("lic");
    System.out.println("properties=" + properties);
    //修改
    properties.put("john", "约翰");
    System.out.println("properties=" + properties);

#### 8. 集合实现类使用的选择 ####

在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下：

1.  先判断存储的类型（一组对象）【单列】或者一组键值对（双列）。
2.  一组对象：Colleaction接口
    
    允许重复：List
    
    增删多：LinkedList（底层维护了一个双向链表）
    
    改查多：ArrayList（底层维护Object类型的可变数组）
    
    不允许重复： Set
    
    无序：HashSet（底层是HashMap，维护了一个哈希表）
    
    排序：TreeSet
    
    插入和取出顺序一致：LinkedHashSet，维护数组+双向链表。
3.  一组键值对：Map
    
    键无序：HashMap
    
    键排序： TreeSet
    
    键插入和取出顺序一致：LinkedHashMap
    
    读取文件：Properties

#### 9. 结语 ####

> 集合类在Java开发中十分常用，在写算法题时也是经常使用，如HashMap，对于部分题型有意想不到的效果，其底层也十分复杂，强烈建议自己进行Debug，搞清楚到底是怎么实现的。

[415a73b587314594a959fbd7ebb41e82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/79c358c4d9094517907df0447ce2cbb1.png
[466f93cc9e604107a4ddd284287a728d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/081c46a9b7b44a3281ccfb36529c88ae.png
[39e7199160b74c1ea3f56fb4f5bf87e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/347d30e4b3154b2aa1ca00afc3e56a7d.png
[0818d6fbfbcb4300809d13b1c0085a9a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4ead5af8909b4431a3d3bbb24a05051d.png
[e3ecfcfbbd554a4ab1d76a85bba7bfea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f861d0e5369f4c3799a46f62d0cee8da.png
[410a3fa770f74e129184b6639efa2f37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/0634c259c1d649d1935fca0802892041.png