栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

集合(三)Hashmap源码

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

集合(三)Hashmap源码

一、Hashmap数据结构 1.1 HashMap数据结构

        HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null,允许多条记录的值为 null。HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力,或者使用 ConcurrentHashMap。我们用下面这张图来介绍 HashMap 的结构。

Jdk1.7实现 数组+链表

上图中,每个绿色的实体是嵌套类 Entry 的实例, Entry 包含四个属性: key, value, hash 值和用于单向链表的 next 。         1. capacity:当前数组容量,始终保持 2^n ,可以扩容,扩容后数组大小为当前的 2 倍。         2. loadFactor:负载因子,默认为 0.75 。         3. threshold:扩容的阈值,等于 capacity * loadFactor  Jdk1.8实现 数组+链表+红黑树

 

二、Hashmap源码-put方法
transient Node[] table;

 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[] tab; Node p; int n, i;
         //数组为空时,初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            //resize()这里只是初始化数组
            n = (tab = resize()).length;
         //计算hash值对应数组的位置,为空就直接添加节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            //hash和key都相同,进行覆盖
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是树,执行树的添加逻辑
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            //链表
            else {
                for (int binCount = 0; ; ++binCount) {
                    //找到链表最后一个节点,并添加一个节点(尾插法)
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于8而且数组长度大于64,树化
                        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;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//key不相同时,每次插入一条数据自增1. 当size大于threshold
            resize();
        afterNodeInsertion(evict);
        return null;
    }

1.首先获取Node数组table对象和长度,若table为null或长度为0,则调用resize()方法进行初始化table数组和长度。

2.根据hash值计算出数组中对应桶的位置是否为Null,若为Null ,直接添加节点

3.若判定不为Null,我们的判断再做分支
3.1 首先对hash和key值进行判断,如果都相同,则直接覆盖原来的数据

3.2 若进行判断为false,则判断是否为是一颗红黑树, 若判定成功则在红黑树中查找符合条件的节点并将其回传赋给e

3.3 若上面判断都为false,说明这个桶上是一个链表结构,向单向链表中添加数据若单向链表的长度大于等于8并且在treeifyBin(tab, hash)里判断数组长度大于64,就将其转为红黑树保存,记录下一个节点,对e进行判定若成功则返回旧值

4.最后判定数组是否需要扩容
 

四、Hashmap源码-hash方法
  static final int hash(Object key) {
       int h;
        //计算hashCode并且使用hashCode的低16位和高16位进行异或操作,目的使hashCode值足够分散
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

        在下面Hashmap第一次进行调用resize()数组时,DEFAULT_INITIAL_CAPACITY 这个参数强调了Hashmap的数组长度必须是2的倍数。在hash值计算中可以利用位运算去代替取模运算。在hash值计算时,可以看到源码中他将hashCode的高16位和低16位进行一个异或运算,使用hashCode可以充分的使用,使值能相对分散(一个不错的策略)。

五、Hashmap源码-resize方法 
final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            //MAXIMUM_CAPACITY = 1 << 30
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //2倍扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) /
            newCap = oldThr;
        else {    
            //初始化时 
            //DEFAULT_INITIAL_CAPACITY = 1 << 4; 强调初始容量是2的整数倍
            //DEFAULT_LOAD_FACTOR = 0.75f;    
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //分割树
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node 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);
                        //这里看出hashMap扩容不是在原来位置就是原来位置加原来数组长度的位置
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

1.判断数组大小是否足够,足够则直接返回旧数组

2.(1)若旧数组长度大于2的30次方,则直接把数组长度设置成Integer最大值。

   (2)若旧数组左移一位(两倍扩容)后,长度小于2的30次方且大于16,进行两倍扩容

3.确定下一次数组的长度, 将新数组赋予当前数组

4.通过for循环将旧数组中的值存入扩容后的新数组中

4.1 获取旧数组中指定桶下的Node对象 赋予e, 并将旧表中的桶位置数据置空。

4.2 若e的下面没有其他节点则将e直接赋到新数组中桶的位置

4.3 若e的类型为TreeNode(红黑树)

​ 4.3.1 分割树,将新数组和旧数组分割成两个树,并判断桶处节点的长度是否需要转换成红黑树放入新数组存储

​ 4.3.2 通过doWhile循环,不断获取新旧数组的节点

​ 4.3.3 通过判定将旧数据和新数据存储到新数组指定的位置

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/964237.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号