Map.HashMap
Map.HashMap
脑丨残 发表于5个月前
Map.HashMap
  • 发表于 5个月前
  • 阅读 5
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云实验室 1小时搭建人工智能应用,让技术更容易入门 免费体验 >>>   

HashMap jdk8

  • 构造函数,负载因子默认0.75F,影响map扩容//TODO,提供根据参数计算负载因子
  • 继承AbstractMap,实现Map,大部分API都在AbstractMap抽象类中模板方法实现
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;
    }
  • put,hashMap中维护了一个数组,其中存放链表。超过8则转换为红黑树。
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
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;
        //根据table的长度位算法(i = (n - 1) & hash)分配一个index,空则填入node
        //@one
        if ((p = tab[i = (n - 1) & hash]) == null)
            //没有hash碰撞的情况下,put完毕
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //新k-v全等于已有元素,进入@four覆盖
            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) {
                    //@two,相同hash值,添加为链表下一节点
                    //有hash碰撞的情况下,put完毕
                    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;
                    }
                    //
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //@four 覆盖已有值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //防止foreach异常//TODO
        ++modCount;
        if (++size > threshold)
            //重新分配map
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  • get
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    /**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //同put算法(n - 1) & hash,定位数组中相同hash的链表
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //这里always check是,可能大部分情况hashMap碰撞情况很小
            if (first.hash == hash && // always check first node
                ((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 {
                    //开始遍历相同hash的链表,直到找到为止
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
  • EntrySet
  • entrySet返回Set<Node>结构,真正在遍历map时,会遍历HashMaptable[],Node链表。见nextNode();
public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
       final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
                                                        //table[]赋值
            if ((next = (current = e).next) == null && (t = table) != null) {
                //真正遍历table[] ,链表
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
  • KeySet,values,同理,nextNode();遍历节点,取值
final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
}
  • TODO map扩容
标签: map
共有 人打赏支持
粉丝 8
博文 55
码字总数 19033
×
脑丨残
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: