HashMap的原理简述

最近想起了之前看HashMap 源代码时写的那篇博客突然发现一个问题其实那篇写的很差因为没有一个整体的思路所以我决定重新写一篇HashMap相关的文章顺便在有时间的时候会把数据结构的部分的HashMap的kotlin版本完成。

那么要说清HashMap的原理首先要弄清楚它是什么。

首先Hash Map是怎样的数据结构使用过的人都知道它是键值对一一对应的每一个Key对应了一个value。所以Hash Map的每一个节点都应该是 包含一个key值和一个value值的。

HashMap的组成最基础的HashMap中包含了一个数组这个数组用来快速的查找数据

Hash Map中 hash方法返回值为以存储的key的hashcode值的高16位的取值。

而hashMap 将key,value存入数组的过程原理就是先将key通过hash方法计算返回的值和

数组的长度n减去1的得到的数值相位与(n-1)&hash(key) 这个很好理解位与计算是同为1才为1所以得到的数值一定是一个小于或等于n-1的值。然后将这个结果值作为存取数据的数组索引。

由于不同hash值和n-1进行位与会得到相同的数值。所以两个不同的key可能会返回相同的结果

当出现相同的结果的时因此就需要在相同的索引的情况形成链表因此hash Map的每一个节点都包含一个next值用于在hash计算的值相同的情况形成链表。查找的时候会先通过数组下标找到对应的Node。在遍历以这个Node为first节点的链表直到找到key与传入的key相等的那个节点。返回它。

由于遍历链表的执行效率会随着链表的长度增加而增加因此为了更高效。hashMap在这个链表超过长度8以后将它重新排列成红黑树因此可以推测Hash Map包含两种节点或者也可以是相同的Node结构同时包含 next left right以方便进行不同方式的数据排列和遍历。从源码看hashmap使用了两种不同结构的Node Node与Tree Node。

那么要实现一个hashMap 只需要定义好Node类在hashMap 中定义好数组然后实现它的ha sh方法还有put ,get方法。

那么Hash Map是如何扩容并且在什么情况下扩容呢。当hashMap的size大于threshold默认是数组的长度乘以0.75时就会进行扩容。

扩容的时候会重新创建一个数组并将所有的数据重新计算hash的值重新存到新的数组。

那么扩容以后是多大呢在源码中是通过tableSizeFor返回的可以看到注释里是原来长度的2次方在源码中扩容时候是先通过 tableSizeFor给threshold赋值之后再将数组的设置为threshold的值。而threshold的默认值是默认的数组长度乘以0.75

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

整理好了思路有空我会写一个Hash Map补充到这篇博客。