HashMap原理(三)

阅读:231

目录介绍

  • 01.容量和装载因子
  • 02.HashTable和HashMap
  • 03.hashCode和equal
  • 04.Key为何需要不可变
  • 05.HashMap为啥要扩容
  • 06.HashMap的table下标

01.容量和装载因子

  • 在HashMap中有两个很重要的参数,容量(Capacity)和负载因子(Load factor)
    • 简单的说,Capacity就是bucket的大小,Loadfactor就是bucket填满程度的最大比例。
    • 如果对迭代性能要求很高的话,不要把capacity设置过大,也不要把load factor设置过小。
    • 当bucket中的entries的数目大于capacity*load factor时就需要调整bucket的大小为当前的2倍。
  • 什么是装载因子
    • 装载因子用于规定数组在自动扩容之前可以数据占有其容量的最高比例,即当数据量占有数组的容量达到这个比例后,数组将自动扩容。
    • 装载因子衡量的是一个散列表的空间的使用程度,装载因子越大表示散列表的装填程度越高,反之愈小。因此如果装载因子越大,则对空间的利用程度更高,相对应的是查找效率的降低。
    • 如果装载因子太小,那么数组的数据将过于稀疏,对空间的利用率低,官方默认的装载因子为0.75,是平衡空间利用率和运行效率两者之后的结果。
    • 如果在实际情况中,内存空间较多而对时间效率要求很高,可以选择降低装载因子的值;如果内存空间紧张而对时间效率要求不高,则可以选择提高装载因子的值。
    • 此外,即使装载因子和哈希算法设计得再合理,也不免会出现由于哈希冲突导致链表长度过长的情况,这将严重影响 HashMap 的性能。为了优化性能,从 JDK1.8 开始引入了红黑树,当链表长度超出 TREEIFY_THRESHOLD 规定的值时,链表就会被转换为红黑树,利用红黑树快速增删改查的特点以提高 HashMap 的性能。
    //序列化ID
    private static final long serialVersionUID = 362498820763181265L;
    
    //哈希桶数组的默认容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    //网上很多文章都说这个值是哈希桶数组能够达到的最大容量,其实这样说并不准确
    //从 resize() 方法的扩容机制可以看出来,HashMap 每次扩容都是将数组的现有容量增大一倍
    //如果现有容量已大于或等于 MAXIMUM_CAPACITY ,则不允许再次扩容
    //否则即使此次扩容会导致容量超出 MAXIMUM_CAPACITY ,那也是允许的
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //装载因子的默认值
    //装载因子用于规定数组在自动扩容之前可以数据占有其容量的最高比例,即当数据量占有数组的容量达到这个比例后,数组将自动扩容
    //装载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小
    //对于使用链表的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,则对空间的利用程度更高,相对应的是查找效率的降低
    //如果负载因子太小,那么数组的数据将过于稀疏,对空间的利用率低
    //官方默认的负载因子为0.75,是平衡空间利用率和运行效率两者之后的结果
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    //为了提高效率,当链表的长度超出这个值时,就将链表转换为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    

  • HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
    • 如果超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法。

02.HashTable和HashMap

  • HashTable和HashMap初始化与增长方式
    • 初始化时:
      • HashTable在不指定容量的情况下的默认容量为11,且不要求底层数组的容量一定要为2的整数次幂;HashMap默认容量为16,且要求容量一定为2的整数次幂。
    • 扩容时:
      • Hashtable将容量变为原来的2倍加1;HashMap扩容将容量变为原来的2倍。
  • HashTable和HashMap线程安全性
    • HashTable其方法函数都是同步的(采用synchronized修饰),不会出现两个线程同时对数据进行操作的情况,因此保证了线程安全性。也正因为如此,在多线程运行环境下效率表现非常低下。因为当一个线程访问HashTable的同步方法时,其他线程也访问同步方法就会进入阻塞状态。比如当一个线程在添加数据时候,另外一个线程即使执行获取其他数据的操作也必须被阻塞,大大降低了程序的运行效率,在新版本中已被废弃,不推荐使用。
    • HashMap不支持线程的同步,即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步(1)可以用Collections的synchronizedMap方法;(2)使用ConcurrentHashMap类,相较于HashTable锁住的是对象整体,ConcurrentHashMap基于lock实现锁分段技术。首先将Map存放的数据分成一段一段的存储方式,然后给每一段数据分配一把锁,当一个线程占用锁访问其中一个段的数据时,其他段的数据也能被其他线程访问。ConcurrentHashMap不仅保证了多线程运行环境下的数据访问安全性,而且性能上有长足的提升。

03.hashCode和equal

  • get和put的中的equals()和hashCode()的都有什么作用?
    • 通过对key的hashCode()进行hashing,并计算下标( (n-1) & hash),从而获得buckets的位置。
    • 如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点

04.Key为何需要不可变

  • 为什么HashMap中String、Integer这样的包装类适合作为K?
    • String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率
      • 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况
      • 内部已重写了equals()、hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况
      • 如果对象在创建后它的哈希值发生了变化,则Map对象很可能就定位不到映射的位置。
  • 想要让自己的Object作为K应该怎么办呢?
    • 重写hashCode()和equals()方法
      • 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞;
      • 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性;
  • 总结
    • 采用合适的equals()和hashCode()方法的话,将会减少碰撞的发生,提高效率。不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择。

05.HashMap为啥要扩容

  • HashMap是为啥要扩容
    • 当链表数组的容量超过初始容量*加载因子(默认0.75)时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中。为什么需要使用加载因子?为什么需要扩容呢?因为如果填充比很大,说明利用的空间很多,如果一直不进行扩容的话,链表就会越来越长,这样查找的效率很低,扩容之后,将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置,这样就减少了每个链表的长度,增加查找效率。
  • 重新调整HashMap大小存在什么问题吗?
    • 当多线程的情况下,可能产生条件竞争。当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

06.HashMap的table下标

  • 它是用自己的hash方法确定下标
    • HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均;
    • 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题;
  • 不直接使用hashCode()处理后的哈希值
    • hashCode()方法返回的是int整数类型,其范围为-(2^31)~(2^31-1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置;
  • 为什么数组长度要保证为2的幂次方呢?
    • 只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,即实现了key的定位,2的幂次方也可以减少冲突次数,提高HashMap的查询效率;
    • 如果 length 为 2 的次幂 则 length-1 转化为二进制必定是 11111……的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;如果 length 不是 2 的次幂,比如 length 为 15,则 length - 1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0 ,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

赞赏支持


精彩留言

发表评论