一、HashMap数据结构

一、HashMap数据结构初学HashMap,希望大家批评指正。

大家好,又见面了,我是你们的朋友全栈君。HashMap数据结构

1、HashMap介绍

hash就是散列,就是把对象在内存中打散,其目的就是查询速度更快。

如何做到查询速度快?

哈希码。hashCode()方法。

HashMap是一种实现了Map接口,key和value都允许为空,并且无序的,非线性安全的,非常常见、方便和有用的集合。

2、头部源码

public class HashMap<K,V>

    extends AbstractMap<K,V>

    implements Map<K,V>, Cloneable, Serializable

HashMap实现了Map接口,继承了AbstractMap。Map接口定义了键映射到值的规则,而AbstractMap类提供 Map 接口的骨干实现,HashMap 实现了Serializable接口,因此它支持序列化,实现了Cloneable接口,能被克隆。

HashMap的实例有两个参数影响其性能:初始容量和负载因子。

容量是哈希表中数组元素的数量,初始容量只是哈希表在创建时的容量。负载因子是哈希表在其容量自动增加之前可以达到的最大限度。当哈希表中元素的数量超出了加载因子与当前容量的乘积时,则要对该哈希表进行rehash操作(即重建内部数据结构),从而哈希表将扩大两倍。

3、HashMap的数据结构

Java中比较常用的两种结构是数组和引用(模拟指针),HashMap实际上就是一个数组和链表的结合体。

一、HashMap数据结构

4、属性分析

    a、static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    HashMap默认的初始化数组元素数量。

    b、static final int MAXIMUM_CAPACITY = 1 << 30;

    HashMap中数组元素数量的最大值。

    c、static final float DEFAULT_LOAD_FACTOR = 0.75f;

    默认的负载因子,如果在创建HashMap的构造函数中没有指定负载因子则指定该HashMap的默认负载因子为0.75,这意味着当HashMap中条目的数量达到了条目数量75%时,HashMap将进行resize操作以增加数组元素的数量。

    d、transient Node<K,V>[] table;

     table是HashMap的存储结构,显然这是一个数组,数组的每一个元素都是一个条目,Node是HashMap中的一个内部类,它有四个属性:int hash, K key, V value, Node<K,V> next,分别是哈希值,键,值,指向下一个链表结点的指针。

    e、transient int size;

     size表示HashMap中键值对的数量。

    f、int threshold;

     threshold是HashMap的重构阈值,它的值为容量和负载因子的乘积。在HashMap中所有数组元素中条目的总数量达到了这个重构阈值之后,HashMap将进行resize操作以自动扩容。

5、构造函数

    (1)public HashMap(int initialCapacity, float loadFactor) {

            …

            /**

             * 根据传入的初始化容量计算该HashMap的容量(即元素的数量)

            **/

            if (initialCapacity > MAXIMUM_CAPACITY)

                initialCapacity = MAXIMUM_CAPACITY;

            ..

            /*

                初始化负载因子            

             */

            this.loadFactor = loadFactor;

            /*

                键值对阈值计算            

             */

            this.threshold = tableSizeFor(initialCapacity);

        }

        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;

    }

    (2)public HashMap(int initialCapacity) {

        //初始化容量传入,加载因子为默认值0.75f

        this(initialCapacity, DEFAULT_LOAD_FACTOR);

    }

    (3)public HashMap() {

        this.loadFactor = DEFAULT_LOAD_FACTOR; // 均为默认值

    }

    (4)public HashMap(Map<? extends K, ? extends V> m) {

        this.loadFactor = DEFAULT_LOAD_FACTOR;

        putMapEntries(m, false);

    }

6、hash函数

在get和put的过程中,计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标。

    static final int hash(Object key) {

        int h;

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    }


一、HashMap数据结构

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/144538.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • PCA算法过程_pca推导

    PCA算法过程_pca推导PCA是主成分分析(PrincipalComponentsAnalysis)的简称。这是一种数据降维技术,用于数据预处理。一般我们获取的原始数据维度都很高,那么我们可以运用PCA算法降低特征维度。这样不仅可以去除无用的噪声,还能减少很大的计算量。…

  • HTTP.SYS 详解

    HTTP.SYS 详解http.sys 是一个位于Win2003和WinXPSP2中的操作系统核心组件,能够让任何应用程序通过它提供的接口,以http协议进行信息通讯。温馨提示:如果用户不慎删除了该驱动文件,不用担心,该驱动会在下次系统启动时重建。是一个删不掉的系统核心组件!实用程序结束该驱动,该驱动也会马上重新创建(只有粉碎文件才不能马上重建,但粉碎后,下次启动会重建)。微软在Windows

  • ORB-SLAM 2+3 rgbd稠密地图 (地图可回环)「建议收藏」

    ORB-SLAM 2+3 rgbd稠密地图 (地图可回环)「建议收藏」高博曾经在他的github上提供过,但因为大佬时间少,并没有将回环加入到稠密地图,现提供一个可回环的稠密地图版本https://github.com/tiantiandabaojian/ORB-SLAM2_RGBD_DENSE_MAP.git第一张图片是TUM数据集未回环的地图第二张图片是经过回环的地图第三张是博主自己用KinectV2跑出的地图望能帮到各位…

  • 闰年的判断方法_判断是不是闰年的条件

    闰年的判断方法_判断是不是闰年的条件①、普通年能被4整除且不能被100整除的为闰年.②、世纪年能被400整除的是闰年③、对于数值很大的年份,这年如果能整除3200,并且能整除172800则是闰年.如172800年是闰年,86400年不是

  • 帕金森疾病的事件相关电位与认知「建议收藏」

    认知障碍是帕金森疾病(PD)中常见的一个非运动性症状。但是在个体之间的认知变化的本质特点有着很大的差异。根据双症侯群假说,一组患者的特点是执行功能的缺陷,这可能与额叶纹状体功能障碍有关;其他患者主要表现为非额叶相关的认知损伤,迅速发展为帕金森疾病痴呆(PDD)。本文对事件相关电位(ERP)的研究进行了全面的回顾,通过ERP方法来证明PD中认知损伤的这种异质性特点。本综述提供了证据,显示PDD中出现P3b和失匹配负波的改变,但这不存在于非痴呆PD患者中,表明这些ERP成分的改变组成了PDD的电生理标记。相反,

  • 主机号「建议收藏」

    主机号「建议收藏」用于识别该网络中的主机。IP地址分为五类,A类保留给政府机构,B类分配给中等规模的公司,C类分配给任何需要的人,D类用于组播,E类用于实验,各类可容纳的地址数目不同。A、B、C三类IP地址的特征:

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号