java集合类-3-Map

2019-09-30 本文已影响0人宠辱不惊的咸鱼

HashMap

属性

int DEFAULT_INITIAL_CAPACITY = 1 << 4; // table数组默认初始大小
int MAXIMUM_CAPACITY = 1 << 30; // table数组最大容量
int TREEIFY_THRESHOLD = 8; // bin达到8开始树化
int MIN_TREEIFY_CAPACITY = 64; // 树化时table需满足容量，否则说明碰撞过多，resize table
int UNTREEIFY_THRESHOLD = 6; // bin达到6开始去树化
int size; // 键值对数量
int threshold; // resize临界值，size > threshold开始扩容
float DEFAULT_LOAD_FACTOR = 0.75f; // 小于1：减少碰撞，空间换时间
float loadFactor;
Node<K,V>[] table; // Node数组
Set<Map.Entry<K,V>> entrySet; // 实体集合，Node实现Map.Entry<K,V>接口
int modCount; // 用于ConcurrentModificationException

Node

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

TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
    // Node有的这个都有
    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;

构造方法

HashMap() // 赋值默认负载因子
HashMap(int initialCapacity) // this(initialCapacity, DEFAULT_LOAD_FACTOR)
HashMap(int initialCapacity, float loadFactor)
    this.loadFactor = loadFactor;                   // 负载因子
    this.threshold = tableSizeFor(initialCapacity); // threshold

// cap的ceil 2次幂
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;
}

resize

场景
- table为空： putVal
- ++size > threshold：putVal添加之后，其实放前面比较好(ConcurrentHashMap就是放前面)
- putMapEntries：待塞Map的size > threshold
- 树化时：table没有达到MIN_TREEIFY_CAPACITY(64)
机制
- table >= MAXIMUM_CAPACITY(2^30)，threshold = Integer.MAX_VALUE，table不变
- table > 0 && DEFAULT_INITIAL_CAPACITY <= table && 2 * table < MAXIMUM_CAPACITY
  - capacity和threshold都放大1倍
- table为空 && threshold > 0（构造方法传进初始容量，threshold = ceil 2次幂）
  - table = threshold, threshold = table * loadFactor
- table为空 && threshold == 0（无参构造方法）
  - table = DEFAULT_INITIAL_CAPACITY
  - threshold = DEFAULT_INITIAL_CAPACITY * loadFactor
- 遍历table，处理每一个bin
  - 单节点bin：&(oldCap-1) -> &(newCap-1)
  - TreeNode：树拆分
  - 多节点list，(e.hash & oldCap) == 0 ? lo : hi，lo放回原index，hi放到(原index+oldCap)

树拆分

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

添加

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

// 防止table过小时hash高位失效
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (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;
    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<K,V> 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<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);
                    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;
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
- table是否存在，不存在则resize生成一个table
- 判断table[hash & (n-1)]是否存在
  - bin不存在，创建首节点
  - bin存在
    - 首节点命中
    - 首节点p是TreeNode，调用((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)
    - 非TreeNode，遍历list；添加后bin达树化容量，进行树化
  - 根据++size是否超threshold决定resize
  - afterNodeInsertion(evict) - LinkedHashMap

TreeNode添加

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)
- 判断parent是否为空，来决定root是root()还是当前节点
- 比较hash，决定左右方向，dir -1代表左，dir 1代表右
  - hash碰撞时
    - 比较key，若key相等，则命中
    - 利用compareTo进行比较，得到dir值
    - 调用find(h, k, kc)
    - dir = tieBreakOrder(k, pk);通过默认的hashCode来得到方向
- 找到叶子节点处，新建一个节点，并调用balanceInsertion和moveRootToFront
- 在以上的过程中，实际分两种大的情况，即命中和未命中；若是命中，会返回调用者一个节点，用于value的更新；若未命中，则返回null，那么调用者就不需要更新value，也即新增

树化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

