为您推荐:
精华内容
最热下载
问答
  • 要了解HashMap底层实现原理,我们首先要对HashMap的部分底层源码进行分析 public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable 我们可以...

    要了解HashMap的底层实现原理,我们首先要对HashMap的部分底层源码进行分析

    public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable

    我们可以看出HashMap继承了AbstractMap,实现了Map,Cloneable,Serializable接口。

     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    HashMap的默认初始容量(必须是2的幂),它的值是1左移4位,也就是16

    static final int MAXIMUM_CAPACITY = 1 << 30;

    HashMap的最大容量,如果任何一个带参数的构造函数指定了较大的值,就会使用它来比较,而且值必须是2的幂,并且小于1左移30位,2的30次方,也就是1073741824

     static final float DEFAULT_LOAD_FACTOR = 0.75f;

    HashMap默认的加载因子,因为从上可知,HashMap的默认初始容量是16,当HashMap的实际容量达到16*0.75,就是12,HashMap会自动扩容。

      static final int TREEIFY_THRESHOLD = 8;

    HashMap底层链表转换成红黑树的临界值,当链表的长度大于8时,会自动转化成红黑树。

    static final int UNTREEIFY_THRESHOLD = 6;

    HashMap底层红黑树转化成链表的临界值,当红黑树的长度小于6时,红黑树又会自动转换成链表。

    static final int MIN_TREEIFY_CAPACITY = 64;

    HashMap转化成树结构的最小容量,因为HashMap底层时数组+链表+红黑树实现的,HashMap的容量大于64时,会自动转换成树结构,也就是数组的长度大于64时,也会转换成红黑树。


    以下是HashMap的静态内部类

    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;//若放入的节点key的hash值(若key所在的类未进行重写hash()方法的重写,则为Object的hash()方法) 定义数组索引的位置
            final K key;//放入节点的key
            V value;//放入节点的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) {
                   // 判断key和value是否都相等
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                  // 如果key和value都相等,就返回true
                        return true;
                }
                   // 如果key或者value不相等,就返回false
                return false;
            }
        }
    

    继续往下看

    static final int hash(Object key) { // 计算key的hash值
        int h;
        // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    static Class<?> comparableClassFor(Object x) {
        // 1.判断x是否实现了Comparable接口
        if (x instanceof Comparable) {
            Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
            // 2.校验x是否为String类型
            if ((c = x.getClass()) == String.class) // bypass checks
                return c;
            if ((ts = c.getGenericInterfaces()) != null) {
                // 3.遍历x实现的所有接口
                for (int i = 0; i < ts.length; ++i) {
                    // 4.如果x实现了Comparable接口,则返回x的Class
                    if (((t = ts[i]) instanceof ParameterizedType) &&
                        ((p = (ParameterizedType)t).getRawType() ==
                         Comparable.class) &&
                        (as = p.getActualTypeArguments()) != null &&
                        as.length == 1 && as[0] == c) // type arg is c
                        return c;
                }
            }
        }
        return null;
    }

        /**
         * HashMap的成员变量数组
         */
        transient Node<K,V>[] table;
    
        /**
         * 存储的是entrySet,其实里面的每个元素就是HashMap的每个节点
         */
        transient Set<Map.Entry<K,V>> entrySet;
    
        /**
         * HashMap中已存元素的个数 size
         */
        transient int size;
    
        /**
         * HashMap被修改的次数 put remove 操作的次数
         */
        transient int modCount;
    
        //阈值 capacity*loadFactor 或者是将要初始化扩容的容量值
        int threshold;
    
        /**
         * 负载因子
         */
        final float loadFactor;
    

    简单看一下底层源码,我们可以做出以下总结:

    HashMap的初始容量是16,默认加载因子是0.75,扩容按照原始容量的2倍扩容,可以存储null值和null键,因为没有加锁,当多个线程同时操作一个hashmap就可能出现不安全的情况,所以线程也是不安全的,底层是由数组+链表+红黑树实现。

    当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度大于8时,链表就转换为红黑树,以及当数组的长度大于64时,也会自动转换成红黑树,这样大大提高了查找的效率。

    通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,就把Node(节点)添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着key和链表上每个节点的key进行equals。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals的结果返回了true,那么这个节点的value将会被覆盖。

    展开全文
    wenkezhuangyuan 2021-08-02 17:09:33
  • 一:HashMap底层实现原理解析 我们常见的有数据结构有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点: 1、数组结构: 存储区间连续、内存占用严重、空间复杂度大 优点:...

    一:HashMap底层实现原理解析

    我们常见的有数据结构有三种结构:1、数组结构 2、链表结构 3、哈希表结构 下面我们来看看各自的数据结构的特点:
    1、数组结构: 存储区间连续、内存占用严重、空间复杂度大

    • 优点:随机读取和修改效率高,原因是数组是连续的(随机访问性强,查找速度快)
    • 缺点:插入和删除数据效率低,因插入数据,这个位置后面的数据在内存中都要往后移动,且大小固定不易动态扩展。

    2、链表结构:存储区间离散、占用内存宽松、空间复杂度小

    • 优点:插入删除速度快,内存利用率高,没有固定大小,扩展灵活
    • 缺点:不能随机查找,每次都是从第一个开始遍历(查询效率低)

    3、哈希表结构:结合数组结构和链表结构的优点,从而实现了查询和修改效率高,插入和删除效率也高的一种数据结构
    常见的HashMap就是这样的一种数据结构
    在这里插入图片描述

    HashMap中的put()和get()的实现原理

    • 1、map.put(k,v)实现原理
      (1)首先将k,v封装到Node对象当中(节点)。
      (2)然后它的底层会调用K的hashCode()方法得出hash值。
      (3)通过哈希表函数/哈希算法,将hash值转换成数组的下标,下标位置上如果没有任何元素,就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false,那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true,那么这个节点的value将会被覆盖。
    • 2、map.get(k)实现原理
      (1)先调用k的hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。
      (2)通过上一步哈希算法转换成数组的下标之后,在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有,则返回null。如果这个位置上有单向链表,那么它就会拿着K和单向链表上的每一个节点的K进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的K和参数K进行equals返回true,那么此时该节点的value就是我们要找的value了,get方法最终返回这个要找的value。

    为何随机增删、查询效率都很高的原因是?
    原因: 增删是在链表上完成的,而查询只需扫描部分,则效率高。

    HashMap集合的key,会先后调用两个方法,hashCode and equals方法,这这两个方法都需要重写。

    为什么放在hashMap集合key部分的元素需要重写equals方法?
    因为equals方法默认比较的是两个对象的内存地址

    二:HashMap红黑树原理分析

    相比 jdk1.7 的 HashMap 而言,jdk1.8最重要的就是引入了红黑树的设计,当hash表的单一链表长度超过 8 个的时候,链表结构就会转为红黑树结构。
    为什么要这样设计呢?好处就是避免在最极端的情况下链表变得很长很长,在查询的时候,效率会非常慢。
    在这里插入图片描述

    • 红黑树查询:其访问性能近似于折半查找,时间复杂度 O(logn);
    • 链表查询:这种情况下,需要遍历全部元素才行,时间复杂度 O(n);

    简单的说,红黑树是一种近似平衡的二叉查找树,其主要的优点就是“平衡“,即左右子树高度几乎一致,以此来防止树退化为链表,通过这种方式来保障查找的时间复杂度为 log(n)。
    在这里插入图片描述
    关于红黑树的内容,网上给出的内容非常多,主要有以下几个特性:

    • 1、每个节点要么是红色,要么是黑色,但根节点永远是黑色的;

    • 2、每个红色节点的两个子节点一定都是黑色;

    • 3、红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色);

    • 4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点;

    • 5、所有的叶节点都是是黑色的(注意这里说叶子节点其实是上图中的 NIL 节点);

    在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件 3 或条件 4,需要通过调整使得查找树重新满足红黑树的条件。

    展开全文
    qq_43370771 2020-12-18 10:37:27
  • hashmap是我们开发中用的最常见的集合之一,但是我们是否有了解过他的底层呢?这篇文章我将带您了解一下hashmap的底层 ...在学习hashmap底层原理的时候,我们必须要掌握位运算,别问为什么,往下面看自然知晓 ...

    hashmap是我们开发中用的最常见的集合之一,但是我们是否有了解过他的底层呢?这篇文章我将带您了解一下hashmap的底层

    位运算

    在学习hashmap底层原理的时候,我们必须要掌握位运算,别问为什么,往下面看自然知晓

    我们知道,计算机用的是二进制,也就是010101…这样的字符,当我们输入某一个数字的时候,存入计算机里面的也是二进制譬如说

    • 0-》00000000
    • 1-》00000001
    • 2-》00000010
    • 3-》00000011

    &(按位与)

    参加运算的两个二进制数,同时为1,才为1,否则为0。举例 3&5=1。

    在这里插入图片描述

    |(按位或)

    参加运算的两个二进制数,一个为1就为1,否则为0。2 | 4=6

    在这里插入图片描述

    ^(按位异或)

    参加运算的两个二进制数,位不同则为1,位相同则为0。6^7=1

    在这里插入图片描述

    << (左位移运算符)

    将二进制码整体左移指定位数,左移后空出来的位用“0”填充,例如 -5 << 2 = -20

    例如:2<<4
    00000010->00100000=16

    “>>”(右位移运算符)与 >>(无符号右位移运算符)

    例如:16>>4
    00100000->00000010=2

    好了,现在了解了位运算,那么我们来了解一下hashmap

    hashmap的概述

    • HashMap 基于哈希表的 Map 接口实现,是以 key-value 存储形式存在,即主要用来存放键值对。
    • HashMap 的实现不是同步的,这意味着它不是线程安全的。它的 key、value 都可以为 null,此外,HashMap中的映射不是有序的。
    • jdk1.8 之前 HashMap 由 数组 + 链表 组成,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突(两个对象调用的hashCode 方法计算的哈希值经哈希函数算出来的地址被别的元素占用)而存在的(“拉链法”解决冲突)。
    • jdk1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为 8 )并且当前数组的长度大于 64时,此时此索引位置上的所有数据改为使用红黑树存储。

    HashMap 特点:

    • 存储无序;
    • 键和值位置都可以是 null,但是键位置只能存在一个 null;
    • 键位置是唯一的,是由底层的数据结构控制的;
    • jdk1.8 前数据结构是链表+数组,jdk1.8 之后是链表+数组+红黑树;
    • 阈值(边界值)> 8 并且桶位数(数组长度)大于 64,才将链表转换为红黑树,变为红黑树的目的是为了高效的查询;

    HashMap存储数据的过程

    测试代码

     public static void main(String[] args) {
            HashMap map=new HashMap();
            map.put("student1","萧炎");
            map.put("student2","林动");
            map.put("student3","牧尘");
            map.put("student4","古尘沙");
            System.out.println(map);
        }
    

    结果

    在这里插入图片描述

    执行流程分析:

    • 首先程序读到HashMap map=new HashMap();的时候,并不会马上创建一个数组,而是在我们第一次使用hashmap自己的put方法的时候,创建一个长度为16的数组,也叫作桶Node[]table ,这个用来存储数据

    • 当我们需要存入一个数据,比方说(key=a,value=3),首先会先调用重写的String的hashcode方法,计算出对应的hash数值,然后根据数组的长度和某种算法,找到这组数据应该对应的桶位数,就是数组的下标,例如0,1,2,3,4,5…然后查看这个桶里面是否有存其他的数据,如果没有,那么就直接把数据存入桶中,我们加入这一次存在‘3’这个位置
      在这里插入图片描述

    • 当我们又再一次的调用put方法,存入(key=b,value=4)的时候,假设这次算出来的又是存在三号位,这个时候,三号位已经有一个数据了,这个时候会判断两个数据的hash值是否相同,如果不相同,那我们这个时候就会在这个桶下生成一个链表,用来存储数据,这个叫做拉链法

    • 如果相同的话则会对两个数据进行一次判断
      数据相同:直接覆盖
      数据不同:从该桶位的链表开始,一直往下比,直到出现不同的时候,便存在不同的地方的下一个位置,如果这个时候链表长度超过了8,那么链表就会转化成红黑树

    • 在不断的添加新数据的时候,如果某一时刻超过了阈值,并且那个时候要存入数据的地方刚好不为空,那么,我们就要扩容了,每次扩容都是在原来的基础上,扩大2倍,原因后面会讲。

    在这里插入图片描述

    jdk1.8 中引入红黑树的进一步原因:

    1. jdk1.8 以前 HashMap 的实现是数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有n个元素,遍历的时间复杂度就是O(n),完全失去了它的优势。
    2. 针对这种情况,jdk1.8 中引入了红黑树(查找时间复杂度为 O(logn))来优化这个问题。当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。

    在这里插入图片描述

    HashMap继承体系

    在这里插入图片描述
    从继承体系可以看出:

    • HashMap 实现了Cloneable接口,可以被克隆。
    • HashMap 实现了Serializable接口,属于标记性接口,HashMap 对象可以被序列化和反序列化。
    • HashMap 继承了AbstractMap,父类提供了 Map 实现接口,具有Map的所有功能,以最大限度地减少实现此接口所需的工作。

    存储结构

    在这里插入图片描述
    在Java中,HashMap的实现采用了(数组 + 链表 + 红黑树)的复杂结构,数组的一个元素又称作
    在添加元素时,会根据hash值算出元素在数组中的位置,如果该位置没有元素,则直接把元素放置在此处,如果该位置有元素了,则把元素以链表的形式放置在链表的尾部。
    当一个链表的元素个数达到一定的数量(且数组的长度达到一定的长度)后,则把链表转化为红黑树,从而提高效率。
    数组的查询效率为O(1),链表的查询效率是O(k),红黑树的查询效率是O(log k),k为桶中的元素个数,所以当元素数量非常多的时候,转化为红黑树能极大地提高效率。

    HashMap基本属性与常量

    基本属性,常量一览

    /*
     * 序列化版本号
     */
    private static final long serialVersionUID = 362498820763181265L;
    
    /**
     * HashMap的初始化容量(必须是 2 的 n 次幂)默认的初始容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    /**
     * 最大的容量为2的30次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
     * 默认的装载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * 树化阈值,当一个桶中的元素个数大于等于8时进行树化
     */
    static final int TREEIFY_THRESHOLD = 8;
    
    /**
     * 树降级为链表的阈值,当一个桶中的元素个数小于等于6时把树转化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /**
     * 当桶的个数达到64的时候才进行树化
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    /**
     * Node数组,又叫作桶(bucket)
     */
    transient Node<K,V>[] table;
    
    /**
     * 作为entrySet()的缓存
     */
    transient Set<Map.Entry<K,V>> entrySet;
    
    /**
     * 元素的数量
     */
    transient int size;
    
    /**
     * 修改次数,用于在迭代的时候执行快速失败策略
     */
    transient int modCount;
    
    /**
     * 当桶的使用数量达到多少时进行扩容,threshold = capacity * loadFactor
     */
    int threshold;
    
    /**
     * 装载因子
     */
    final float loadFactor;
    
    
    • 容量:容量为数组的长度,亦即桶的个数,默认为16 ,最大为2的30次方,当容量达到64时才可以树化。
    • 装载因子:装载因子用来计算容量达到多少时才进行扩容,默认装载因子为0.75。
    • 树化:树化,当容量达到64且链表的长度达到8时进行树化,当链表的长度小于6时反树化。

    Hashmap属性解释

    DEFAULT_INITIAL_CAPACITY

    集合的初始化容量(必须是 2 的 n 次幂):

    // 默认的初始容量是16	1 << 4 相当于 1*2的4次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    

    提问:为什么是2的次幂呢?如果输入值不是 2 的幂比如 10 会怎么样?

     /**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
    
    • HashMap 构造方法可以指定集合的初始化容量大小,根据上述讲解我们已经知道,当向 HashMap 中添加一个元素的时候,需要根据 keyhash 值,去确定其在数组中的具体位置。HashMap 为了存取高效,减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现的关键就在把数据存到哪个链表中的算法。
    • 这个算法实际就是取模,hash % length,而计算机中直接求余效率不如位移运算。所以源码中做了优化,使用 hash & (length - 1),而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是2 的 n 次幂。(这段话是摘抄传智播客锁哥的,这个解释确实很完美!)

    例如,数组长度为 8 的时候,3 & (8 - 1) = 3,2 & (8 - 1) = 2,桶的位置是(数组索引)3和2,不同位置上,不碰撞。
    再来看一个数组长度(桶位数)不是2的n次幂的情况:

    数组长度为9 hash为3

    00000011 3
    00001000 8
    ————————
    00000000 0

    数组长度为9 hash为5

    00000101 5
    00001000 8
    ————————
    00000000 0

    数组长度为9,hash为6

    00000101 5
    00001000 8
    ————————
    00000000 0

    由此可见,如果不是2的次幂,hash值很容易一模一样,这样会经常产生哈希碰撞,导致性能下降,所以,这里采用的是2的次幂

    为什么要用2的次幂小结:

    • 由上面可以看出,当我们根据key的hash确定其在数组的位置时,如果n为2的幂次方,可以保证数据的均匀插入,如果n不是2的幂次方,可能数组的一些位置永远不会插入数据,浪费数组的空间,加大hash冲突。
    • 另一方面,一般我们可能会想通过%求余来确定位置,这样也可以,只不过性能不如&运算。而且当n是2的幂次方时: hash & (length1) == hash % length
    • 因此,HashMap容量为2次幂的原因,就是为了数据的的均匀分布,减少hash冲突,毕竟hash冲突越大,代表数组中一个链的长度越大,这样的话会降低hashmap的性能

    如果创建HashMap对象时,输入的数组长度length是10,而不是2的n次幂会怎么样呢?

    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;
        }
    

    这里HashMap会采用一个tableSizeFor()方法,通过这个方法,把数组长度设置成最接近自己输入数组长度数量的2的次幂的数量例如如果我输入10,最后返回的就是16,我输入5,那么返回的便是8,我们复制一下这个方法,自己测试 一下

    public class Test01 {
        public static void main(String[] args) {
            System.out.println(tableSizeFor(12));
        }
    
        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 + 1;
        }
    }
    
    

    int n = cap - 1;为什么要减去1呢?

    防止 cap 已经是 2 的幂。如果 cap 已经是 2 的幂,又没有这个减 1 操作,则执行完后面的几条无符号操作之后,返回的 capacity 将是这个 cap 的 2 倍(后面还会再举个例子讲这个)。

    最后为什么有个 n + 1 的操作呢?

    如果 n 这时为 0 了(经过了cap - 1后),则经过后面的几次无符号右移依然是 0,返回0是肯定不行的,所以最后返回n+1最终得到的 capacity 是1。
    注意:容量最大也就是 32bit 的正数,因此最后 n |= n >>> 16;最多也就 32 个 1(但是这已经是负数了,在执行 tableSizeFor 之前,对 initialCapacity 做了判断,如果大于MAXIMUM_CAPACITY(2 ^ 30),则取 MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY,会执行位移操作。所以这里面的位移操作之后,最大 30 个 1,不会大于等于 MAXIMUM_CAPACITY。30 个 1,加 1 后得 2 ^ 30)。

    完整例子

    在这里插入图片描述

    DEFAULT_LOAD_FACTOR

    负载因子:默认为0.75

    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    

    MAXIMUM_CAPACITY

    static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次幂
    
    

    集合最大容量:为2的30次方

    TREEIFY_THRESHOLD

    当桶(bucket)上的结点数大于这个值时会转为红黑树

    // 当桶(bucket)上的结点数大于这个值时会转为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    

    为什么 Map 桶中结点个数超过 8 才转为红黑树?

    8这个阈值定义在HashMap中,针对这个成员变量,在源码的注释中只说明了 8 是 bin( bucket 桶)从链表转成树的阈值,但是并没有说明为什么是 8。

    在 HashMap 中有一段注释说明:

    Because TreeNodes are about twice the size of regular nodes, we use them only when bins
    contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too
    small (due to removal or resizing) they are converted back to plain bins.  In usages with
    well-distributed user hashCodes, tree bins are rarely used.  Ideally, under random hashCodes, 
    the frequency of nodes in bins follows a Poisson distribution 
    (http://en.wikipedia.org/wiki/Poisson_distribution) 
    with a parameter of about 0.5 on average for the default resizing
    threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, 
    the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The first values are:
    
    翻译:因为树结点的大小大约是普通结点的两倍,所以我们只在箱子包含足够的结点时才使用树结点(参见TREEIFY_THRESHOLD)。
    当它们变得太小(由于删除或调整大小)时,就会被转换回普通的桶。在使用分布良好的用户 hashCode 时,很少使用树箱。
    理想情况下,在随机哈希码下,箱子中结点的频率服从泊松分布。
    默认调整阈值为0.75,平均参数约为0.5,尽管由于调整粒度的差异很大。忽略方差,列表大小k的预朗出现次数是(exp(-0.5)*pow(0.5, k) / factorial(k)
    第一个值是:
    
    0:    0.60653066
    1:    0.30326533
    2:    0.07581633
    3:    0.01263606
    4:    0.00157952
    5:    0.00015795
    6:    0.00001316
    7:    0.00000094
    8:    0.00000006
    more: less than 1 in ten million
    
    

    一句话概括:
    hashCode 算法下所有 桶 中结点的分布频率会遵循泊松分布,这时一个桶中链表长度超过 8 个元素的槪率非常小,权衡空间和时间复杂度,所以选择 8 这个数宇。

    UNTREEIFY_THRESHOLD

    当链表长度低于6会从红黑树转化成链表

    // 当桶(bucket)上的结点数小于这个值,树转为链表 
    static final int UNTREEIFY_THRESHOLD = 6;
    
    

    MIN_TREEIFY_CAPACITY

    当 Map 里面的数量超过这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4*TREEIFY_THRESHOLD(8)

    // 桶中结构转化为红黑树对应的数组长度最小的值 
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    

    table(重点)

    table 用来初始化(必须是二的n次幂)

    // 存储元素的数组 
    transient Node<K,V>[] table;
    
    

    在 jdk1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构,其中 table 就是 HashMap 中的数组,jdk8 之前数组类型是 Entry<K,V> 类型。从 jdk1.8 之后是 Node<K,V> 类型。只是换了个名字,都实现了一样的接口:Map.Entry<K,V>。负责存储键值对数据的。

    entrySet

    用来放缓存

    // 存放具体元素的集合
    transient Set<Map.Entry<K,V>> entrySet;
    
    

    size(重点)

    HashMap 中存放元素的个数

    // 存放元素的个数,注意这个不等于数组的长度
     transient int size;
    
    

    size 为 HashMap 中 K-V 的实时数量,不是数组 table 的长度。

    modCount

    用来记录 HashMap 的修改次数

    // 每次扩容和更改 map 结构的计数器
     transient int modCount;  
    
    

    threshold(重点)

    用来调整大小下一个容量的值计算方式为(容量*负载因子)

    // 临界值 当实际大小(容量*负载因子)超过临界值时,会进行扩容
    int threshold;
    
    

    loadFactor(重点)

    哈希表的负载因子

    // 负载因子
    final float loadFactor;// 0.75f
    
    

    说明:

    • oadFactor 是用来衡量 HashMap 满的程度,表示HashMap的疏密程度,影响 hash 操作到同一个数组位置的概率,计算HashMap 的实时负载因子的方法为:size/capacity,而不是占用桶的数量去除以 capacity。capacity是桶的数量,也就是 table 的长度 length。
    • loadFactor 太大导致查找元素效率低,太小导致数组的利用率低,存放的数据会很分散。loadFactor 的默认值为 0.75f是官方给出的一个比较好的临界值。
    • 当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时,表示 HashMap
      太挤了,需要扩容,而扩容这个过程涉及到 rehash、复制数据等操作,非常消耗性能。所以开发中尽量减少扩容的次数,可以通过创建HashMap 集合对象时指定初始容量来尽量避免。
    • 在 HashMap 的构造器中可以定制 loadFactor。
    // 构造方法,构造一个带指定初始容量和负载因子的空HashMap
    HashMap(int initialCapacity, float loadFactor);
    
    

    为什么负载因子loadFactor 设置为0.75,初始化临界值threshold是12?

    loadFactor 越趋近于1,那么 数组中存放的数据(entry)也就越多,也就越密,也就是会让链表的长度增加,loadFactor 越小,也就是趋近于0,数组中存放的数据(entry)也就越少,也就越稀疏。
    在这里插入图片描述
    如果希望链表尽可能少些,要提前扩容。有的数组空间有可能一直没有存储数据,负载因子尽可能小一些。

    例举:

    例如:负载因子是0.4。 那么16*0.4--->6 如果数组中满6个空间就扩容会造成数组利用率太低了。
    	 负载因子是0.9。 那么16*0.9--->14 那么这样就会导致链表有点多了,导致查找元素效率低。
    
    

    所以既兼顾数组利用率又考虑链表不要太多,经过大量测试 0.75 是最佳方案。

    threshold 计算公式:capacity(数组长度默认16) * loadFactor(负载因子默认0.75)==12。

    这个值是当前已占用数组长度的最大值。当 Size >= threshold(12) 的时候,那么就要考虑对数组的 resize(扩容),也就是说,这个的意思就是 衡量数组是否需要扩增的一个标准。 扩容后的 HashMap 容量是之前容量的两倍。

    HashMap扩容机制

     /**
         * Initializes or doubles table size.  If null, allocates in
         * accord with initial capacity target held in field threshold.
         * Otherwise, because we are using power-of-two expansion, the
         * elements from each bin must either stay at same index, or move
         * with a power of two offset in the new table.
         *
         * @return the table
         */
        final Node<K,V>[] resize() {
            //把旧的table 赋值个一个变量
            Node<K,V>[] oldTab = table;
            //获取旧的tabel的长度
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 旧的阈值
            int oldThr = threshold;
            int newCap, newThr = 0;
        
            if (oldCap > 0) {
                //判断数组的长度是否大约等于最大值
                if (oldCap >= MAXIMUM_CAPACITY) {
                    //如果数组的长度达到了最大值,那么就不在进行扩容,直接返回,不管了任由hash冲突
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                //把旧的数组长度左移一位(也就是乘以2),然后判断是否小于最大值,并且判断旧的数组长度是否大于等于默认的长度16
                }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    //如果条件成立就把旧的阈值左移一位复制给新的阈值
                    newThr = oldThr << 1; // double threshold
            }//如果就的数组长度小于0并且旧的阈值大于0
            else if (oldThr > 0) // initial capacity was placed in threshold
                //就把旧的阈值赋值给新的数组长度(初始化新的数组长度)
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                //使用默认值 
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //如果新的阈值等于0
            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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            //已完成新的数组扩容,开始把就的数据移动到新的数组中,通过循环遍历
            if (oldTab != null) {
                for (int j = 0; j < oldCap; ++j) {
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        //如果没有子元素那么说明是下面不是一个链表,直接通过 hash&(新的数组长度-1)计算出新的位置,把就的数据放入新的位置
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        //如果该节点为红黑树结构,就进行树的操作
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            //有多个数据并且不是树那么该节点上放的是链表
                            //这里是java1.8很精妙的地方,如果 e.hash& 旧的数组长度 如果等于0
                            那么该数据的位置没有发生变化,还在原来的索引位置上,如果不等于0 那么就在该值就在 (原来的索引位置+旧的数组长度)的位置上,
                            这里重新创建了两个节点,在原来位置上的放入loHead中,在新的位置上的放入
    hiHead 中,最后把这两组数据放入新的数组中即可。(这里的精妙之处是不用重新计算每一个数据的hash,就可以把旧的数据放入新的数组中去)
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            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;
        }
    

    在这里插入图片描述

    内部类

    Node内部类

    Node是一个典型的单链表节点,其中,hash用来存储key计算得来的hash值。

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;// hash用来存储key计算得来的hash值
        final K key;// 键
        V value;// 值
        Node<K,V> next;// 下一个node节点
        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() {// 调用底层c++ 返回Key/Value的哈希码值,如果此对象为null,则返回0
            return Objects.hashCode(key) ^ Objects.hashCode(value);// 将Key/Vaule
        }
        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;
        }
    }
    
    

    HashMap构造方法

    HashMap()

    构造一个空的HashMap,默认初始容量(16)和默认负载因子(0.75)。

    public HashMap() {
       // 将默认的负载因子0.75赋值给loadFactor,并没有创建数组
       this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }
    
    

    HashMap(int initialCapacity)

    构造一个具有指定的初始容量和默认负载因子(0.75)HashMap 。

    // 指定“容量大小”的构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    

    HashMap(int initialCapacity,float loadFactor)构造方法

    构造一个具有指定的初始容量和负载因子的 HashMap。

    /*
    	 指定“容量大小”和“负载因子”的构造函数
    	 initialCapacity:指定的容量
    	 loadFactor:指定的负载因子
    */
    public HashMap(int initialCapacity, float loadFactor) {
        	// 判断初始化容量initialCapacity是否小于0
            if (initialCapacity < 0)
                // 如果小于0,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        	// 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
            if (initialCapacity > MAXIMUM_CAPACITY)
                // 如果超过MAXIMUM_CAPACITY,会将MAXIMUM_CAPACITY赋值给initialCapacity
                initialCapacity = MAXIMUM_CAPACITY;
        	// 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                // 如果满足上述其中之一,则抛出非法的参数异常IllegalArgumentException
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
         	// 将指定的负载因子赋值给HashMap成员变量的负载因子loadFactor
            this.loadFactor = loadFactor;// 一般不建议修改默认的负载因子
            this.threshold = tableSizeFor(initialCapacity);
        }
    	// 最后调用了tableSizeFor,来看一下方法实现:
         /*
         	返回比指定cap容量大的最小2的n次幂数:
         	前面第一遍讲述的应该有些小伙伴难以理解,这里我在举例解析一下:
         	-------------------------------------------------------
         	首先假定传入的cap = 10
         	则,n = 10 -1 => 9
         	n |= n >>> 1 就等同于 n = (n | n >>> 1),所以:
         	(位运算不懂的可以去看我的《Java基础提高之位运算》这篇文章)
         	9 => 0b1001    9 >>> 1 => 0b0100 
         	n |= n >>> 1;  ===>  0b1001 | 0b0100 => 0b1101
         	n |= n >>> 2;  ===>  0b1101 | 0b0011 => 0b1111
            n |= n >>> 4;  ===>  0b1111 | 0b0000 => 0b1111
            n |= n >>> 8;  ===>  0b1111 | 0b0000 => 0b1111
            n |= n >>> 16; ===>  0b1111 | 0b0000 => 0b1111
            得到:
            0b1111 => 15
            返回:
            return 15 + 1 => 16
            -------------------------------------------------------
            如果cap 不减去1,即直接使n等于cap的话,int n = cap;
            我们继续用上边返回的cap => 16 传入tableSizeFor(int cap):
            
            cap = 16
            n = 16
            16 => 0b10000  16 >>> 1 => 0b01000
            n |= n >>> 1;  ===>  0b10000 | 0b01000 => 0b11000
            n |= n >>> 2;  ===>  0b11000 | 0b00110 => 0b11110
            n |= n >>> 4;  ===>  0b11110 | 0b00001 => 0b11111
            n |= n >>> 8;  ===>  0b11111 | 0b00000 => 0b11111
            n |= n >>> 16; ===>  0b11111 | 0b00000 => 0b11111
            得到:
            0b11111 => 31
            返回 return 31 +1 => 32
            
            而实际情况是应该传入cap = 16 , n = cap -1 = 15
            15 => 0b1111 
            
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            经过上面运算后得到:还是15
            
            返回结果:
            return 15 + 1 = 16
            所以我们得出结果:
            防止 cap 已经是 2 的幂数情况下。没有这个减 1 操作,
            则执行完几条无符号位移或位运算操作之后,返回的cap(32)将是实际所需cap(16)的 2倍。
         */
        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;
        }
    
    
    

    说明:
    对于this.threshold = tableSizeFor(initialCapacity); 疑问?
    tableSizeFor(initialCapacity)**判断指定的初始化容量是否是2的n次幂,如果不是那么会变为比指定初始化容量大的最小的2的n次幂。

    但是注意,在tableSizeFor方法体内部将计算后的数据返回给调用这里了,并且直接赋值给threshold边界值了。有些人会觉得这里是一个bug,应该这样书写:
    this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

    这样才符合threshold的意思(当HashMap的size到达threshold这个阈值时会扩容)

    但是请注意,在jdk8以后的构造方法中,并没有对table这个成员变量进行初始化,table的初始化被推迟到了put方法中,在put方法中会对threshold重新计算。

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

    包含另一个 “Map” 的构造函数

    // 构造一个映射关系与指定 Map 相同的新 HashMap。
    public HashMap(Map<? extends K, ? extends V> m) {
        	// 负载因子loadFactor变为默认的负载因子0.75
             this.loadFactor = DEFAULT_LOAD_FACTOR;
             putMapEntries(m, false);
     }
    
    

    最后调用了 putMapEntries(),来看一下方法实现:

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //获取参数集合的长度
        int s = m.size();
        if (s > 0) {//判断参数集合的长度是否大于0
            if (table == null) { // 判断table是否已经初始化
                    // 未初始化,s为m的实际元素个数
                    float ft = ((float)s / loadFactor) + 1.0F;// 得到新的扩容阈值
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// 新的扩容阈值float自动向下转型为int
                
                    // 计算得到的t大于阈值,则初始化阈值,将其变为符合要求的2的n次幂数
                    if (t > threshold)
                        threshold = tableSizeFor(t);
            }
            // 如果table已初始化过了,并且m元素个数大于阈值,进行扩容处理
            else if (s > threshold)
                resize();
            // 将m中的所有元素添加至HashMap中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 得到的key 和 value 放入 hashmap
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    
    

    注意:

    float ft = ((float)s / loadFactor) + 1.0F; 这一行代码中为什么要加 1.0F ?

    (float)s/loadFactor 的结果是小数,加 1.0F 与 (int)ft 相当于是对小数做一个向上取整以尽可能的保证更大容量,更大的容量能够减少 resize 的调用次数(为了效率,应当尽量减少扩容的次数)。所以 + 1.0F 是为了获取更大的容量。
    例如:原来集合的元素个数是 6 个,那么 6/0.75 是8,由于8是 2 的n次幂,那么
    if (t > threshold) threshold = tableSizeFor(t);执行过后,新的数组大小就是 8 了。然后原来数组的数据就会存储到长度是 8 的新的数组中了,这样会导致在存储元素的时候,容量不够,还得继续扩容,那么性能降低了,而如果 +1 呢,数组长度直接变为16了,这样可以减少数组的扩容。

    展开全文
    weixin_43145539 2021-05-24 18:25:48
  • HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的...

    ①HashMap的工作原理

    HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

    当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

    因为HashMap的好处非常多,我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java,也出于性能的考虑,我们会经常用到HashMap和ConcurrentHashMap。

    ②HashMap和Hashtable的区别

    HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。

    1. HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
    2. HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
    3. 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
    4. 由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
    5. HashMap不能保证随着时间的推移Map中的元素次序是不变的。

    要注意的一些重要术语:

    1) sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。

    2) Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图“结构上”更改集合对象,将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。

    3) 结构上的更改指的是删除或者插入一个元素,这样会影响到map的结构。

    我们能否让HashMap同步?

    HashMap可以通过下面的语句进行同步:
    Map m = Collections.synchronizeMap(hashMap);

    结论

    Hashtable和HashMap有几个主要的不同:线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable,而如果你使用Java 5或以上的话,请使用ConcurrentHashMap吧。

    ashMap和HashSet的区别是Java面试中最常被问到的问题。如果没有涉及到Collection框架以及多线程的面试,可以说是不完整。而Collection框架的问题不涉及到HashSet和HashMap,也可以说是不完整。HashMap和HashSet都是collection框架的一部分,它们让我们能够使用对象的集合。collection框架有自己的接口和实现,主要分为Set接口,List接口和Queue接口。它们有各自的特点,Set的集合里不允许对象有重复的值,List允许有重复,它对集合中的对象进行索引,Queue的工作原理是FCFS算法(First Come, First Serve)。

    首先让我们来看看什么是HashMap和HashSet,然后再来比较它们之间的分别。

    ③HashMap和HashSet的区别

    HashMap和HashSet的区别是Java面试中最常被问到的问题。如果没有涉及到Collection框架以及多线程的面试,可以说是不完整。而Collection框架的问题不涉及到HashSet和HashMap,也可以说是不完整。HashMap和HashSet都是collection框架的一部分,它们让我们能够使用对象的集合。collection框架有自己的接口和实现,主要分为Set接口,List接口和Queue接口。它们有各自的特点,Set的集合里不允许对象有重复的值,List允许有重复,它对集合中的对象进行索引,Queue的工作原理是FCFS算法(First Come, First Serve)。

    首先让我们来看看什么是HashMap和HashSet,然后再来比较它们之间的分别。

    什么是HashSet

    HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有储存相等的对象。如果我们没有重写这两个方法,将会使用这个方法的默认实现。

    public boolean add(Object o)方法用来在Set中添加元素,当元素值重复时则会立即返回false,如果成功添加的话会返回true。

    什么是HashMap

    HashMap实现了Map接口,Map接口对键值对进行映射。Map中不允许重复的键。Map接口有两个基本的实现,HashMap和TreeMap。TreeMap保存了对象的排列次序,而HashMap则不能。HashMap允许键和值为null。HashMap是非synchronized的,但collection框架提供方法能保证HashMap synchronized,这样多个线程同时访问HashMap时,能保证只有一个线程更改Map。

    public Object put(Object Key,Object value)方法用来将元素添加到map中。

    HashSet和HashMap的区别

    *HashMap**HashSet*
    HashMap实现了Map接口HashSet实现了Set接口
    HashMap储存键值对HashSet仅仅存储对象
    使用put()方法将元素放入map中使用add()方法将元素放入set中
    HashMap中使用键对象来计算hashcode值HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
    HashMap比较快,因为是使用唯一的键来获取对象HashSet较HashMap来说比较慢

     

     

    ④面试题

    HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考察的深度很深。这题经常出现在高级或中高级面试中。投资银行更喜欢问这个问题,甚至会要求你实现HashMap来考察你的编程能力。ConcurrentHashMap和其它同步集合的引入让这道题变得更加复杂。让我们开始探索的旅程吧!

    “你用过HashMap吗?” “什么是HashMap?你为什么用到它?”

    几乎每个人都会回答“是的”,然后回答HashMap的一些特性,譬如HashMap可以接受null键值和值,而Hashtable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对等等。这显示出你已经用过HashMap,而且对它相当的熟悉。但是面试官来个急转直下,从此刻开始问出一些刁钻的问题,关于HashMap的更多基础的细节。面试官可能会问出下面的问题:

    “你知道HashMap的工作原理吗?” “你知道HashMap的get()方法的工作原理吗?”

    你也许会回答“我没有详查标准的Java API,你可以看看Java源代码或者Open JDK。”“我可以用Google找到答案。”

    但一些面试者可能可以给出答案,“HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点,或者错误的认为仅仅只在bucket中存储值的话,你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确,也显示出面试者确实知道hashing以及HashMap的工作原理。但是这仅仅是故事的开始,当面试官加入一些Java程序员每天要碰到的实际场景的时候,错误的答案频现。下个问题可能是关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法:

    “当两个对象的hashcode相同会发生什么?” 从这里开始,真正的困惑开始了,一些面试者会回答因为hashcode相同,所以两个对象是相等的,HashMap将会抛出异常,或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法,并告诉他们两个对象就算hashcode相同,但是它们可能并不相等。一些面试者可能就此放弃,而另外一些还能继续挺进,他们回答“因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理,虽然有很多种处理碰撞的方法,这种方法是最简单的,也正是HashMap的处理方法。但故事还没有完结,面试官会继续问:

    “如果两个键的hashcode相同,你如何获取值对象?” 面试者会回答:当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket,他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较,你是如何确定确定找到值对象的?除非面试者直到HashMap在链表中存储的是键值对,否则他们不可能回答出这一题。

    其中一些记得这个重要知识点的面试者会说,找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。完美的答案!

    许多情况下,面试者会在这个环节中出错,因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现,而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。

    如果你认为到这里已经完结了,那么听到下面这个问题的时候,你会大吃一惊。“如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?”除非你真正知道HashMap的工作原理,否则你将回答不出这道题。默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

    如果你能够回答这道问题,下面的问题来了:“你了解重新调整HashMap大小存在什么问题吗?”你可能回答不上来,这时面试官会提醒你当多线程的情况下,可能产生条件竞争(race condition)。

    当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?:)

    热心的读者贡献了更多的关于HashMap的问题:

      1. 为什么String, Interger这样的wrapper类适合作为键? String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。
      2. 我们可以使用自定义的对象作为键吗? 这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
      3. 我们可以使用CocurrentHashMap来代替Hashtable吗?这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。看看这篇博客查看Hashtable和ConcurrentHashMap的区别。
    展开全文
    suifeng629 2018-08-29 11:00:56
  • fengxi_tan 2020-06-08 22:27:12
  • weixin_49822811 2021-02-13 22:41:16
  • qq_38362274 2020-04-08 21:31:08
  • qq_23609603 2020-06-10 21:36:53
  • tuke_tuke 2016-06-05 11:13:44
  • chinese_zhang 2020-03-30 17:23:05
  • weixin_48929324 2021-01-02 17:27:00
  • qq_41345773 2019-06-15 10:14:34
  • qq_32711309 2019-08-21 15:47:27
  • MDreamlove 2018-05-16 10:38:40
  • qq_39685066 2020-07-28 18:02:41
  • qq_36388734 2019-08-01 07:59:19
  • qq_45055856 2019-08-02 22:03:56

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,983
精华内容 15,193
关键字:

hashmap底层实现原理put