1.存储结构
从JDK8之后，底层结构实现由数组+链表改为了数组+链表+红黑树。
基本存储字段如下图所示
同样，从JDK8之后，基本存储单元由Entry<K,V>改为了Node<K,V>，Node结构如下图所示
这里说明2个字段，负载因子和阈值，公式为阈值=容量*负载因子，容量为当前HashMap最大容量，当实际容量超过阈值时进行扩容。
2.get方法
如下图所示
这里说明下HashMap计算索引的方式，分为3步：1. key.hashCode() 2. (h = key.hashCode()) ^ h >>> 16 3.n - 1 & hash
第一步计算key的hashCode值，然后将该值向右位移16位，在与自己做或运算得出hash值，最后与最大容量减1做与运算。其中第二步的目的是让高16位与低16位分步均匀。
另外，这里涉及到一个问题，为什么HashMap的容量是2的n次方，个人目前理解有3点，1.当容量为2的n次方时，n - 1 & hash运算等价于对n取模，也就是hash%n，但是&比%效率更高，我们都知道计算机运算最终都是转换为二进制进行计算的，而&直接对二进制进行计算所以更快。2.当容量为2的n次方时，n-1的值的二进制表示，低位全部为1，如下图所示
这样进行与运算求索引位的时候可以保证每个位置都可以被取到，不至于有些位置永远无法获取，造成空间浪费。3.扩容的时候更加方便，这个后文进行说明。
3.put方法
如下图所示
这里有2点需要说明下，1.HashMap初始化并不是在构造的时候进行，而是在第一次put时进行扩容从而初始化。2.put时当某条链表长度大于7会进行树化，转换成红黑树。
3.扩容
如下图所示
扩容的时候会新建一个数组，将老数组中的数据全部转移到新数组，同时将老数组中的节点全部赋为null，让系统进行回收。
扩容中最精华的地方在于新数组索引位的计算，如图6所示，上文中说过，索引的计算是key的hash值与n-1做与运算，扩容的时候hash值是不变的，变的是n-1的值，而每次扩容是之前的2倍，那么n-1的二进制表示就是高位加1，那么最后索引计算的结果就取决于这个新增的高位1与hash值计算的结果，而老数组容量的二进制表示正好是这个高位为1，低位全部为0，那么只要计算老容量与hash值与运算结果是否为0就可以判断新的索引位是否会发生改变，源码中创建了2条链表，一条表示不改变的，一条表示改变的，最后将2条链表赋值给新数组。还有一点变化的是，JDK8之前，扩容的时候原链表转移到新数组后，链表顺序会倒置，采用的头插入法，JDK8之后，顺序不变，采用的是尾插入法，这点从图6中可以看出。
至此，HashMap的底层原理就简单介绍到此。
网友评论