深入理解HashMap的底层原理(一)

爱被打了一巴掌 2023-07-13 12:28 4阅读 0赞

> 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）  
> –摘自《百度百科》

## 前言 ##

一步一步，一小步，一大步，我相信知识的积累会有一个质的飞跃。  
写此文章的目的是为了记录自己的学习。记录在此也是希望各位业界的前辈们如果发现了不正确的地方，希望您能及时批评指正，在此感谢!

## 本篇内容 ##

本篇主要是记录HashMap中定义的一些属性目的为了初步了解和加深一下概念。  
先来看看HashMap定义的几个主要变量

/** * 默认的初始容器大小,必须是2的整幂数,如果在创建实例的时候没有初始化一个对象, * 那么容器就会默认使用这个数值 */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    /** * 容器的最大容量,也就说容器大小必须<=MAXIMUM_CAPACITY */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /** * 加载因子,用来判断容器装载的程度,这个值并不是任意取的,他取的是一个平衡值,当容器实例创建时不指定 * 的话,会默认将此值作为加载因子 final float loadFactor = DEFAULT_LOAD_FACTOR */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /** * 临界值,当容器大小超过临界值的时候会进行扩容,threshold=capacity * load factor */
    int threshold;
    /** * 加载因子 */
    final float loadFactor;
    /** * 返回(记录)key-value映射的个数 */
    transient int size;

##### 一、初始容量 #####

在HashMap的使用中其实是提倡我们在实例化的时候给指定的初始容量,这一点在《阿里巴巴java开发手册》集合处理中也有明确的规定。那么为什么我们要进行初始化？  
我们的定义4个集合,一个默认容量,一个初始化容量为16,一个初始化为20000,一个初始化为10000

public void compareInitial(){ 
            Map<Integer, Integer> map1 = new HashMap<>();
            long start1 = System.currentTimeMillis();
            for(int i = 0 ; i <10000000;i++){ 
                map1.put(i,i);
            }
            long end1 = System.currentTimeMillis();
            System.out.println("map1 capacity->default 耗时:"+(end1-start1));
    
            Map<Integer, Integer> map2 = new HashMap<>(20000);
            long start2 = System.currentTimeMillis();
            for(int i = 0 ; i <10000000;i++){ 
                map2.put(i,i);
            }
            long end2 = System.currentTimeMillis();
            System.out.println("map2 capacity->20000 耗时:"+(end2-start2));
    
    
            Map<Integer, Integer> map3 = new HashMap<>(16);
            long start3 = System.currentTimeMillis();
            for(int i = 0 ; i <10000000;i++){ 
                map3.put(i,i);
            }
            long end3 = System.currentTimeMillis();
            System.out.println("map3 capacity->16 耗时:"+(end3-start3));
    
    
            Map<Integer, Integer> map4 = new HashMap<>(10000);
            long start4 = System.currentTimeMillis();
            for(int i = 0 ; i <10000000;i++){ 
                map4.put(i,i);
            }
            long end4 = System.currentTimeMillis();
            System.out.println("map4 capacity->10000 耗时:"+(end4-start4));
        }

结果

map1 capacity->default 耗时:8049
    map2 capacity->20000 耗时:4812
    map3 capacity->16 耗时:1388
    map4 capacity->10000 耗时:4685

从结果中不难看出，给容器一个合理的初始大小很够有效的提高性能,因为容器会有一个临界值threshold当容器装载的kv超过此大小时候容器会进行扩容，扩容机制为threshold=capacity \* load factor,每次的扩容HashMap都会重建Hash表.

##### 二、size和capacity #####

在变量的定义中，我们会觉得size似乎与capac定义类似。  
**size**:返回容器中存储了多少个kv  
**capacity**:是当前容器的大小  
请看演示

public void sizeCompareCapacity() throws Exception{ 
            Map<String, String> map = new HashMap<>();
            map.put("name","张三");
            Map<String, String> map1 = new HashMap<>(5); 
            map1.put("name","张三1");
            Map<String, String> map2 = new HashMap<>(16);
            map2.put("name","张三2");
            //通过反射机制来获取容器内的方法
            Class<?> capaci =  map.getClass();
            Method method = capaci.getDeclaredMethod("capacity");
            method.setAccessible(true);
    
            System.out.println("map capacity: "+ method.invoke(map)+"------> map size:"+map.size());
            System.out.println("map1 capacity: "+ method.invoke(map1)+"------> map1 size:"+map.size());
            System.out.println("map2 capacity: "+ method.invoke(map2)+"------> map2 size:"+map.size());
        }

