文档章节

JDK1.8HashMap源码分析

小小明童鞋
 小小明童鞋
发布于 10/16 20:31
字数 2284
阅读 59
收藏 6
JDK

HashMap和Hashtable的主要区别是:
1. Hashtable是线程安全,而HashMap则非线程安全,Hashtable的实现方法里面大部分都添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高一些,在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

2. HashMap的键和值都可以为null,而Hashtable的键值都不能为null。

3. HashMap的初始容量为16,Hashtable初始容量为11,两者的填充因子默认都是0.75。HashMap扩展容量是当前容量翻倍即:capacity*2,Hashtable扩展容量是容量翻倍+1即:capacity*2+1(关于扩容和填充因子后面会讲)

4. 两者的哈希算法不同,HashMap是先对key(键)求hashCode码,然后再把这个码值得高位和低位做异或运算,源码如下:

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
i = (n - 1) & hash


然后把hash(key)返回的哈希值与HashMap的初始容量(也叫初始数组的长度)减一做&(与运算)就可以计算出此键值对应该保存到数组的那个位置上(hash&(n-1))。

而Hashtable计算位置的方式如下:

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;


直接计算key的哈希码,然后与2的31次方做&(与运算),然后对数组长度取余数计算位置。

 

hashMap的一些重要属性:

/默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树转为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//存储方式由链表转成红黑树的容量的最小阈值
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap中存储的键值对的数量
transient int size;
//扩容阈值,当size>=threshold时,就会扩容
int threshold;
//HashMap的加载因子
final float loadFactor;

 

接下来是HashMap的put和remove源码分析

HashMap结构就是Node数组,Node源码:

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

put源码分析:

  final V putVal ( int hash, K key, V value,boolean onlyIfAbsent,
        boolean evict){
            HashMap.Node<K, V>[] tab;
            HashMap.Node<K, V> p;
            int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;//第一次调用的时候,数组长度为零,调用resize(),此时数组长度变为16
            if ((p = tab[i = (n - 1) & hash]) == null)//根据传入的hash值,算出Node所在的数组标,拿出Node,如果为空表示当前数组还没有链表,创建新的节点放在数组这个位置
                tab[i] = newNode(hash, key, value, null);
            else {//若取出的节点p不为空
                HashMap.Node<K, V> e;
                K k;
                if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))//只有当取出的节点hash值与Key都与传参一样时才认为两个Node为同一个
                    e = p;// e指向原有的Node
                else if (p instanceof HashMap.TreeNode)//如果找到的当前节点不是key对应的Node,且为TreeNode,执行treeNode的put逻辑
                    e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                else {
                    for (int binCount = 0; ; ++binCount) {// binCount 用来记录当前链表长度
                        if ((e = p.next) == null) {//如果当前Node 不是我们要找的,遍历这个链表数据
                            p.next = newNode(hash, key, value, null);//如果节点的下一个节点为空,创建新的节点,放在现有的节点后面
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st,如果链表长度 >= 8 ,则将链表转换为红黑树
                                treeifyBin(tab, hash);//转换为红黑树
                            break;
                        }
                        if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))//如果当前节点的下一个节点就是我们要找的元素,直接跳出for循环,e是最终要找的Node
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key,如果e不为空,表示找到了对应的节点
                    V oldValue = e.value;//oldValue 用户存储老的值
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;//将新值覆盖原有的值
                    afterNodeAccess(e);
                    return oldValue; // 找到对应的节点以后,返回值为旧value
                }
            }
            //以下代码为只有当e为空,也就是没有找到相匹配的key值得地方,这是就创建了一个新的Node,添加到某个链表后面
            ++modCount;// modCount 用于记录map 被修改了多少次
            if (++size > threshold)// size 表示当前map 有多少个 Node,添加一个元素Node
                resize();//当添加了一个Node以后 size 如果大于 承载量 则进行扩容
            afterNodeInsertion(evict);
            return null;//如果没有找到你对应的节点,执行新增操作,返回null


        }

