【Set、Map接口详解】聊一聊 HashSet、HashMap、TreeSet、TreeMap、LinkedHashMap等集合以及Collections工具类

【Set、Map接口详解】聊一聊 HashSet、HashMap、TreeSet、TreeMap、LinkedHashMap等集合以及Collections工具类

【Set、Map接口详解】聊一聊 HashSet、HashMap、TreeSet、TreeMap、linkedHashMap等集合

• • 一、Set接口
  • • 1.HashSet
    • • • 概述：
        • 构造方法：
        • 方法：
        • 扩容：
        • hashCode与equals重写原则：
    • 2.TreeSet
    • • • 概述：
        • 定义：
        • 方法：
        • 总结：
    • 3.linkedHashSet
    • • • 概述：
        • 定义：
        • 构造方法：
        • 特点：
  • 二、Map接口
  • • • map方法
      • 遍历
    • 1.HashMap
    • • • 概述：
        • 构造方法：
        • 方法：
        • 扩容机制：
    • 2.HashTable
    • • • 概述：
    • HashMap与HashTable的区别
    • 3.TreeMap
    • • • 概述：
        • TreeMap的key的排序：
    • 4.linkedHashMap
    • • • 概述：
        • 底层
    • 5.Properties
    • • • 概述：
        • 方法：
    • 三、集合的输出
    • • • 1.迭代器Iterator
        • 2.增强For循环ForEach
        • 3.Enumeration
        • 4.使用
    • 四、Collections工具类

一、Set接口

Set是Collection的子接口，不允许重复单值，无序，只能存一个null（因为不可重复）

1. 定义
   public interface Set extends Collection
2. 方法
   • of(E e),of(E… element)
     返回包含0或多个元素的不可修改集
   • removeAll(Collection c)
     从此集合中删除指定集合中包含的所有元素
   • retainAll(Collection c)
     仅保留此集合中包含在指定集合中的元素
3. 注意
   不允许重复值，无序的，一个null

1.HashSet 概述：

• 概述
  散列存放，底层使用HashMap的key存值，value存放默认的对象
  HashSet存储自定义类型元素
  需要重写对象中的hashCode和equals方法，建立自己的比较方
  式，才能保证HashSet集合中的对象唯一
• 重点：
  根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于： hashCode 与 equals 方法。

构造方法：

• HashSet()
• HashSet​(int initialCapacity)
  指定初始值
  默认的初始值为16，负载因子为0.75
• HashSet​(int initialCapacity, float loadFactor)
  指定初始容量跟负载因子
• HashSet​(Collection c)

方法：

类似：接口Set跟Collection接口的方法

扩容：

同HashMap底层机制一样！
底层是数组，初始容量16，使用率达到0.75，即12时，就会扩大为原来的2倍

hashCode与equals重写原则：

• 重写hashCode原则
  • 同一对象，多次调用hashCode返回值相同
  • 两个对象的equals返回相同，hash值也应相同
• 重写equals原则
  • 当类有“逻辑相等”概念，当改写equals时候，总要改写hashCode（）
  • “相等的对象必须具有相等的散列码”
  • 复写equals方法时一般需复写hashCode方法。两个互相参与计算
    面试

2.TreeSet 概述：

一个排序的Set集合，底层是TreeMap
是SortedSet接口的实现类，可以保证元素处于排序状态
TreeSet底层使用红黑树结构存储数据
有序、查询速度比list快

定义：

public class TreeSet extends AbstractSet
implements NavigableSet, Cloneable, Serializable

方法：

1. ceiling​(E e)
   放回比给定元素大或等于的null元素，没有返null
2. first()
   返回第一（最低）元素
3. last()
   返回最后一个（最高）元素
4. floor（E e）
   返回此set小于或等于给定元素的最大元素，没有返回null
5. higher​(E e)
   返回大于给定元素的最小元素
6. headSet​(E toElement)
   返回小于给定元素的部分集合
7. tailSet​(E fromElement)
   返回大于或等于给定元素的部分集合
8. tailSet​(E fromElement, boolean inclusive)
   返回此set的部分视图，其元素大于（或等于，如果 inclusive为true） fromElement 。
9. subSet​(E fromElement, E toElement)
   返回该范围的元素集（前闭后开）
