欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HashMap深入理解

程序员文章站 2023-12-10 19:19:22
参考美团技术团队-Java 8系列之重新认识HashMap一些Map的比较HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全....

参考

美团技术团队-Java 8系列之重新认识HashMap

一些Map的比较

  1. HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
  2. Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。
  3. LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。
  4. TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

HashMap概览

HashMap 底层的数据结构主要是:数组 + 链表 + 红黑树(JDK1.8增加了红黑树部分)。其中当链表的长度大于等于 8 时,链表会转化成红黑树,当红黑树的大小小于等于 6 时,红黑树会转化成链表,整体的数据结构如下:
HashMap深入理解
图中左边竖着的是 HashMap 的数组结构,数组的元素可能是单个 Node,也可能是个链表,也可能是个红黑树,比如数组下标索引为 2 的位置就是一个链表,下标索引为 9 的位置对应的就是红黑树。
HashMap就是使用哈希表来存储的。哈希表为解决冲突,可以采用开放地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。

变量概念

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 :初始容量为 16,它一定是2
static final int MAXIMUM_CAPACITY = 1 << 30 :最大容量 为2一样也一定是2
static final float DEFAULT_LOAD_FACTOR = 0.75f :负载因子默认值为0.75
static final int TREEIFY_THRESHOLD = 8; 桶上的链表长度大于等于8时,链表转化成红黑树
static final int UNTREEIFY_THRESHOLD = 6; 桶上的红黑树大小小于等于6时,红黑树转化成链表
static final int MIN_TREEIFY_CAPACITY = 64; 当数组容量大于 64 时,链表才会转化成红黑树
transient int modCount :结构版本号,强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。
transient int size; HashMap 的实际大小,可能不准(因为当你拿到这个值的时候,可能又发生了变化)
int threshold; // 扩容的门槛,有两种情况 // 如果初始化时,给定数组大小的话,通过 tableSizeFor 方法计算,数组大小永远接近于 2 的幂次方,比如你给定初始化大小 19,实际上初始化大小为 32,为 2 的 5 次方。 // 如果是通过 resize 方法进行扩容,大小 = 数组容量 * 0.75
static class Node<K,V> implements Map.Entry<K,V> {} 链表的节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {} 红黑树的节点

类介绍(注释)

类注释大致内容如下:

  1. 允许 key为null、value 为null ,实现了Map接口的所有方法。
  2. 它是hash table的Map接口实现版本,除了它是非线程安全的,其他与_Hashtable一致。_
  3. 它不保证元素顺序
  4. get、put操作,时间复杂度是O(1)
  5. load factor(影响因子) 默认值是 0.75, 是均衡了时间和空间损耗的值,较高的值会减少空间开销(扩容减少,数组大小增长速度变慢),但增加了查找成本(hash 冲突增加,链表长度变长),不扩容的条件:数组容量 > 需要的数组大小 /load factor;
  6. 如果有很多数据需要储存到 HashMap 中,建议 HashMap 的容量一开始就设置成足够的大小(尽量减少rehash的操作次数),这样可以防止在其过程中不断的扩容,影响性能;
  7. 在迭代过程中,如果 HashMap 的结构被修改(put、delete),会快速失败。
  8. HashMap 是非线程安全的,我们可以自己在外部加锁,或者通过 Collections#synchronizedMap 来创建HashMap实现线程安全,Collections#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁;

# 常用方法源码 ### 哈希桶数组索引位置(hash) 用来计算key的hashcode,这里的Hash算法本质上就是三步:**取key的hashCode值、高位运算、取模运算**。
static final int hash(Object key) {
    int h;
    return (key == null) ? 
        0 :
    // key.hashCode()取hashCode值
    // h ^ (h >>> 16) 高位参与运算
    (h = key.hashCode()) ^ (h >>> 16);
}

//jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
static int indexFor(int h, int length) {  
     return h & (length-1);  //第三步 取模运算
}

