首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HashMap的自问自答

HashMap的自问自答

作者头像
韦东锏
发布2021-09-29 15:19:57
2290
发布2021-09-29 15:19:57
举报
文章被收录于专栏:Android码农Android码农

用最自然的方式掌握HashMap~

带着疑问去了解HashMap,下面用一个个问题,来拆解HashMap

数据存放的载体是什么

这个问题,其实是最核心的,也是最基础的问题

其实知道答案之前,也大概猜到了吧,没错,数据的载体,是数组,并且数组的类型是Node,节点的意思

//真正存放key value的地方
transient Node<K,V>[] table;

Node代表是类型,[]代表是数组,K、V代表的存储的key跟value泛型

Node其实是一个class,本地变量有key、value,key的hash值,还有指向下个node的引用

class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }

hashmap的本质,其实是一个node类型的数组

其实不管是hashmap,还是arraymap,存储的载体都是数组,数组是一块连续的内存空间,天生就非常适合来存储内容

了解了这个核心概念后,后续的问题就自然而然冒出来了

数组的长度

既然是数组,那就必须有一个初始的长度,通过源码,可以知道数组的初始长度是16

# 二进制1左移4位,刚好是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

然后每次扩容的时候,长度都是*2,就像16 -> 32 ->64这样

# java.util.HashMap#resize
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }

其中newCap = oldCap << 1表示旧的容量左移一位,相当于乘2

为什么容量都是2的倍数

核心还是为了性能,在读跟取的时候,经常需要根据key的hash值,快速定位到数组对应的position,而当数组的长度是2的倍数的时候,就可以用位运算快速的计算出来,下面是示例代码

int hash = hash(key)
//n指数组的长度,固定2的倍数
int n = tab.length
//用位运算高效计算hash值对应的数组的位置
Node result = table[(n-1)&hash]

这样,在存或者读的时候,都可以快速定位到数组对应的位置,比如实际读的代码,根据key获取到对应的node

public V get(Object key) {                                          
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;  
}                                                                   

final Node<K,V> getNode(int hash, Object key) {
//hash代表key的hash值
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;                        
    if ((tab = table) != null && (n = tab.length) > 0 &&                    
        (first = tab[(n - 1) & hash]) != null) {
        //直接拿到数组对应位置的node
        if (first.hash == hash &&                
            ((k = first.key) == key || (key != null && key.equals(k))))  
            //如果hash一样,并且key相等,就是我们要的node
            return first;                                                   
        if ((e = first.next) != null) {
        //hash一样,key不一样,代表hash冲突了,需要另行处理
            if (first instanceof TreeNode) 
            //通过红黑树的方式查询
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
            //或者通过链表的方式查询
            do {                                                            
                if (e.hash == hash &&                                       
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    return e;                                               
            } while ((e = e.next) != null);                                 
        }                                                                   
    }                                                                       
    return null;                                                            
}                                                                           

当定位到数组对应的位置,不代表找到的node就是我们要的node,因为不同的key,有可能hash值是相同的,所以引申了下面的问题

碰到hash冲突怎么办

hashmap有两种处理冲突的方式,一是用链表来存储,存储的时候,也是新建一个node,跟当前的node组成链表,不断有新的冲突,就不断的往这个链表后面添加

//一个无限循环,由内部条件控制退出循环
for (int binCount = 0; ; ++binCount) {                            
    if ((e = p.next) == null) { 
    //e==null,代表到了链表的最后一个位置,然后把新的node插入最后一个位置
        p.next = newNode(hash, key, value, null);                 
        if (binCount >= TREEIFY_THRESHOLD - 1) 
        //触发链表转成红黑树
            treeifyBin(tab, hash);                                
        break;                                                    
    }                                                             
    if (e.hash == hash &&                                         
        ((k = e.key) == key || (key != null && key.equals(k))))  
        //如果链表中,有原来的key,说明找到对应node了,结束循环
        break;                                                    
    p = e;                                                        
}                                                                 

理论上,链表可以无穷无尽的往后面不断的添加,不过看上面代码也知道,当链表比较长的时候,就不适合采用链表来存储,会被转成红黑树来存储;

从性能角度考虑,链表只能从头开始往后检索,算法的时间复杂度是O(n),而红黑树的时间复杂度是O(log n),所以在hash冲突数量比较多的地方,用红黑树可以提升性能

链表跟红黑树转换时机:当链表达到8条内容的时候,就转成了红黑树

另外,当红黑树的内容小于6的时候,也会被重新转成链表的形式

可以用这个图片,形象的来展示

数据扩容时机

我们知道,hashmap的容量扩容都是翻倍增加的,那什么时候触发扩容呢

在默认情况下,容量是16,扩容系数是12

newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12

存储的个数超过扩容系数,就会触发扩容,而且每次扩容,都是容量跟扩容系数一起翻倍

newCap = oldCap << 1
newThr = oldThr << 1; // double threshold

容量跟扩容系数的关系如下

容量

扩容系数

16

12

32

24

64

48

128

96

256

192

越到后面,容量跟扩容系数的差距越大,个人感觉,这里的设计不是很合理,扩容系数明显偏小了

那如果是自定义容量的情况下呢?

比如当知道hashmap就只保存五条内容,初始化的时候,就把容量定位5,保存完5几条后,会不会触发内部的扩容?

触发扩容的时机,还是由实际容量决定,关系就是上面的表格那样,不过实际容量并一定等于初始容量,因为实际容量都是2的指数,关系如下图

初始容量值

实际初始容量

4

4

5

8

8

8

9

16

15

16

这样一看,就明白关系了,源码里面,是通过位运算来得出这个结果的

//Returns a power of two size for the given target capacity
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; 
}                                                                            

