文档章节

Map.HashMap

脑丨残
 脑丨残
发布于 2017/05/23 22:25
字数 809
阅读 15
收藏 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扩容

© 著作权归作者所有

共有 人打赏支持
脑丨残
粉丝 8
博文 60
码字总数 23267
作品 0
西安

暂无文章

转:XMLHttpRequest2 新技巧

”XMLHttpRequest 的异步调用网上找的例子运行没问题,但稍微改了一点点就报错”InvalidStateError: XMLHttpRequest has an invalid context“。断断续续 搞了3天终于通了,可以接收二进制文...

SamXIAO
31分钟前
1
0
=====D服务器定时任务=====

Linux定时任务 crontab linux系统是有cron这个系统服务来控制的,Liunx系统上包含很多的计划性工作,使用者自己可以设置计划任务,所以linux系统提供了使用者控制计划任务的命令 crontab的启...

覃光林
40分钟前
1
0
xilinx资源

本系列教学视频由赛灵思高级战略应用工程师带领你:从零开始,一步步深入 掌握 HLS 以及 UltraFAST 设计方法,帮助您成为系统设计和算法加速的大拿! http://www.eetrend.com/topics/2018-0...

whoisliang
51分钟前
2
0
企业级开源四层负载均衡解决方案--LVS

网盘链接 企业级开源四层负载均衡解决方案--LVS 本课程将在Linux环境下,学习配置使用LVS,对Web集群和MySQL集群进行负载均衡,并结合利用Keepalived实现负载均衡器的高可用,实现对后端Rea...

qq__2304636824
今天
3
0
Windows上安装Spacemacs

emacs安装 下载地址emacs 安装比较简单,解压后执行\bin\addpm.exe即可 emacs配置 emacs的默认配置文件路径和.emacs.d文件夹都是在Windows主目录下的 C:\Users\Administrator\AppData\Roami...

yxmsw2007
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部