运行结果

map capacity: 16------> map size:1
    map1 capacity: 8------> map1 size:1
    map2 capacity: 16------> map2 size:1

size的大小为1,capacity的大小不难看出是我们定义的大小。  
**细心的朋友可能看出map1的容器大小我定义的是5他为什么会是8.**  
我先贴一张源码

//无参构造器
    public HashMap() { 
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    //有参构造器
    public HashMap(int initialCapacity) { 
    		//这是我们演示代码中使用的构造方法,调用下面的方法
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    //有参构造器
    public HashMap(int initialCapacity, float loadFactor) { 
            if (initialCapacity < 0)  //如果初始容量必须大于0否则报错
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
             //容器大小限制不大于最大值
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
                //Float.isNaN() is not number 不是一个数,判断我们传入的值是否进行多次计算造成非法
                //数值
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            //赋值 加载因子 
            this.loadFactor = loadFactor;
            //赋予 容器大小
            this.threshold = tableSizeFor(initialCapacity);
        }

在HashMap的内部为我们提供重载的3中构造方法,在源代码中我进行了粗略的注释，下面我们在来看  
最后一行\*\*this.threshold = tableSizeFor(initialCapacity)\*\*的方法  
附一张源码

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

JAVA8对于JAVA7的性能优化tableSizeFor算是一个很好的例子
    |= 和 += 类似。
    所以这里的等价于n = n | n >>> 1
    >>>无符号位运算符,与>>的区别在于不管是正数或负数补位,都是补0 , 
    |或运算符 也就是两个都为0才是0,否则是1
    下面请看:
    我们传入的是cap=5, n=cap-1=4.
    第一次:>>>1
    n---0100
    ->	0010  
    n=  0110
    第二次: >>>2
    n---0110
    ->  0001
    n=  0111
    第三次: >>>3
    n---0111
    ->	0000
    n=	0111
    其实在此后无论再怎么使用无符号位运算符都是0111->转换为十进制:n=2^0+2^1+2^2=7
    使用此运算的目的就是为了让传入cap最高位的1后面都为1.比如我们的结果从0100->0111
    在return的时候在进行+1  0111->1000为10进制的8
    那么为什么会将cap进行-1呢？目的是放止传入的值已经是2的幂次方.
    以上面的例子来说,假设我们传入的是cap=4,不进行减1的话按照上面的流程走完得到的值是7
    那么return返回的结果就是8。

总结来说tableSizeFor方法的作用是**当我们传入一个不符合容器规则的数值是,他会帮我们去寻找比他大的第一个2的幂次方数值。**  
这样也能解释的通为什么我们传入的5变成了8

##### 三、扩容机制 loadFactor和threshold #####

我们先来看一组运行结果

public void loadAndThres() throws Exception { 
            Map<Integer,Integer> map = new HashMap<>(4);
            for(int i =0;i<3;i++){ 
                map.put(i,i);
            }
    
            Class<?> cls = map.getClass();
            Method capacity = cls.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity:"+capacity.invoke(map));
    
            System.out.println("size:"+map.size());
    
            Field threshold = cls.getDeclaredField("threshold");
            threshold.setAccessible(true);
            System.out.println("threshold:"+threshold.get(map));
    
            Field loadFactor = cls.getDeclaredField("loadFactor");
            loadFactor.setAccessible(true);
            System.out.println("loadFactor:"+loadFactor.get(map));
            System.out.println("---------------------------------------");
            map.put(4,4);
            System.out.println("capacity:"+capacity.invoke(map));
            System.out.println("size:"+map.size());
            System.out.println("threshold:"+threshold.get(map));
            System.out.println("loadFactor:"+loadFactor.get(map));
        }

capacity:4
    size:3
    threshold:3
    loadFactor:0.75
    ---------------------------------------
    capacity:8
    size:4
    threshold:6
    loadFactor:0.75

从上结果我们能发现:  
1.threshold:是判断容器是否负载的依据,如果容器的size大于threshold那么容器将会进行扩容.  
扩容的大小为capacity\*loadFactor  
2.capacity:容器扩容大小为2的幂次依次递增.

希望各位看过的伙伴们如果发现了问题能够及时批评指正，在此感谢。

下一篇:[深入理解HashMap的底层原理(二)][HashMap]粗略的介绍一下HashMap的扩容过程,有兴趣的朋友可以帮忙一起探讨指正不足之处!

[HashMap]: https://blog.csdn.net/qq_40409260/article/details/104906133