10. subSet​(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
    返回该范围是否包含边界值的集合
11. pollFirst
    检索并删除第一个（最低）元素，如果此集合为空，则返回 null
12. pollLast
    检索并删除最后一个（最高）元素，如果此集合为空，则返回 null

总结：

• 关于 TreeSet 的排序实现，如果是集合中对象是自定义的或者说其他系统定义的类没有实现Comparable 接口，则不能实现TreeSet 的排序，会报类型转换ClassCastException（转向 Comparable 接口）错误。
• 换句话说要添加到 TreeSet 集合中的对象的类型必须实现了Comparable
  TreeSet 的集合因为借用了 Comparable 接口，同时可以去除重复值，而 HashSet 虽然是Set 接口子类，但是对于没有复写 Object 的 equals 和 hashCode 方法的对象，加入了 HashSet集合中也是不能去掉重复值的

3.linkedHashSet 概述：

set是没有序的，为了保证存入有序，linkedHashSet是双向链表和哈希表组合的一个数据存储结构。
是HashSet子类。底层调用linkedHashMap
根据元素的hashCode值决定元素的位置，使它同时使用双向链表维护元素的次序，使得元素看起来是以插入顺序保存的。
linkedHashSet插入性能低于HashSet，但在迭代访问Set元素时性能好
不允许集合元素重复

定义：

public class linkedHashSet
    extends HashSet implements Set, Cloneable,java.io.Serializable

构造方法：

调用super父类HashSet

 public linkedHashSet() {
        super(16, .75f, true);
    }

特点：

• 哈希表和链表实现的Set接口，具有可预测的迭代次序
• 由链表保证元素有序，也就是说元素的存储和取出顺序是一致的
• 由哈希表保证元素唯一，也就是说没有重复的元素

二、Map接口

双值存储，key-value存储形式
子类：HashMap、TreeMap、HashTable

map方法

1. clear()
   清空
2. containsKey(Object key)
   判断是否存在key
3. containsValue(Object value)
   判断是否存在value
4. Set>entrySet()
   将map接口变为Set集合
5. V get(Object key)
   根据key获得value
6. isEmpty
   判空
7. SetkeySet()
   将key变为Set集合
8. Collection values()
   将value变为Collection集合
9. put(K key,V value)
   增加元素
10. putAll(Map m))
    增加一组集合
11. remove(K key)
    根据key删除内容

遍历

方法一
	获取所有键的集合，用keySet（）实现
	遍历键的集合，获取到每一个键，用增强for
	根据键去找值，用get实现
方法二
	获取所有键值对对象集合Set> entry()实现
	遍历键值对对象集合，得到每一个键值对对象  增强for
	根据键值对对象获取键和值：getKey得到键，getValue()得到值

1.HashMap 概述：

key构成集合是Set：无序、不可重复，所以可以所在类要重写equals、hashCode
value构成集合是Collection：无序的、可重复，所以value所在类重写equals
判断key相等标准：equals返回true，hashCode值相同
判断value相等的标准：equals返回true
存储结构：

• JDK1.7
  数组+链表结构（链地址法）
• JDK1.8
  数组+链表+红黑树实现

构造方法：

HashMap()
HashMap​(int initialCapacity)
HashMap​(int initialCapacity, float loadFactor)
HashMap​(Map m)

方法：

同Map接口方法

扩容机制：

1. 首先弄清楚HashMap类里的几个属性：

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量为16
	static final int MAXIMUM_CAPACITY = 1 << 30;//默认最大容量为2^30
	static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子为0.75
	static final int TREEIFY_THRESHOLD = 8;//树型阈值(界限)8
 	static final int UNTREEIFY_THRESHOLD = 6;//非树阈值(界限)6，转链式的界限值
    static final int MIN_TREEIFY_CAPACITY = 64;//树最小容量64
    
	int threshold;//阈值
	final float loadFactor;//负载因子
	  transient Node[] table;//存储结点
	  transient Set> entrySet;//获取key的set集合的变量
	  transient int size;//键值对数
	  transient int modCount;//被修改的次数
......

2. 以空参构造为例作以说明：
   调用空参构造方法，使用默认的负载因子DEFAULT_LOAD_FACTOR为0.75，它初始默认有16个哈希桶，当桶的使用率达到16*0.75=12时，就进行扩容resize()方法。
   如果是带参构造，在构造方法中，会判断传入的initialCapacity跟loadFactor进行判断！符合条件，进行赋值：
   this.loadFactor = loadFactor;
   this.threshold = tableSizeFor(initialCapacity);

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

3. put方法的底层：
   • 首先调用hash方法得到哈希值，根据哈希值去选择合适哈希桶位置；
   • 当哈希桶全为空，则创建新的结点存储
   • 当当前哈希桶有值，则调用equals进行比较，判断是否为同一对象，如果是同一对象，则不存储；反之，添加一个Node,
     • 当链表长度达到8时，则扩容或者转为树，调用treeifyBin(tab, hash)构建树型结构；
     • 当链表长度为6时，进行树转为链式结构。（为6时，要考虑之前是链表还是树，也就是之前的节点数是多少）
   • 当发现哈希桶使用率达到阈值，则调用resize进行扩容，原来的2倍。

hash方法源码：

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 
        16);//^等同于取余。用自己的hash值跟自己hash值的16个高位进行取余
    }

put方法的源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {
                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;
    }

• resize方法，初始默认哈希桶容量为16个，负载因子为0.75，当哈希桶使用达到16*0.75=12时，扩容，扩大为2倍

