Java 杂谈Java编程社区

java集合框架总结(二)

2019-01-28  本文已影响4人  零度沸腾_yjz

Set

Set集合实现框架:

image.png

Set是一种无序不重复的集合,它最多只允许有一个null元素。Set接口继承Collection接口,因为Set是无序的所以我们可以看到它的接口没有跟游标有管的方法。Set的遍历完全依赖迭代器来Iterator来完成。

image.png

Set有两个有两个子接口,SortedSet和NavigableSet,SortedSet提供了set集合的排序功能,NavigableSet扩展了SortedSet接口,提供了支持基于最接近匹配原则检索元素的行为。

HashSet

HashSet是扩展了Set接口,HashSet使用了Hash表作为支持(实际是HashMap)。如果散列均匀到到不同的桶的haul,HashSet的add、remove、contains和size方法的时间复杂度为O(1)。HashSet的迭代时间等于列表长度+桶数,所以如果迭代很重要,在初始化HashSet的时候应该将其设置的初始容量设置的小一些,或者将负载因子设置的小一些(如果负载因子大的话,桶的个数就多)。

HashSet底层是使用HashMap实现的,所以存储数据变量为map。

 private transient HashMap<E,Object> map;

HashSet提供了6中构造方法,主要参数就是初始容量大小和负载因子。

public HashSet() {
        //初始化容量为HashMap默认容量16,负载因子为HashMap默认负载因子0.75
        map = new HashMap<>();
    }
    public HashSet(Collection<? extends E> c) {
        //以指定集合元素作为新建的HashSet初始值,最少为HashMap的默认值16,如果大于默认值则为集合c的1.75倍容量
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    public HashSet(int initialCapacity, float loadFactor) {
        //指定初始容量和负载因子
        map = new HashMap<>(initialCapacity, loadFactor);
    }
    public HashSet(int initialCapacity) {
        //指定初始用量
        map = new HashMap<>(initialCapacity);
    }
    //使用LinkedHashMap作为HashSet底层存储
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

HashSet将元素作为HashMap的key进行存储,所有操作都是针对HashMap的key进行操作。

public Iterator<E> iterator() {
        //返回map key的迭代器
        return map.keySet().iterator();
    }
    public int size() {
        //返回map个数
        return map.size();
    }
    public boolean isEmpty() {
        //判断map是否为空
        return map.isEmpty();
    }
    public boolean contains(Object o) {
        //判断map的是否包含指定key
        return map.containsKey(o);
    }
    public boolean add(E e) {
        //将添加值作为map的key存储
        return map.put(e, PRESENT)==null;
    }
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    public void clear() {
        map.clear();
    }
    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }

HashSet也不是线程安全的,可以在构造时添加同步操作。

 Set s = Collections.synchronizedSet(new HashSet(...));

LinkedHashSet

LinkedHashSet继承HashSet,它主要使用了HastSet的最后一个构造方法,创建LinkedHashMap。所以LinkedHashSet底层采用的LinkedHashMap进行操作。

 //使用LinkedHashMap作为HashSet底层存储
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

LinkedHashSet的操作方法都是继承HashSet的。

image.png

TreeSet

TreeSet是基于TreeMap实现的NavigableSet有序集合,我们上面说了NavigableSet扩展了SortedSet接口,它能够保证元素有序,并且提供了最近匹配检索元素。元素顺序可以按照自然顺序(升序),或者提供比较器。
需要注意TreeSet中添加是引用类型元素,我们可以通过实现它的comapreTo方法来保证存取顺序。如果compareTo返回1(正数即可),则会按照添加元素的顺序进行存储,如果返回-1(负数即可)则会按照添加元素的倒序进行存储,如果返回0则添加完第一个元素后,后面所有元素都不会添加进去了。我们也可以指定排序方法,这样就会对元素进行排序。
TreeSet为基本操作保证O(logn)时间开销。

image.png