remove源码分析:
 

 final HashMap.Node<K, V> removeNode ( int hash, Object key, Object value,
        boolean matchValue, boolean movable){
            HashMap.Node<K, V>[] tab;
            HashMap.Node<K, V> p;
            int n, index;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                    (p = tab[index = (n - 1) & hash]) != null) {//根据hash值定位到要移除的元素位置
                HashMap.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;//如果找到了对应的元素,让临时变量node指针指向被删除元素
                else if ((e = p.next) != null) {//如果当前节点没有找到,则向下遍历链表
                    if (p instanceof HashMap.TreeNode)//如果是TreeNode ,将节点强制转换为TreeNode
                        node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
                    else {
                        do {
                            if (e.hash == hash &&
                                    ((k = e.key) == key ||
                                            (key != null && key.equals(k)))) {//遍历整个链表,如果找到要删除的节点就将node指针指向该节点
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                //如果node不为空,则表示找到了要删除的节点
                if (node != null && (!matchValue || (v = node.value) == value ||
                        (value != null && value.equals(v)))) {//该节点值与要删的节点value一致,执行删除动作
                    if (node instanceof HashMap.TreeNode)//如果当前节点是treeNode,则执行treeNode的删除逻辑
                        ((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                    else if (node == p)//如果当前节点就是要删除的节点,则把节点的下一个节点放在数组位置,类似于把头给掐断
                        tab[index] = node.next;
                    else//如果要删除节点不在头部的话,这种情况下,p始终为要删除节点的前一个节点
                        p.next = node.next;//将p节点的next指针指向node的下一个节点,即将node节点删除
                    ++modCount;//统计map被修改的次数
                    --size;//map的 Node 个数减一
                    afterNodeRemoval(node);
                    return node;//返回被删除的Node节点
                }
            }
            return null;//如果没找到被删除节点 ,返回null
        }

扩容源码分析:

 final HashMap.Node<K,V>[] resize() {
            HashMap.Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧的容量,即数组长度
            int oldThr = threshold;//旧的承载量
            int newCap, newThr = 0;//声明两个变量存储新的容量和装载量
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {//如果旧的容量大于容量最大值,不进行扩容,将Integer最大值给装载容量
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                        oldCap >= DEFAULT_INITIAL_CAPACITY)//将原有容量扩容一倍,但不能超过最大容量
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;//如果容量为零(数组为空)但承载量不为0,表示map中以前有过元素,将承载量赋值给容量
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;// 第一次调用方法的时候初始化容量,16
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//初始化承载量,容量*0.75(承载因子)
            }

            if (newThr == 0) {//如果承载量为零,则重新赋值
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                        (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;//覆盖原有承载量
            @SuppressWarnings({"rawtypes","unchecked"})
            HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
            table = newTab;//将原有节点数组指向根据新的容量创建新的节点数组
            if (oldTab != null) {//如果原有数组不为空,则将数组上的每一个链表都拆分为两份,一份存储在原有数组位置,一部分存储在新扩容的数组位置,让节点元素保持均匀分布
                for (int j = 0; j < oldCap; ++j) {
                    HashMap.Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof HashMap.TreeNode)
                            ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            HashMap.Node<K,V> loHead = null, loTail = null;
                            HashMap.Node<K,V> hiHead = null, hiTail = null;
                            HashMap.Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

其中,为什么扩容耗时就很明显了,扩容的流程是将原有数组扩大一倍,将数组上的每一个链表一分为二,均匀地分布在数组上,而java8有引进了红黑树,当链表长度大于8时,将链表转换为红黑树,这样大大加快了get(key)的速度。

 

© 著作权归作者所有

共有 人打赏支持
小小明童鞋
粉丝 30
博文 84
码字总数 74698
作品 0
南京
程序员
私信 提问
加载中

评论(2)

小小明童鞋
小小明童鞋

引用来自“lucas_up”的评论

面试被问到1.8以前的map与1.8以后的map有什么不同,回答到红黑树,后面就不记得了
也是要准备一些面试,所以整理了一下。
l
lucas_up
面试被问到1.8以前的map与1.8以后的map有什么不同,回答到红黑树,后面就不记得了
jdk1.7hashMap源码分析

1.8的源码分析在这里:jdk1.8hashMap源码分析 jdk1.7的map接口结构: jdk1.8的map接口结构: hashMap继承关系: hashTable继承结构: concurrentHashMap继承关系: 哈哈,我比较懒,不想画图...

小小明童鞋
10/19
0
0
baidu面试

下午到了百度大厦感觉这一生有幸再一次来到这里真心高兴。梦开始的地方不能忘。不忘初心方的始终。第一面 基础知识面试首先问了hashmap是如何存储数据、找数据的。 第一点,单个数据是什么结...

hyssop
2016/09/23
103
2
源码之下无秘密 ── 做最好的 Netty 源码分析教程

背景 在工作中, 虽然我经常使用到 Netty 库, 但是很多时候对 Netty 的一些概念还是处于知其然, 不知其所以然的状态, 因此就萌生了学习 Netty 源码的想法. 刚开始看源码的时候, 自然是比较痛苦...

永顺
2017/11/29
0
0
Redis 专栏(使用介绍、源码分析、常见问题...)

来源http://blog.csdn.net/yangbodong22011/article/details/78529448 https://github.com/hurley25 https://github.com/hurley25/ANet ANet 基于Redis网络模型的简易网络库,网络模块代码取......

libaineu2004
2017/12/16
0
0
Redux源码分析之bindActionCreators

Redux源码分析之基本概念 Redux源码分析之createStore Redux源码分析之bindActionCreators Redux源码分析之combineReducers Redux源码分析之compose Redux源码分析之applyMiddleware bindAct...

淡色的云
2017/08/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

当程序员有了中年危机 你会发现你就是个屁

前言 程序员是一个怎样的存在?引用一句鸡汤的名言来说:你以为你用双手改变了世界,实际上是苍老了自己。为什么我今天会抛出这个话题,其实我也是一个懵懂的少年,我也曾经为了成为一名程序...

架构师springboot
5分钟前
0
0
大型网站B2C商城项目实战+MongoDB+Redis+zookeeper+MySQL

本文列出了当今计算机软件开发和应用领域最关键部分,如果你想保证你现在以及未来的几年不失业,那么你最好跟上这些技术的发展。虽然你不必对这十种技术样样精通,但至少应该对它们非常熟悉。...

java知识分子
6分钟前
1
0
大型企业网络系统集成方案如何设计?

网络系统集成是企业实现无纸化办公和即时通讯办公的基础建设,在以生产效率为核心竞争力的市场中,企业想要快速获取信息并有效提高企业工作效率及业务能力,企业网络系统集成是必不可少的,由...

Java干货分享
7分钟前
0
0
Spring应用学习——IOC

1. Spring简介 1. Spring的出现是为了取代EJB(Enterprise JavaBean)的臃肿、低效、脱离现实的缺点。Spring致力于J2EE应用的各层(表现层、业务层、持久层)的解决方案,Spring是企业应用开...

江左煤郎
8分钟前
0
0
用Redis轻松实现秒杀系统

导论 曾经被问过好多次怎样实现秒杀系统的问题。昨天又在CSDN架构师微信群被问到了。因此这里把我设想的实现秒杀系统的价格设计分享出来。供大家参考。 秒杀系统的架构设计 秒杀系统,是典型...

James-
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部