文档章节

Map.HashMap

脑丨残
 脑丨残
发布于 2017/05/23 22:25
字数 809
阅读 16
收藏 1
map

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.LinkedHashMap
脑丨残
粉丝 8
博文 60
码字总数 23267
作品 0
西安
私信 提问

暂无文章

Spring应用学习——AOP

1. AOP 1. AOP:即面向切面编程,采用横向抽取机制,取代了传统的继承体系的重复代码问题,如下图所示,性能监控、日志记录等代码围绕业务逻辑代码,而这部分代码是一个高度重复的代码,也就...

江左煤郎
45分钟前
1
0
eclipse的版本

Eclipse各版本代号一览表 Eclipse的设计思想是:一切皆插件。Eclipse核心很小,其它所有功能都以插件的形式附加于Eclipse核心之上。 Eclipse基本内核包括:图形API(SWT/Jface),Java开发环...

mdoo
47分钟前
1
0
SpringBoot源码:启动过程分析(一)

本文主要分析 SpringBoot 的启动过程。 SpringBoot的版本为:2.1.0 release,最新版本。 一.时序图 还是老套路,先把分析过程的时序图摆出来:时序图-SpringBoot2.10启动分析 二.源码分析 首...

Jacktanger
54分钟前
3
0
小白带你认识netty(二)之netty服务端启动(上)

上一章 中的标准netty启动代码中,ServerBootstrap到底是如何启动的呢?这一章我们来瞅下。 server.group(bossGroup, workGroup);server.channel(NioServerSocketChannel.class).optio...

天空小小
今天
3
0
聊聊storm trident batch的分流与聚合

序 本文主要研究一下storm trident batch的分流与聚合 实例 TridentTopology topology = new TridentTopology(); topology.newStream("spout1", spout) .p......

go4it
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部