注意这里提供了许多NavigableSet中定义的匹配检索最近元素的方法,比如taiSet、subSet、headSet等。
TreeSet底层实现方式和HashSet一样,直接操作的TreeMap。

其它Set

除了上面说的Set,Java还提供了一下基类Set。
CopyOnWriteArraySet,它底层采用CopyOnWriteArrayList实现。它是线程安全的Set,它适合用于小数据量集合,并且读操作远远超过修改操作,因为修改操作代价很昂贵,需要复制数组。
用于枚举操作的EnumSet,EnumSet保证值存储单个枚举类型的元素。EnumSet底层使用Enum变量存储数据final Enum<?>[] universe;。EnumSet是抽象类,它主要被用于JumboEnumSet和RegularEnumSet。
基于ConcurrentSkipListMap的实现的NavigableSet的实现类ConcurrentSkipListSet,它是线程安全的,并且元素有序。

Map集合框架

Map和Collection是同一级别的集合框架接口,Map定义了一组键值对的映射。Map中键值是唯一的,并且每一个键对应一个映射值。Map中的元素顺序取决于迭代器的迭顺序,有的实现类保证了输入、输出时的顺序,比如TreeMap;有的实现类则是无序,比如HashMap。

image.png

Map提供了三种视图来帮助分析Map:keySet、values和Entry。

image.png

keySet是Map中键的集合,它使用Set保存,所以不允许重复,所以存储的键值需要重写equals和hashCode方法。可通过Map.keySet()获取键值集合。
values是Map中值的集合,它以Collection形式保存,因此可以重复。可以通过Map.values()获取值集合。
Entry是Map中存储键值对的实体,它是Map中内部定义的数据结构。通过Map.entrySet()可以的得到一组Entry集合保存在Set中。

下面是Map接口定义的方法:

Map接口还定义了内部接口Entry,下面是Entry中定义的方法。


image.png

Set替代了Dictionary抽象类,作为映射的顶级接口。
可以使用Map类型作为映射的value,但是禁止使用Map类型作为key。因为太复杂equals和hashCode方法很难确定。还有就是应该尽量避免key是可变的,因为这样会造成map的混乱。

AbstractMap

AbstractMap是Map接口的核心实现抽象类,这样以后map就不需要重新实现这些方法了。当我们要实现一个不可变Map时,可以直接继承该抽象类。如果想要实现可变的Map映射,则还需要覆盖put方法。因为AbstractMap中定义的put方法是不允许操作的。

public V put(K key, V value) {
        throw new UnsupportedOperationException();
    }

AbstractMap中定义了唯一抽象方法entrySet,所以子类都需要重写这个方法,这个方法是返回Map中所有映射实体的集合。AbstractMap中其它方法,都是基于该方法返回的Set<Entry<K,V>>来实现的。

public abstract Set<Entry<K,V>> entrySet();

AbstractMap中定义了两个变量,用来存储键集合和值集合。transient表示该变量不可序列化,volatile表示并发环境的线程可见性。

transient volatile Set<K>        keySet;
transient volatile Collection<V> values;

下面是AbstractMap具体方法实现:

//Set集合中Entry个数就是map中映射的个数
    public int size() {
        return entrySet().size();
    }
    public boolean isEmpty() {
        //长度为0就是为空
        return size() == 0;
    }
    public boolean containsValue(Object value) {
        //获取Entry的迭代器,然后通过Entry.getValue()来获取映射值
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        //分是否为null进行判断
        if (value==null) {
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (e.getValue()==null)
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (value.equals(e.getValue()))
                    return true;
            }
        }
        return false;
    }
    public boolean containsKey(Object key) {
        //获取Entry的迭代器,然后通过Entry.getKey来判断是否存在指定key
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        //通过这里来看可以知道,Map中的key是允许为null的。
        if (key==null) {
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    return true;
            }
        } else {
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    return true;
            }
        }
        return false;
    }
    public V get(Object key) {
        //获取Entry的迭代器
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        if (key==null) {
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    return e.getValue();
            }
        } else {
            while (i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                //通过key的equals来比较key是否相同
                if (key.equals(e.getKey()))
                    return e.getValue();
            }
        }
        //如果没有找到,则返回null
        return null;
    }
    public V remove(Object key) {
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        Map.Entry<K,V> correctEntry = null;
        //查找要删除的Entry
        if (key==null) {
            while (correctEntry==null && i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (e.getKey()==null)
                    correctEntry = e;
            }
        } else {
            while (correctEntry==null && i.hasNext()) {
                Map.Entry<K,V> e = i.next();
                if (key.equals(e.getKey()))
                    correctEntry = e;
            }
        }
        //存储要删除的value,如果没有找到要删除的映射,则返回null。找到的话则返回删除key对应的value。
        V oldValue = null;
        if (correctEntry !=null) {
            oldValue = correctEntry.getValue();
            i.remove();
        }
        return oldValue;
    }
    public void putAll(Map<? extends K, ? extends V> m) {
        //遍历指定的map,然后调用put方法。
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            put(e.getKey(), e.getValue());
    }
    public void clear() {
        //直接使用Set的clear()方法
        entrySet().clear();
    }
    public Set<K> keySet() {
        //如果key为空,则返回一个空的set集合
        if (keySet == null) {
            keySet = new AbstractSet<K>() {
                //AbstractSet中的抽象方法iterator方法实现
                public Iterator<K> iterator() {
                    return new Iterator<K>() {
                        //直接使用entrySet的迭代器
                        private Iterator<Map.Entry<K,V>> i = entrySet().iterator();

                        public boolean hasNext() {
                            return i.hasNext();
                        }

                        public K next() {
                            return i.next().getKey();
                        }

                        public void remove() {
                            i.remove();
                        }
                    };
                }

                public int size() {
                    return AbstractMap.this.size();
                }

                public boolean isEmpty() {
                    return AbstractMap.this.isEmpty();
                }

                public void clear() {
                    AbstractMap.this.clear();
                }

                public boolean contains(Object k) {
                    return AbstractMap.this.containsKey(k);
                }
            };
        }
        return keySet;
    }
    public Collection<V> values() {
        //如果值集合为空,则返回一个新建的Collection
        if (values == null) {
            values = new AbstractCollection<V>() {
                public Iterator<V> iterator() {
                    return new Iterator<V>() {
                        private Iterator<Map.Entry<K,V>> i = entrySet().iterator();

                        public boolean hasNext() {
                            return i.hasNext();
                        }

                        public V next() {
                            return i.next().getValue();
                        }

                        public void remove() {
                            i.remove();
                        }
                    };
                }

                public int size() {
                    return AbstractMap.this.size();
                }

                public boolean isEmpty() {
                    return AbstractMap.this.isEmpty();
                }

                public void clear() {
                    AbstractMap.this.clear();
                }

                public boolean contains(Object v) {
                    return AbstractMap.this.containsValue(v);
                }
            };
        }
        return values;
    }

除了上面基本方法,还有就是提供equals和hashCode:

public boolean equals(Object o) {
        if (o == this)
            return true;
        //先判断类型
        if (!(o instanceof Map))
            return false;
        Map<?,?> m = (Map<?,?>) o;
        //在判断长度,能够有效提高比较效率
        if (m.size() != size())
            return false;

        try {
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();
            while (i.hasNext()) {
                //比较key和value相同才相等
                Map.Entry<K,V> e = i.next();
                K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
                    if (!(m.get(key)==null && m.containsKey(key)))
                        return false;
                } else {
                    if (!value.equals(m.get(key)))
                        return false;
                }
            }
        } catch (ClassCastException unused) {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }

        return true;
    }
    public int hashCode() {
        int h = 0;
        Iterator<Map.Entry<K,V>> i = entrySet().iterator();
        //map的hash值为所有Entry哈希值的和
        while (i.hasNext())
            h += i.next().hashCode();
        return h;
    }