所以初始容量是5,实际容量是8,扩容系数是8*0.75=6,保存五条内容不会触发扩容

不过当初始容量是14的hashmap,保存14条内容,情况是如何呢?

val map = HashMap<String, String>(14)
for (i in 1..14) {                    
    map.put("key$i", "value$i")   
}                                     

上面的代码,初始的容量是14,实际申请的容量是16,可以得知扩容系数是12,当存储到第13条内容的时候,就触发了扩容,容量扩大到32,浪费了内存空间,同时也降低的性能

所以,对于保存固定数量的hashmap,建议同时设定loadFactor为1.0

val map = HashMap<String, String>(14, 1.0f)
for (i in 1..14) {                    
    map.put("key$i", "value$i")   
}    

这样的话,扩容系数跟容量一样的了,实际可以保存16条不会扩容,避免了内存浪费

数组容量会自动缩小吗

不会,容量只会扩大,即使item全部remove掉了,hashmap的容量也不会缩小;如果想用更节约内存的key value组件,可以考虑用ArrayMap

扩容都做了什么

在上面代码可以知道,key都是通过它的hash值与数组长度-1做二级制的与计算,确定对应的value在数组的position

//用位运算高效计算hash值对应的数组的位置,n就是数组长度
Node result = table[(n-1)&hash]

扩容后,n变了,原来key对应的value的position全部都要重新计算,所以每次扩容,都会重新排序全部的key value,是一个比较重的操作,下面是扩容的代码,也可以看下作为参考

if (oldTab != null) {                                                            
    for (int j = 0; j < oldCap; ++j) {  
        Node<K,V> e;                                                             
        if ((e = oldTab[j]) != null) {  
        //j位置,有可能没有value,所以需要做判空
            oldTab[j] = null;                                                    
            if (e.next == null)  
                //把e赋值到新的position
                newTab[e.hash & (newCap - 1)] = e;                               
            else if (e instanceof TreeNode)    
                //红黑树下的遍历
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);               
            else { // preserve order    
                //链表下的遍历
                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;                                 
                }                                                                
            }                                                                    
        }                                                                        
    }                                                                            

如果是可以大概预估hashmap的长度的场景,应该在初始化的时候,就直接赋值进去,可以避免触发扩容,提升性能

val n = 100 //预估的容量不会超过100
val hashMap = HashMap<String, String>(n, 1.0f)

还有别忘了第二个参数要填1.0f

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2021-09-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Android码农 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据存放的载体是什么
  • 数组的长度
  • 为什么容量都是2的倍数
  • 碰到hash冲突怎么办
  • 数据扩容时机
  • 数组容量会自动缩小吗
  • 扩容都做了什么
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档