对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,模运算的消耗还是比较大的,在HashMap中是这样做的:调用方法二来计算该对象应该保存在table数组的哪个索引处。
这个方法非常巧妙,它通过h & (table.length -1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

添加(put,jdk1.8)

public V put(K key, V value) {
    // 对key进行hash操作后,调用putVal方法
    return putVal(hash(key), key, value, false, true);
}

// 入参 hash:通过 hash 算法计算出来的值。
// 入参 hash:通过 hash 算法计算出来的值。
// 入参 onlyIfAbsent默认为 false
// false 表示 key 存在时,会用新值覆盖原来的值,
// 为true时,表示只有在key 不存在时,才会被放入map
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    
     // n 表示数组的长度,i 为数组索引,p 为 i 下标位置的 Node 值
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是,则直接在树中插入键值对,否则转向⑤;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
       // 5.可以确定,该表为链表。遍历table[i],
       // 在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
        else {
            for (int binCount = 0; ; ++binCount) {
                 // e = p.next 表示从头开始,遍历链表
                // p.next == null 表明 p 是链表的尾节点
                
                if ((e = p.next) == null) {
                    // 在尾部添加
                    p.next = newNode(hash, key, value, null);
                    
                    // 判断链表长度是否大于8,大于8的话把链表转换为红黑树,
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到相同的,不为null的key,结束遍历
                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;
            // 当 onlyIfAbsent 为 false 时,才会覆盖值 
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    
    // 变更 HashMap 的结构版本号
    ++modCount;
    
    // 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

从以上源码中,我们可以了解到,在当链表长度 >= 8 时,此时的链表就会转化成红黑树,转化的方法是:treeifyBin,此方法有一个判断,当链表长度>= 8,并且整个数组大小> 64 时,才会转成红黑树,当数组大小<64 时,只会触发扩容,不会转化成红黑树。
那么,这个转为红黑树的阈值(MIN_TREEIFY_CAPACITY)为什么是8呢?
在HashMap源码的143~198行,解释了这个“8”的由来。中文翻译过来大概的意思是:
链表查询的时间复杂度是 O (n),红黑树的查询复杂度是 O (log (n))。在链表数据不多的时候,使用链表进行遍历也比较快,只有当链表数据比较多的时候,才会转化成红黑树,但红黑树需要的占用空间是链表的 2 倍,考虑到转化时间和空间损耗,所以我们需要定义出转化的边界值。
在考虑设计 8 这个值的时候,我们参考了泊松分布概率函数,由泊松分布中得出结论,链表各个长度的命中概率为:
泊松分布-wiki

* 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

意思是,链表的长度为 8 的概率是 0.00000006,不到千万分之一,所以说正常情况下,链表的长度不可能到达 8 ,而一旦到达 8 时,肯定是 hash 算法出了问题,所以在这种情况下,为了让 HashMap 仍然有较高的查询性能,所以让链表转化成红黑树,我们正常写代码,使用 HashMap 时,几乎不会碰到链表转化成红黑树的情况,毕竟概率只有千万分之一。
其实想要hash的更加彻底还有很多神奇的算法,比如redis的murmurHash或者DJB HASH算法,但是因为性能差不多最后还是用了效率最高的^(异或 XOR)来解决问题

扩容(resize)

本方法分析参照美团技术团队-Java 8系列之重新认识HashMap,可以直接查看原帖,原帖还讲述了JDK1.8对扩容操作的优化、性能分析。
扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。

JDK1.8的resize方法,由于加入了红黑树的原因,较为复杂,这里先选取JDK1.7的resize方法。

void resize(int newCapacity) {   //传入新的容量
    Entry[] oldTable = table;    //引用扩容前的Entry数组
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
        return;
    }

    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable);                         //!!将数据转移到新的Entry数组里
    table = newTable;                           //HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);//更新扩容阈值
}

resize方法中,复制数据时,调用了transfer方法:

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
                // 先更新next 的指向;也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;
                // 这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话)
                e.next = newTable[i]; 
                newTable[i] = e;      //将元素放在数组上
                e = next;             //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}

这里在重新计算每个元素在数组中的位置时,与JDK1.8不同。

HashMap的线程安全

HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。
原因:在并发的场景中使用HashMap可能造成死循环(环形链表)。

本文地址:https://blog.csdn.net/lik_lik/article/details/107058666