除了这些方法,AbstractMap还定义了两个内部静态类SimpleImmutableEntry和SimpleEntry,它们实现了Entry接口,分别表示不可边的实体Entry和可变的Entry,二者唯一的区别就是setValue方法的支持和不支持。

HashMap

HashMap是使用哈希表(hash table)实现的键值对集合,它继承AbstractMap抽象类和实现了Map接口。

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

HashMap在功能上和HashTable一样,只不过HashMap不是同步操作,而且HashMap允许键值为null。
HashMap的特殊存储结构,使得获取指定元素前,需要经过哈希计算,得到目标元素在哈希表中的位置,然后在进行少量的比较即可得到元素。

image.png

当发生哈希冲突时,HashMap采用拉链法进行解决,所以HashMap的底层实现其实是数组+链表。

下面我们看一下HashMap的具体实现。
HashMap中定义了下面13个变量:

image.png
  1. 默认初始容量16,比如为2的整数倍
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  1. 最大容量2^30,所以map大小为2 ~ 2^30 中间的偶数个。
static final int MAXIMUM_CAPACITY = 1 << 30;
  1. 哈希表的默认负载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
  1. 树型阈值,当使用树而不是使用列表时使用,必须大于2。JDK1.8新增
static final int TREEIFY_THRESHOLD = 8;
  1. 非树形阈值(TODO),JDK1.8新增
static final int UNTREEIFY_THRESHOLD = 6;
  1. 树的最小容量,至少是TREEIFY_THRESHOLD的4倍,避免扩容时冲突。
static final int MIN_TREEIFY_CAPACITY = 64;
  1. 哈希表中的链表数组。
transient Node<K,V>[] table;
  1. 缓存的键值对集合,另外两个视图在AbstractMap中的values()和keySet()中。
transient Set<Map.Entry<K,V>> entrySet;
  1. map中的长度
transient int size;
  1. HashMap的修改次数,用来保证快速失败(fail-fast)
transient int modCount;
  1. 下次需要扩容的值,等于容量 * 负载因子
int threshold;
  1. Hash表的负载因子
final float loadFactor;

其中Node[K,V] table是HashMap底层存储的链表数组,在JDK1.8之前这也是唯一存储数据结构。Node实现了Map.Entry接口。Node的定义就是链表的定义加上实现了Entry中的方法。

static class Node<K,V> implements Map.Entry<K,V> {
        //哈希值,就是位置
        final int hash;
        //存储的键
        final K key;
        //存储的值
        V value;
        //指向下一个节点的指针
        HashMap.Node<K,V> next;

