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

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

前言

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

本篇内容

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

/**
*	默认的初始容器大小,必须是2的整幂数,如果在创建实例的时候没有初始化一个对象,
*	那么容器就会默认使用这个数值
*/
static final int DEFAULT_INITIAL_CAPACITY = 1  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  MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
            //Float.isNaN() is not number 不是一个数,判断我们传入的值是否进行多次计算造成非法
            //数值
        if (loadFactor >> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (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 map = new HashMap(4);
        for(int i =0;i