www.adminn.cn
站长正能量分享网!

Java中的HashMap

AD:阿里云服务器企业会员更优惠 腾讯云香港,韩国免备案服务器1.8折优惠

想必经历过面试的人很多都能被问到这个问题,当然小编也不例外,今天就给大家剖析一下HashMap在jdk1.8中的结构及其使用,分享在这,从中自己也在学习,不断积累技术和大家一起分享。

一:概述

       HashMap最早在jdk1.2中就存在了,HashMap继承自父类(AbstractMap),实现了Map、Cloneable、Serializable接口,底层思想是基于散列算法实现的,HashMap可以用null作为键,也可以用null作为值,当存储的键为null时,对应计算的结果是0,用0作为键值的,HashMap不是线程安全的,如果使用HashMap要满足线程安全,可以使用Collectio类的的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap类。

一:数据的存储结构

      在jdk1.7中的HashMap中的数据结构是数组+单链表的组合,使用链表处理hash值冲突的元素,而存在的问题就是当hash键值相等的情况较多时,都会将值保存在一个单链表上,也就是其中的一个桶中,导致通过key值去查找效率很低,所以在jdk1.8中,HashMap采用了数组+链表+红黑树来实现,这在结构上与jdk 1.7最大的不同,而在jdk1.8中,如果hash键值冲突较多时,单链表的长度超过规定的临界值(8)时,就会将链表转换成红黑树的结构存储,这样就能高效的查询,提高HashMap的查询效率。

       1. HashMap成员变量:   

             * The default initial capacity – MUST be a power of two.

             *  默认HashMap初始化的容量为16,且长度必须为2的幂等

             */

            static final int DEFAULT_INITIAL_CAPACITY = 16;

 /**

     * The table, resized as necessary. Length MUST Always be a power of two.

                * 数组是存储HashMap的链表表头

     */

    transient Entry<K,V>[] table;

        /** 最大初始容量,2^30 */            static final int MAXIMUM_CAPACITY = 1 << 30;           /** 负载因子,默认0.75,负载因子越小,hash冲突机率越低 */          static final float DEFAULT_LOAD_FACTOR = 0.75f;    /** 初始化一个Entry的空数组 */     static final Entry<?,?>[] EMPTY_TABLE = {};        /** HashMap实际存储的元素个数 */        transient int size;          /** 临界值(HashMap 实际能存储的大小),公式为(threshold = capacity * loadFactor) */    int threshold;

    /** 负载因子 */

         final float loadFactor; /** HashMap的结构被修改的次数,用于迭代器 */

         transient int modCount;

2:HashMap的数组结构

图1

3:红黑树结构及性质介绍

     红黑树其实就是一种自平衡的二叉查找树,他这个自平衡的特性就是针对HashMap中链表可能会很长,做出的优化。红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找中有的性质外,红黑树也有自己的特点:

特点1. 节点都是红色或黑色,所以称为红黑树。

特点2. 树的根节点是黑色。

特点3. 每个叶节点(NIL节点,空节点)是黑色的。

特点4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

特点5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {     TreeNode<k,v> parent;  // 父节点     TreeNode<k,v> left; //左子树     TreeNode<k,v> right;//右子树     TreeNode<k,v> prev;    // needed to unlink next upon deletion     boolean red;    //颜色属性     TreeNode(int hash, K key, V val, Node<k,v> next) {         super(hash, key, val, next); 

    } 

4:HashMap的扩容机制

     HashMap中含有resize()方法,当HashMap的元素个数超过数组的容量长度(length)HashMap就会进行扩容,默认情况下数组容量是16,当HashMap中的元素个数超过12个时(16*0.75 == 12),就超过了临界值(也就是源码中的threshold),这时,HashMap就需要把数组大小扩容到原来的一倍,然后通过rehash(再哈希),重新计算每个元素在数组中的位置.

模板优惠价: (点击购买)
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《Java中的HashMap》
文章链接:https://www.adminn.cn/news/785.html
本站资源模板仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。2021.5月起,网站调整,暂不再分享免费模板。谢谢理解

本站源码仅供本地环境下学习借鉴研究使用!

源码请勿用于任何涉灰站点!净化网络,站长更有责!

支付宝扫一扫打赏