如果你这么去理解HashMap就会发现它真的很简单

返回：HashMap

好话说在前头

Java中的HashMap相信大家都不陌生，也是大家编程时最常用的数据结构之一，各种面试题更是恨不得掘地三尺的去问HashMap、HashTable、ConcurrentHashMap，无论面试题多么刁钻的问，只要我们真正的掌握了它的设计思想，便可以不变应万变，hold住所有的面试题了

本文主要包含以下内容，力求深入浅出一步一步彻底明白HashMap的设计思想：

数组的优势

返回：顶部

如果我们要获取第四个元素的值，直接a[3]就可以了，时间复杂度为O(1)，
如果我们要将第四个元素的值替换为36，直接a[3]=36就可以了，时间复杂度也是O(1),
也就是说基于下标的随机访问和赋值数组元素的时间复杂度都是O(1)，无论这个数组是多大（在内存充足的条件下），这是数组的优势之一。

数组是特殊的键值对

返回：顶部

通过上面的简单描述，我们可以知道数组可以通过“下标”来获取数组中的指定元素，但是这个下标只能是正整数，且从0开始。
但是如果我们想通过一个浮点数、一个字符串、一个对象来获取对应的元素呢？也就是所谓的键值对，是不是数组就满足不了了？
我们可以把数组看做是一种特殊的键值对，key就是数组的下标，value就是下标对应的元素：

所以我们要求KV数据结构里面的key是一个对象，而不仅仅只能是数组中的一个下标。因此我们需要创造出一种数据结构，他至少需要具有以下的特性：

• O(1)复杂度的访问任何一个key对应的值
• 这个key可以支持整型、浮点、字符串、对象等任何类型的数据

Hash

显然我们需要对key做一些特殊处理，这个时候Hash函数就上场了。

Hash函数

返回：顶部

Hash

哈希函数的作用就是通过哈希算法把任意类型的key转换成固定类型、固定长度的散列值，也就是我们所期望的数组下标（整型）。

因此哈希函数需要具有如下的特征：

• 相同的内容经过哈希算法计算后输出结果一致；
• 不同的内容经过哈希算法计算后输出不同的结果，但也可能会出现相同的输出值（即哈希碰撞）；

优秀的hash

因此，一个优秀的哈希算法是不同的内容经过哈希计算后输出的结果具有分布均匀的特点，也就是低碰撞率。
同时，计算速度必须要快！

比较出名的哈希算法有time33算法、Murmurhash算法，这些算法都在追求更好的均匀分布和更快的计算速度。

java8中String的hashCode实现方法：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

public static void main(String[] args) {
    String s1 = "abcdef";
    String s2 = "abcdef";
    String s3 = "abcdee";
    System.out.println("s1.hashCode:"+s1.hashCode());
    System.out.println("s2.hashCode:"+s2.hashCode());
    System.out.println("s3.hashCode:"+s3.hashCode());
//        System.out.println(new BigDecimal(""));
}

输出：

s1.hashCode:-1424385949
s2.hashCode:-1424385949
s3.hashCode:-1424385950

可以看出来s1和s2是相同的字符串，输出了相同的hash值，s3和s1、s2不同，输出的hash值也不同，但是也很接近。

说明java采用的hash算法分散性不好，如果用Murmurhash算法，差异就会很大，即哈希算法的剧烈度大，感兴趣的同学可以用Guava中Murmurhash方法试验一下。

但是又来了一个问题，通过上面的实验我们拿到的hashCode值很大，无法作为数组的下标，否则我们的数组占用的内存就太大了！

取余

所以就采用了根据hashCode取余的方式，比如Java中的HashMap默认size是16，那么92599395%16=3，那么实际上abcde这个字符串就存储在HashMap数组中下标为3的地方。

Hash冲突

返回：顶部

冲突

上面已经讲过Hash算法无法做到完全均匀分布，也就是说可能会有那么两个不一样的字符串经过hash计算后得到相同的值，此时两个不同的字符串都得对应同一个数组下标上，这就造成了所谓的Hash冲突。

因此，为了解决Hash冲突问题，我们需要下标对应的元素不再仅仅是当前对应的字符串了，而应该是当前的字符串再加上它的next节点的对象地址，这样的一个对象应该如下：

/**
* Basic hash bin node, used for most entries.  (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}