Java集合框架之Set和Map详解

目录

• Set接口
• HashSet
• TreeSet
• Map接口
• HashMap
• TreeMap

Set接口

set接口等同于Collection接口，不过其方法的行为有更严谨的定义。set的add方法不允许增加重复的元素。要适当地定义set的equals方法：只要俩个set包含同样的元素就认为它们是相同的，而不要求这些元素有相同的顺序。hashCode方法的定义要保证包含相同元素的俩个set会得到相同的散列码。
——Java核心技术 卷一

public interface Set<E> extends Collection<E> {
    //一些方法
}

set不允许包含相同的元素，如果调用 add 方法来添加俩个相同的元素，那么在添加第二个元素时就会返回 false。这个接口有俩个比较常用的实现类：HashSet，TreeSet。HashSet是一个没有重复元素的一个无序集合，而TreeSet是一个有序集。

HashSet

HashSet 使用数组和链表来实现散列表，不同 hashcode 的值存放在不同数组下标的位置，相同 hashcode 的值存放在相同数组下标的链表上的不同位置上。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable{
    //一些方法
}

HashSet类中有四个构造方法：

public HashSet()   //构造一个空的散列集
public HashSet(Collection<? extends E> c) //构造一个散列集，并将集合中的所有元素添加到这个散列集中
public HashSet(int initialCapacity, float loadFactor) //构造一个有指定容量和装填因子的空散列集
public HashSet(int initialCapacity)  //构造一个指定容量的空散列集

现在让我们来看一下add方法的源码：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

可以看到这里面是调用了 map.put() 方法，map 在HashSet中的声明如下：

private transient HashMap<E,Object> map;

由此可见HashSet和HashMap有很紧密的联系。

HashSet的底层是用一个HashMap来实现的。HashSet再添加时如何扩容问题在下文HashMap中再详细介绍。

散列表

Java中，散列表用链表，数组实现。也就可以这么理解，在数组不同索引位置上放的是一个链表，要想查找表中对象的位置，要先计算它的散列码，然后与数组长度取余，所得到的结果就是保存这个元素的索引。在保存对象时，通过这个计算方式得到了索引位置，如果这个位置没有其他元素，那就将元素直接插入到该位置就好了，如果这个位置已经有其他元素了，那么需要将这个新的对象与已有的对象进行比较，查看这个对象是否已经存在。如果不存在就在链表的末尾存储这个对象。

TreeSet

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable{
    //一些方法
}

树集是一个有序集合，可以以任意顺序将元素插入集合中。

TreeSet排序是用一个红黑树完成的，每次将一个元素添加到树中时，都会将其放置到正确的排序位置上。由于树集时有序的，所以将一个元素添加到树中要比添加到散列表中慢，所以如果不需要数据是有序的，就没必要为了排序而影响性能。

它也有四个构造函数：

public TreeSet()  //构造一个空的树集，排序方式是自然排序
public TreeSet(Comparator<? super E> comparator)  //构造一个空树集，指定比较器，就是排序方式
public TreeSet(Collection<? extends E> c)   //构造一个树集，并将集合中的所有元素添加到这个树集中
public TreeSet(SortedSet<E> s)     //构造一个树集，并增加一个集合或者有序集中的所有元素，如果是有序集的话，要使用同样的顺序。

上面提到的自然排序是用元素的 compareTo() 方法来比较元素的大小关系（比如你存入v,b,a，就会输出a,b,v），然后将集合元素按照升序排列。

Map接口

集是一个集合，允许你快速的查找现有的元素。但是要查找一个元素，需要有所要查找的那个元素的准确副本。这不是一种常见的查找方式。通常，我们知道某些关键信息，希望查找与之关联的元素。映射（map）数据结构就是为此设计的。映射用来存放键 / 值对。如果提供了键，就可以查找到值。
——Java核心技术

public interface Map<K,V> {
	int size();  //返回映射中的元素数
    V get(Object key);  //返回指定键对应的值
    V remove(Object key); //从映射中删除指定键对应的元素。
}

Java为映射提供了俩个通用的实现：HashMap和TreeMap

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
}

实现了Map接口，存储的内容是键值对(key-value)映射，将键进行散列，散列或比较函数只应用于键，与键相关的值不进行散列或比较。

HashMap底层的结构是，散列表（数组和链表）和红黑树

我用反射的方式输出了这个map的容量，可以看到如果使用无参的构造方法，那么map的容量默认为16。我们也可以通过传参的方式，来指定它的容量，值的一提的是，你指定的容量，一定要为 2 的幂次方，且要小于 int 范围内最大的 2 的幂次方数（1073741824）。

//指定容量
HashMap<String,String> map = new HashMap<String, String>(8);

这个构造方法还是调用了下面的这个构造方法，只是把默认的负载因子值传进去了：

put方法，直接看源码：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

调用put方法后，会根据键值来计算一个值（位置），然后调用putVal来存放元素。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //hash表为空或者长度为0的话，创建hash表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//resize()HashMap扩容的方法
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果位置上没有元素，就加进去，成为链表的头结点
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果这个值的类型为树结构的话，就直接添加到树中，不会判断是否超过8
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //binCount链表的长度
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果链表不为空，就往下一个节点添加
                    p.next = newNode(hash, key, value, null);
                    //如果这个链表的长度大于8，就会转为红黑树存储
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        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;
    //如果里面的元素超过 threshold 的话就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

通过代码中的注释，相信你已经初步了解了 put 方法，总的来说就是添加时首先是用 k 通过哈希函数计算位置，位置上如果没有元素添加在链表的头结点，如果有插入到链表的下一个节点，当链表的长度为大于等于8时，转为红黑树存储，如果该键已经有映射关系的话，用这次的值覆盖掉之前的值，最后判断要不要扩容。如果要扩容，会扩容为原来容量的2倍。这样效率会高一些，也可以减少哈希冲突。

负载因子

上文中我们提到了负载因子，那么负载因子是什么呢？

负载因子也叫装填因子，是一个0.0~1.0之间的数，确定散列表填充的百分比，当大于这个百分比时，散列表进行再散列。在map中，也就是说，当put的元素数量超过一定值的时候，就会扩容，这个值就是负载因子*容量。

HashMap中的负载因子默认是0.75：

static final float DEFAULT_LOAD_FACTOR = 0.75f;

就是说如果map中的元素超过容量的3/4就要进行扩容。

那么为什么这里要默认为0.75呢？这了也是规定了一个相对合理的值，如果为 1 的话效率太低，满了之后才扩容；如果为0.5的话，浪费空间。所以选了一个居中的值。

TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
    
}

它没有实现Map接口是因为AbstractMap实现了Map接口，TreeMap是一个能比较元素大小的Map集合，可以对 key 值进行大小排序。其中，可以使用自然顺序，也可以使用集合中自定义的比较器来进行排序。底层是红黑树结构。

TreeMap中运用到的红黑树结构，是数据结构的一种，相关知识太多，大家感兴趣的话可以在网上查阅资料（博主对树结构的理解不是很透彻