HashMap原理总结1

HashMap原理总结1 HashMap原理总结1 面试问题

你看过HashMap源码吗，知道底层的原理吗为什么使用数组+链表用linkedList代替数组可以吗既然是可以的，为什么不用反而用数组。 重要变量（理解） HashMap桶容量一定要2的n次方

    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // 位运算的速度最快，所以写成1<<4而不是16

如果new 一个HashMap的容量不是2的n次方即取最近大于的。
例：HashMap hash = new HashMap<>(14)即取16

1 -> 27 -> 814 -> 15
…
为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，使得每个链表长度大致相同。关键就在于把当前数据存放到哪一个桶中(哪个节点node上)，实现这个目标的算法就是取模运算
当为2的n次幂，hash & (capacity - 1) == hash % capacity

这里有一个小建议：在初始化HashMap的时候，应该尽量指定其大小。尤其是当你已知map中存放的元素个数时。（《阿里巴巴Java开发规约》）

负载因子的使用

    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

当元素的总个数 > 当前数组的长度 * 负载因子。数组会进行扩容，扩容为原来的两倍 。
负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率

链表阈化值==8与红黑树链化阙值=6

    
    static final int TREEIFY_THRESHOLD = 8;

    
    static final int UNTREEIFY_THRESHOLD = 6;

hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况
在理想情况下，桶(bins)中的节点数概率(链表长度)符合泊松分布，当桶中节点数(链表长度)为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率

原理

HashMap底层是基于数组和链表

从图中我们可以看到一个hashmap就是一个数组结构，当新建一个hashmap的时候，就会初始化一个数组。
java代码

    static class Entry implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Entry next;
        ....
    }

上面的Entry就是数组中的元素，

问题回答

1.为什么使用数组+链表？
答：由于我们数组的值是限定死的，我们在对key进行散列时取到下标放入数组时，难免会出现取到相同的下标，但是却放入同一个位置中，这时就可以使用链表存储
2.用linkedList代替数组可以吗？
答：可以的
3.既然是可以的，为什么不用反而用数组？
答：因为数组查询速度快，效率高。在HashMap中，定位节点的位置是利⽤元素的key的哈希值对数组⻓度取模得到。此时，我们已得到节点的位置。显然数组的查 找效率⽐linkedList⼤（底层是链表结构）。
那ArrayList，底层也是数组，查找也快啊，为啥不⽤ArrayList? 因为采⽤基本数组结构，扩容机制可以⾃⼰定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率⾼。 ⽽ArrayList的扩容机制是1.5倍扩容

Hash冲突

我们可以看到在hashmap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合，所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。

所以我们首先想到的就是把hashcode对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是为了减少“模”运算的效率。
使用当为2的n次幂，hash & (capacity - 1) == hash % capacity。
效率最高，碰撞最小。（具体见上文重要变量举例所述）

经个人总结
参考文档

1.https://www.bilibili.com/read/cv5517205/
2.https://www.iteye.com/topic/539465
3.https://blog.csdn.net/qq_40298054/article/details/85224198?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=1