        Node(int hash, K key, V value, HashMap.Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        //哈希值为键和值哈希值的异或
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                //kv相等才相等
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

HashMap扩容开销是非常大的(重新创建数组、重新哈希、分配等等呢个),所以我们应该尽量减少扩容次数。与扩容有关的两个因素:

HashMap的默认加载因子是0.75,这是在时间和空间两方面的考虑。加载因子太大的话,产生冲突的可能性就会很大,查找的效率就会降低。太小的话,需要频繁rehash,导致性能低。

加载因子表示哈希表中元素填满的程度,加载因子越大,填充的元素越多,导致冲突的概率也会越大,查找效率也会越低,但是空间利用率会提高。如果加载因子越少,则填充的元素少,导致冲突的概率也会越小,查找的效率会提高,但是空间利用率会降低。

HashMap提供了四个构造方法:

//指定初始容量和加载因子
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        //容量最多为2^30个
        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);
    }
    //指定容量
    public HashMap(int initialCapacity) {
        //使用默认加载因子
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    //使用默认容量和默认加载因子
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    //创建一个内容为m映射
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

我们看到上面第三个构造方法调用了tableSizeFor方法,该方法是根据你传入的容量,计算出最接近你传入初始容量的2^n。比如传入是5,则返回8。

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

接下来我们看看添加kv操作:

//将指定kv添加到Map中
    public V put(K key, V value) {
        //需要先调用hash方法计算hash值
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //哈希表的一个引用
        HashMap.Node<K,V>[] tab;
        //插入kv的节点
        HashMap.Node<K,V> 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 {
            //如果插入位置不为空则有两种情况:插入key已经存在或该key是产生hash冲途的链表内
            HashMap.Node<K,V> e; K k;//e为当前插入节点
            //拿出链表的第一个节点进行匹配,如果匹配成功则直接返回给e(对于引用类型需要使用equals比较,基础类型使用==比较)
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果第一个节点不为目标节点,并且该节点类型是树形(JDK1.8后)则新增节点到树中
            else if (p instanceof HashMap.TreeNode)
                e = ((HashMap.TreeNode<K,V>)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);
                        //当链表中节点个数大于8时,就需要树型化,提高效率
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果匹配到则直接停止,此时e已经指向了对应节点
                    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;
    }

上述流程可以总结如下:

  1. 先调用hash()方法计算哈希值。
  2. 然后调用putVal()方法根据哈希值进行相关操作。
  3. 如果当前链表为空,则新建一个链表。
  4. 如果插入的桶中没有元素,则新建一个节点放进去。
  5. 匹配桶中链表第一个元素,如果匹配成功,则直接替换新节点,结束查找。
  6. 如果第一个元素,并且第一个元素是JDK8以后的树型节点,则调用putTreeVal()将新数据插入到树中。
  7. 否则从传统链表中查找、替换。
  8. 当当前链表长度大于8时,调用treeIfyBin(),将链表树形话。
  9. 最后检查是否需要扩容

上面设计的方法:

我们先看一下上面计算hash值的方法。hash方法将当前key的哈希值与该哈希值右移16位的结果进行异或。之所以这么做是因为,元素的hashCode在很多时候低位是相同的,这将容易导致冲突。将key的hashCode与hashCode值右移16位进行异或,效果如下:


image.png

代码实现如下:

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这样能够避免只依靠低位计算的结果导致冲突,将高低位结合能够避免哈希值的分布不均。

resize()是初始化或扩容时候使用的,思路是如果是初始化并且

final HashMap.Node<K,V>[] resize() {
        HashMap.Node<K,V>[] 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;
            }
            //扩容到旧容量的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //旧容量为0,但是旧阈值大于0,说明创建的了哈希表,但是还没有添加元素
        else if (oldThr > 0) // initial capacity was placed in threshold
            //容量扩容到旧阈值
            newCap = oldThr;
        //旧容量和阈值都为0,说明还没有创建哈希表,则使用默认规则创建哈希表
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //如果新阈值为0,则使用新容量重新计算一次
        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"})
        HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    //将旧桶置为空
                    oldTab[j] = null;
                    //如果当前桶中没有元素,则直接赋值给对应位置
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果旧节点是树形元素,则在新链表数组中该节点也是树形
                    else if (e instanceof HashMap.TreeNode)
                        ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //否则保留旧哈希表中桶的元素顺序
                        HashMap.Node<K,V> loHead = null, loTail = null;
                        HashMap.Node<K,V> hiHead = null, hiTail = null;
                        HashMap.Node<K,V> 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;
    }

扩容过程中的键点:

获取元素时最常用的就是get(Object key)了,我们看下它是如何实现的。

public V get(Object key) {
        HashMap.Node<K,V> e;
        //先计算key的hash值,然后通过getNode获取
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final HashMap.Node<K,V> getNode(int hash, Object key) {
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
        //如果哈希表为空,则返回null。tab[n-1 & hash]是获取哈希表中的数组位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            //如果拉链表中的一个元素和给定的key匹配,则返回
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //第一个元素不符合,则开始向后遍历
            if ((e = first.next) != null) {
                //如果节点类型为树类型,则通过getTreeNode获取节点值
                if (first instanceof HashMap.TreeNode)
                    return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    //节点类型为链表,则开始遍历链表
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

获取值的关键步骤:

HashMap提供的其它方法实现和上面类似,都是先通过hash值找到哈希表位置,然后遍历链表进行操作,这里就不一一介绍了。下面主要看下JDK1.8新增的红黑树。

[图片上传失败...(image-f0783a-1548676054872)]

在JDK8之后如果桶中的链表长度大于8之后,就会将其转换为一棵红黑树,目的在于能够提高查大量哈希冲突后的元素遍历。
首先看一下HashMap中的红黑树定义:

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        ...
     }

TreeNode中提供了红黑树的基本操作左右转:rotateLeft和rotateRight。同时还提供了红黑树节点的添加、删除、修剪等操作。
JDK8新增的红黑树有三个关键参数变量:

//桶的树化阈值,当桶中元素个数大于8时,将链表转换为RB-tree
static final int TREEIFY_THRESHOLD = 8;
//桶中将树还原为链表的阈值,当树的节点个数为6时,将其转换为列表
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表最小树形化容量,让hash表中元素大于这个值时才会进行树型化
static final int MIN_TREEIFY_CAPACITY = 64;

关于HashMap的红黑树内部具体实现之后再看:TODO

HashMap不是同步的,如果想要同步使用,可以加锁或使用Collections.synchronizedMap包一层,变成线程安全的Map。
HashMap返回的三个视图,都是fail-fast,所以在遍历过程中,如果修改了Map内容,会抛出ConcurrentModificationException。
如果HashMap中大量元素放在一个桶中,这时候在遍历桶中元素时,时间复杂度就为O(n),就失去HashMap的优势了。针对这个问题HashMap在JDK1.8新增了红黑树优化这个问题。
之所以容量要为2的幂次方,主要是以下两个原因:

  1. 容量为2的整次幂的话,h&(length-1)就相当于取模运算,使用减法替代取模运算提升效率。
  2. 保证了length-1为奇数,这样length-1二进制最后一位为1,它与hash结果进行&运算可以随着hash值得到奇数或偶数。如果为偶数,则与后的值一定为0(因为0与任何值都是0),这样所有值都会散列到数组下标偶数位置。

TreeMap

TreeMap继承AbstractMap,并且实现了NavigableMap,再看TreeMap前,我们先看下NavigableMap实现。

NavigableMap

NavigableMap接口继承SortedMap接口。
Map中键值对是无序的,我们在遍历Map时,遍历键的顺序是随机的。SortedMap接口是Map接口进一步扩充,通过对键(key)的排序(自然升序或提供比较器),使得在遍历Map视图时能够根据指定顺序遍历(entrySet()、keySet()、values()方法返回的迭代器)。

public interface SortedMap<K,V> extends Map<K,V> {
    //返回此Map中使用的比较器,如果采用自然顺序,则返回null。
    Comparator<? super K> comparator();
    //返回此映射的部分视图,范围从指定的fromKey(包含)到toKey(不包含)
    java.util.SortedMap<K,V> subMap(K fromKey, K toKey);
    //返回次映射的部分视图,范围为键值小于toKey的所有键值对
    java.util.SortedMap<K,V> headMap(K toKey);
    //返回此映射的部分视图,范围为键值大于等于fromKey的所有键值对
    java.util.SortedMap<K,V> tailMap(K fromKey);
    //返回此映射中的第一个键
    K firstKey();
    //返回次映射的最后一个键值
    K lastKey();
    //返回包含所有键的集合视图
    Set<K> keySet();
    //返回所有值的列表视图
    Collection<V> values();
    //返回所有键值对实体的集合视图
    Set<Map.Entry<K, V>> entrySet();
}

所有实现可排序的Map的实现类,都应该实现四个标准构造方法。

需要注意,所有键都需要实现Comparable接口,或能够接受comparator比较器。

NavigableMap扩展了Sorted接口,提供了要查找的元素最接近匹配相关方法。

[图片上传失败...(image-316f83-1548676054872)]

NavigalbeMap除了提供SortedMap定义的方法外,还提供了以下几类方法:

TreeMap实现

TreeMap是基于红黑树实现的有序键值对集合,该映射根据键的自然顺序或传入的比较器进行排序,具体取决于使用的构造函数。
TreeMap的基本操作containsKey、get、put和remove的时间复杂度为log(n)。
TreeMap继承了AbstractMap抽象类,并且实现了NavigableMap、Cloneable、Serializable接口。

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

首先TreeMap的构造方法就是包含了第一开始所说的可排序Map四类构造函数。

    //无惨构造函数
    public TreeMap() {
        comparator = null;
    }
    //指定比较器的构造函数
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    //传入指定Map,以自然升序构造的新TreeMap
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
    //传入排好序的SortedMap
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            //采用有序方式构造TreeMap
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

我们看到第三个构造函数最后调用了putAll方法,我们再看下putAll的具体实现。

    public void putAll(Map<? extends K, ? extends V> map) {
        int mapSize = map.size();
        //如果Map类型为SortedMap类型,通过buildFromSorted方法构造
        if (size==0 && mapSize!=0 && map instanceof SortedMap) {
            Comparator<?> c = ((SortedMap<?,?>)map).comparator();
            if (c == comparator || (c != null && c.equals(comparator))) {
                ++modCount;
                try {
                    buildFromSorted(mapSize, map.entrySet().iterator(),
                                    null, null);
                } catch (java.io.IOException cannotHappen) {
                } catch (ClassNotFoundException cannotHappen) {
                }
                return;
            }
        }
        //如果是无序Map,则使用AbstractMap中定义的putAll方法
        super.putAll(map);
    }

从上面可以看到如果传入Map类型如果SortedMap则采用和第四个构造函数一样的方法构建TreeMap:buildFromSorted。如果为普通Map则使用AbstractMap的putAll,上面我们看到过AbstractMap的putAll就是挨个调用子类的put方法实现。

首先我们看下红黑树的数据结构:

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key; //存储Map的key
        V value;//存储Map的value
        Entry<K,V> left; //树左节点引用
        Entry<K,V> right; //树右节点应用
        Entry<K,V> parent;
        boolean color = BLACK; //颜色

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }

除了HashMap和TreeMap,我们看下Map中的其它实现:

集合相关问题

  1. Iterable和Iterator的关系是什么?
    Iterator是迭代器接口,而Iterable是使用迭代器需要实现的接口。所以我们如果想要使用迭代器就需要实现Iterable接口,并且实现它的iterator()方法,来返回一个迭代器。
    之所以这样主要是因为Iterator中的next()、hasNext()等方法是依赖当前位置进行的,如果所有需要使用迭代器的类都直接继承Iterator接口的话,都需要为其维护一套指针,并且当同时操作一个类的迭代器时,就会出现这个指针混乱。
    所以一个明智的方法就是通过Iterable的iterator方法来为每个需要使用迭代器的方法返回一个迭代器。

  2. 什么是深拷贝和浅拷贝?
    拷贝方法定义在Object中,Object对clone方法进行了默认实现,这个默认实现其实就是一种浅拷贝。它对于拷贝对象中的应用类型会将其地址拷贝出来,这样就会导致两个对象操作相同的引用变量。
    所以如果想要使用深拷贝,需要重新实现clone方法,不仅利用浅拷贝将基础类型进行拷贝,而且还还需将引用类型进行深拷贝。
    还有一种实现深拷贝的方法就是利用序列化与反序列化,将对象序列化成字节,然后反序列化成对象返回。

上一篇下一篇

猜你喜欢

热点阅读