final void treeify(Node<K,V>[] tab)
- 第一个作为root
- 其余，先进行方向确定，然后底部插入
- 利用root = balanceInsertion(root, x)进行平衡
- 确定方向过程中，发生hash碰撞，且无法通过compareTo决定时，调用dir = tieBreakOrder(k, pk);
- tieBreakOrder中使用原始hashCode做排名，这个信息在find时并没有用到，查询时在hash碰撞及compareTo失效时，采取递归
static int tieBreakOrder(Object a, Object b)
- 相等时返回-1
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)
- 插入x，x xp xpp xppl xppr分别为x的父亲和爷爷，步骤如下：
- x.red置true
  - xp为null，那么x就是root（在treeify调用时感觉不会发生）
  - xp非红，或者xpp为null，无需操作，直接返回root
  - xp为红左
    - 若xppr为红右，那么双红置黑红上移
    - 若x为xp的右节点，那么左旋，再右旋
  - xp为红右
    - 若xppl为红左，那么双红置黑红上移
    - 若x为xp的左节点，那么右旋，再左旋
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root)
- 如果root不是bin的第一节点，就把root拎出来放到第一个位置，具体操作如同对LinkedList操作一般
static <K,V> boolean checkInvariants(TreeNode<K,V> t)
- 不是很懂什么意思，被moveRootToFront调用了，其中用了assert，实际部署中应该是无效的

取值

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((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;
}

final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

// 若是x实现了Comparable，则返回x的Class对象，否则返回null
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) 
                && ((p = (ParameterizedType)t).getRawType() == Comparable.class)
                && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

// x非空 && x和kc同类型，返回k.compareTo(x)；若是类型不同，就没有compareTo的必要了
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
}

find
- 根据hash判左右
- hash碰撞key不等，调key的compareTo
- 没有实现Comparable接口，递归右侧

删除

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

// 清空table元素，不删table
public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

Set相关

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

Hashtable

public synchronized V get(Object key) 
public synchronized boolean contains(Object value)
public synchronized boolean containsKey(Object key)

public synchronized V put(K key, V value)
public synchronized void putAll(Map<? extends K, ? extends V> t)

public synchronized V remove(Object key)
public synchronized void clear()

public synchronized Object clone()

public synchronized String toString()

TreeMap

概述

基于红黑树

属性

private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;

private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;

构造方法

public TreeMap() {
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    
    } catch (ClassNotFoundException cannotHappen) {
    
    }
}

添加

public void putAll(Map<? extends K, ? extends V> map)
- 若属于SortedMap，调用buildFromSorted(mapSize, map.entrySet().iterator(), null, null);
- 否则调用super.putAll
public V put(K key, V value)
- 先判断root是否为null，为null直接新建Entry，并返回null（表示未命中）
- 判断comparator是否为空
  - comparator不为空，用compare方法去消耗树，直到遇到叶子节点；或者命中，命中时更新value并返回旧的value
  - comparator为空，则用Comparable的compareTo（此处会有ClassCastException，不知道为什么没有处理，故意的？？？）去消耗树，直到遇到叶子节点；或者命中，命中时更新value并返回旧的value
- 创建一个节点，并根据cmp值放在左边或者右边
- fixAfterInsertion(e);//e是一个Entry；此处会左右旋修补
- size++ modCount++ 返回null（表示未命中）

取值

final Entry<K,V> getEntry(Object key) {
    if (comparator != null)// Offload comparator-based version for sake of performance
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;//这里可能ClassCastException哦
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
    K k = (K) key;
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

final Entry<K,V> getCeilingEntry(K key)
    匹配项不存在时，先找大于该key的最小项，还不存在则返回null

final Entry<K,V> getHigherEntry(K key)
    不寻找匹配项，其余同getCeilingEntry

final Entry<K,V> getFloorEntry(K key)
    匹配项不存在是，先找小于该key的最大项，还不存在则返回null

final Entry<K,V> getLowerEntry(K key) 
    不寻找匹配项，其余同getFloorEntry

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

public boolean containsValue(Object value) {
    for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
        if (valEquals(value, e.value))
            return true;
    return false;
}

删除

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;
    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

public void clear() {
    modCount++;
    size = 0;
    root = null;
}

Set相关

public Set<K> keySet() {
    return navigableKeySet();
}
public NavigableSet<K> navigableKeySet() {
    KeySet<K> nks = navigableKeySet;
    return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}

public NavigableSet<K> descendingKeySet() {
    return descendingMap().navigableKeySet();
}

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

java集合类-3-Map

HashMap

属性

Node

TreeNode

构造方法

resize

树拆分

添加

TreeNode添加

树化

取值

删除

Set相关

Hashtable

TreeMap

概述

属性

构造方法

添加

取值

删除

Set相关

猜你喜欢

热点阅读