对于java程序员来说，hashMap是最常用的集合之一。那么他的底层的数据结构以及实现又是怎么样的呢？
在java中，最常见的数据结构就是数组与链表。hashMap就是两者的结合，我们叫做散列表。为什么hashMap要这种结构呢？是因为单纯的以数组来存储的话，查询会很快，但是每次修改的时候，数组都要重新计算索引，就会很慢。单纯的以链表进行存储的话，新增与删除很快，只需要修改一下指向下一个地址的指针即可，但是查询就没有那么大的效率了，他需要遍历整个链表才可以。所以hashMap采用了数组加链表的形式。
图片.png
hashMap根据key的hashCode值，可以很快的定位到该key在哪个数组下标，然后不管新增还是删除，还是查询，只是遍历或者修改该数组下标中存储的链表即可。为了查询的更快，最理想的情况就是每个数组下标中的链表，长度只为1，那么就无需遍历了。
所以我们期望尽可能的把值平均的分布到数组的各个位置。而当数据达到一定程度，数组大多数的位置都有值了，为了有更好的效率，就需要将数组扩容，然后重新计算数组下标。
那么来看看hashMap是如何实现的呢，以下是根据jdk1.8来进行分析的。
我们首先来看一下put方法。put(k,v);
图片.png
首先就是直接将key做hash运算。然后再看putVal方法。
图片.png
第一步：判断数组是否空，如果为空或者长度为0，就先初始化数组大小。
第二步：根据key的hash值与数组长度-1进行一次&运算来获取数组下标。
为什么要这么做呢？首先，hashMap的数组长度是2的倍数。我们拿hashMap的默认的数组长度16来举例，16转换为2进制就是10000，减去1就是1111。如果hashMap的长度是15的话，那么减去1的值就是1110。以2，3为例，与1110进行&，值都为2。与1111进行&值为2，3。所以这种算法的散列性比较好。而且如果是1110的话，那么他的最后一位都是0，就导致进行&运算时，造成大量的坐标无法存放值。
如果当前的数组下标没有值，就新创建一个node。
第三步：即不是初始化，并且数组下标已经有值了，如果对应数组下标的链表头的node的hash值与当前key的hash值相等，并且key也相等，则当前的node就是链表头的node
第四步：如果p是树结点的话，那么就往树里面赛值
第五步：如果已经是链表的尾部了还没有找已存在的key相等的node，就创建一个结点，如果长度大于一定的长度，就转为红黑树。
如果该node的hash值与传入的hash值相等，并且key也相等，那么这就是目标node。
p=e；赋值操作，与e=p.next。使得不断往后遍历链表
第六步：对hashMap来说不重要。
第七部：每次put一次，修改字数就加1，并且size加1，并且进行判断是非需要扩容。如果是，就进行扩容；
接下来讲讲扩容：
图片.png
获取一下原先数组的大小，容量。如果老的数组大小大于最大长度，就返回老的数组，不再扩容，否则的话就想新数组的容量变为老数组的2倍，如果oldThr>0不成立并且oldCap>0也不成立，就认为这个数组是进行初始化的，赋予默认大小。根据参数创建一个新的数组，然后将老数组的数据放入到新数组里面
图片.png
这里的逻辑是，如果当前数组中的链表结点就一个，那么就直接计算他在新数组中的位置。如果是红黑树的话，就走红黑树的逻辑。否则的话，就定义2个链表
lo链表 和 hi链表，loHead指向lo链表头，loTail指向lo链表尾。hi链表也一样。
然后就遍历链表，判断(e.hash & oldCap) 是否等于0，等于0，就放到lo链表，否则放到hi链表。然后将lo链表放到新数组的当前位置，hi链表放到当前位置索引加原来数组长度的索引位置。
网友评论