文档章节

Map.HashMap

脑丨残
 脑丨残
发布于 2017/05/23 22:25
字数 809
阅读 12
收藏 0
点赞 0
评论 0
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
西安

暂无文章

Mybaties入门介绍

Mybaties和Hibernate是我们在Java开发中应用的比较多的两个ORM框架。当然,目前Mybaties正在慢慢取代Hibernate,这是因为相比较Hibernate而言Mybaties性能更好,响应更快,更加灵活。我们在开...

王子城
昨天
0
0
编程学习笔记之python深入之装饰器案例及说明文档[图]

编程学习笔记之python深入之装饰器案例及说明文档[图] 装饰器即在不对一个函数体进行任何修改,以及不改变整体的原本意思的情况下,增加函数功能的新函数,因为这个新函数对旧函数进行了装饰...

原创小博客
昨天
0
0
流利阅读笔记33-20180722待学习

黑暗中的生物:利用奇技淫巧快活生存 Daniel 2018-07-22 1.今日导读 如果让你在伸手不见五指的黑暗当中生存,你能熬过几天呢?而大千世界,无奇不有。在很多你不知道的角落,有些生物在完全黑...

aibinxiao
昨天
2
0
Hystrix降级逻辑中如何获取触发的异常

通过之前Spring Cloud系列教程中的《Spring Cloud构建微服务架构:服务容错保护(Hystrix服务降级)》一文,我们已经知道如何通过Hystrix来保护自己的服务不被外部依赖方拖垮的情况。但是实际...

程序猿DD
昨天
0
0
gin endless 热重启

r := gin.New()r.GET("/", func(c *gin.Context) {c.String(200, config.Config.Server.AppId)})s := endless.NewServer(":8080", r)s.BeforeBegin = func(add string) ......

李琼涛
昨天
0
0
JAVA模式之代理模式

平时一直在用spring,spring中最大的特效IOC和AOP,其中AOP使用的就是代理模式.闲着无聊,随手写了一个代理模式,也记录下代理模式的实现Demo. 比如现在有一个场景是:客户想要增加一个新的功能,...

勤奋的蚂蚁
昨天
0
0
ES15-JAVA API 索引管理

1.创建连接 创建连接demo package com.sean.esapi.client;import java.net.InetSocketAddress;import org.elasticsearch.action.get.GetResponse;import org.elasticsearch.clien......

贾峰uk
昨天
0
0
单点登录的设计,从单域名到多域名(经验分享)

个人实践总结,最初的的需求,多个产品线都在同一个根域名下面。 独立的用户中心分离,单独负责用户登录和用户信息获取、变更等处理逻辑。 第一步,用户登录成功,分配给用户一个memToken(令...

小海bug
昨天
0
0
合格前端第十二弹-TypeScript + 大型项目实战

写在前面 TypeScript 已经出来很久了,很多大公司很多大项目也都在使用它进行开发。上个月,我这边也正式跟进一个对集团的大型运维类项目。 项目要做的事情大致分为以下几个大模块 一站式管理...

qiangdada
昨天
3
0
gradle学习笔记

相关文档 适合新手的 gradle 自学教程合集 Gradle教程

OSC_fly
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部