链表与红黑树：

当链表长度到8时，转为红黑树treeifyBin()
当树的结点小于等于6时，转为链表
初始16，最大2的30次幂，树临界8，链表临界6,树最小容量64

2.HashTable 概述：

• HashTable是古老的Map实现类，Hashtable不同于HashMap：Hashtable是线程安全的
• 实现原理和HashMap相同，功能相同，底层都是用哈希表结构，查询快
• 不同的是：Hashtable不允许使用null作为key或value
• 也不能保证key-value对顺序
• 判断相等与HashMap一样

HashMap与HashTable的区别

HashMap
	JDK 1.2 之后
		异步处理，性能较高
			允许设置为 null
Hashtable
	JDK 1.0 时
		   同步处理，性能较低
			不允许设置null，否则将出现空指向异常

3.TreeMap 概述：

TreeMap需要根据key-value对进行排序。保证所有键值对处于有序状态
底层使用红黑树结构存储数据
不能存储null，会报空指针异常

TreeMap的key的排序：

• 自然排序：所有key必须实现Comparable接口，所有key应为同一类对象，否则抛出ClassCastException
• 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap的key排序，此时不需要key实现Comparable接口
• 判断两个key相等：两个key通过compareTo或compare返回0

4.linkedHashMap 概述：

是HashMap的子类，在HashMap存储结构基础上，使用了一对双向链表来记录添加元素的顺序
与linkedHashSet类似，可以维护Map迭代顺序，与键值对插入顺序一致

底层

  底层存储实现是HashMap，同时加入了双向链表，通过HashMap里的Node类和linkedHashMap中的Entry类来存储数据，主要是linkedHashMap里Entry类，通过before，after两个指针来标记该节点前后的结点，实现链式存储（记录插入的顺序，实际数据存储在哈希表里）。

HashMap的Node类
	    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
...
}

linkedHashMap的Entry类
	 static class Entry extends HashMap.Node {
        Entry before, after;
        Entry(int hash, K key, V value, Node next) {
            super(hash, key, value, next);
        }
    }

5.Properties 概述：

是HashTable的子类
该对象用于处理属性文件，key和value都为字符串
存取数据：setProperty（key,value）、getProperty（key）

方法：

实际使用:

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");

三、集合的输出 1.迭代器Iterator

1. Iterator
   hasNext、next、remove
2. ListIterator
   List特有的迭代器
   previous往前移动指针
   hasPrevious前面是否有元素
   add添加，开始的add是添加在list最前面的位置，应该前移后遍历
   nextIndex返回下一个索引值
   previousIndex返回上一个索引值
3. 迭代
     即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续在判断，如果还有就再取出出来。一直把集合中的所有元素全部取出。这种取出方式专业术语称为迭代。

2.增强For循环ForEach

forEach
  增强for循环(也称for each循环)是JDK1.5以后出来的一个高级for循环，专门用来遍历数组和集合的。它的内部原理其实是个Iterator迭代器，所以在遍历的过程中，不能对集合中的元素进行增删 *** 作

3.Enumeration

Enumeration 是一个非常古老的输出接口，其也是一个元老级的输出接口，最早的动态数组使用 Vector 完成，那么只要是使用了 Vector 则就必须使用 Enumeration 进行输出

Enumeration enu = v.elements();
while (enu.hasMoreElements()) {
System.out.println(enu.nextElement());
}

Vector对象.elements()：获得Enumeration
hasMoreElements()：判断是否后面有元素
nextElement()：取出当前元素并后移

4.使用

在实际开发中，我们使用频率如下：
Iterator 迭代输出（90%）、ListIterator（5%）、Enumeration（1%）、foreach（4%）

四、Collections工具类

1. 概述：
   Collections类在java.util.collections
   Collections是一个 *** 作Set、List、Map等集合的工具类
2. 排序 *** 作（均为static方法）
   reverse（List）：反转List中元素的顺序
   shuffle（List）：对List集合元素进行随机排序
   sort（List）：根据自然顺序进行升序排序
   sort（List，Comparator）：根据指定Comparator排序
   swap（List，int，int）：交换
3. 常用方法
   max、min、copy（List dest，src）：src内容复制到dest中、replace（list，old，new）：新值替换、
   frequency（Collection，Object）：出现次数
4. 同步控制
   Collections提供多个synchronizedXxx（）方法，可以将指定集合包装成线程同步的集合。从而解决多线程并发访问集合时线程的安全问题。
   迭代方法器未加锁，其他全加锁
5. 不可变集合
   emptyXxx（）
     返空，不可变集合对象
   singletonXxx(T o)
     返回只包含指定对象的不变集合
   unmodifiableXxx(Xxx xx)
     返回指定集合不可变的集合

集合是我们后续编程开发中，使用最多的存储容器，对于这方面的知识以及用法，我们应多看多练，对集合做到得心应手！