java.util.HashMap

image.png

public class HashMap<K, V> extends AbstractMap implements Map<K, V>, Cloneable, Serializable

本质是一个Entry[]数组（哈希桶数组），用Key的哈希值对桶数组size取模可得到数组下标。若数组下标碰撞，进化为链表或红黑树。

使用

构造函数

    HashMap map = new HashMap();

常用方法

    HashMap<String, Integer> map = new HashMap();
    map.put("ary", 1);
    map.get("ary");
    Set<Map.Entry<String, Integer>> entrySet = map.entrySet();

Lambda用法

    map.merge("ary", 1, (oldValue, newValue) -> oldValue + newValue);
    map.compute("ary", (k, v) -> v + 1);

摘要

HashMap 是一个关联数组、哈希表，线程不安全的，遍历时无序。
其底层数据结构是数组称之为哈希桶，每个桶里面放的是链表，链表中的每个节点，就是哈希表中的每个元素。
在JDK8中，当链表长度达到8，会转化成红黑树，以提升它的查询、插入效率，它实现了Map<K,V>, Cloneable, Serializable接口。

因其底层哈希桶的数据结构是数组，所以也会涉及到扩容的问题。
当HashMap的容量达到threshold域值时，就会触发扩容。扩容前后，哈希桶的长度一定会是2的次方。
这样在根据key的hash值寻找对应的哈希桶时，可以用位运算替代取余操作，更加高效。
在扩容中只用判断原来的 hash 值与左移动的一位（newtable 的值）按位与操作是 0 或 1 就行，0 的话索引就不变，1 的话索引变成原索引加上扩容前数组

而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。即，碰撞率会增大。

哈希表的容量一定要是2的整数次幂。

首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；

其次，length为2的整数次幂为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1(这取决于h的值)，即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。

而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了一半的空间。

因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列

由于存在链表和红黑树互换机制，搜索时间呈对数 O(log(n))级增长，而非线性O(n)增长

扰动函数

扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）

扩容操作时，会new一个新的Node数组作为哈希桶，然后将原哈希表中的所有数据(Node节点)移动到新的哈希桶中，相当于对原哈希表中所有的数据重新做了一个put操作。所以性能消耗很大，可想而知，在哈希表的容量越大时，性能消耗越明显。

扩容时，如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位，或者扩容后的下标，即high位。 high位= low位+原哈希桶容量

运算

与运算替代模运算

static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值  
    return h & (length-1);  //这里不能随便算取，用 hash&(length-1) 是有原因的，这样可以确保算出来的索引是在数组大小范围内，不会超出  
}

除法效率低，与运算效率高

hash & (table.length-1)
hash % (table.length)

判断扩容后，节点e处于低区还是高区

if ((e.hash & oldCap) == 0)

参考链接

https://baiqiantao.github.io/Java/%E9%9B%86%E5%90%88/3AFbAb/#HashMap%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84

根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：

如果这两个 Entry 的 key 的 hashCode() 相同，那它们的存储位置相同。

如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value
如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部

loadFactor的默认值为0.75

fail-fast 策略

HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了 map，那么将抛出 ConcurrentModificationException。

这一策略在源码中是通过 modCount 域实现的，modCount 就是修改次数，对 HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount

issues

HashMap特性？
HashMap存储键值对，实现快速存取数据；允许null键/值；非同步；不保证有序(比如插入的顺序)，实现map接口。

HashMap的原理，内部数据结构？

HashMap是基于hashing的原理，底层使用哈希表(数组 + 链表)实现
里边最重要的两个方法put、get，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。
存储对象时，我们将K/V传给put方法时，它调用key的hashCode计算hash从而得到bucket位置，进一步存储
HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)
获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对
如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

讲一下 HashMap 中 put 方法过程？

对key的hashCode做hash操作，然后再计算在bucket中的index(1.5 HashMap的哈希函数)
如果没碰撞直接放到bucket里；
如果碰撞了，以链表的形式存在buckets后；
如果节点已经存在就替换old value(保证key的唯一性)
如果bucket满了(超过阈值，阈值=loadfactor*current capacity，load factor默认0.75)，就要resize。

get()方法的工作原理？

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。
如果产生碰撞，则利用key.equals()方法去链表中查找对应的节点。

HashMap中hash函数怎么是是实现的？

对key的hashCode做hash操作：高16bit不变，低16bit和高16bit做了一个异或
通过位操作得到下标index：h & (length-1)

还有哪些 hash 的实现方式？
还有数字分析法、平方取中法、分段叠加法、除留余数法、伪随机数法。

HashMap 怎样解决冲突？
HashMap中处理冲突的方法实际就是链地址法，内部数据结构是数组+单链表。

当两个键的hashcode相同会发生什么？

因为两个键的Hashcode相同，所以它们的bucket位置相同，会发生“碰撞”。
HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

抛开 HashMap，hash 冲突有那些解决办法？
开放定址法、链地址法、再哈希法。

如果两个键的hashcode相同，你如何获取值对象？

重点在于理解hashCode()与equals()。
通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。
两个键的hashcode相同会产生碰撞，则利用key.equals()方法去链表或树（java1.8）中去查找对应的节点。

针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？

将链表转为红黑树，实现 O(logn) 时间复杂度内查找。
JDK1.8 已经实现了。

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？
扩容。这个过程也叫作rehashing，大致分两步：

扩容：容量扩充为原来的两倍（2 * table.length）；
移动：对每个节点重新计算哈希值，重新计算每个元素在数组中的位置，将原来的元素移动到新的哈希表中。

补充：

loadFactor：加载因子。默认值DEFAULT_LOAD_FACTOR = 0.75f；
capacity：容量；
threshold：阈值=capacity*loadFactor。当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍；
size：HashMap的大小，它是HashMap保存的键值对的数量。

为什么String, Interger这样的类适合作为键？

String, Interger这样的类作为HashMap的键是再适合不过了，而且String最为常用。
因为String对象是不可变的，而且已经重写了equals()和hashCode()方法了。
不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。
不可变性还有其他的优点，如线程安全。
因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

HashMap与HashTable区别

Hashtable可以看做是线程安全版的HashMap，两者几乎“等价”（当然还是有很多不同）。
Hashtable几乎在每个方法上都加上synchronized（同步锁），实现线程安全。
HashMap可以通过 Collections.synchronizeMap(hashMap) 进行同步。

区别

HashMap继承于AbstractMap，而Hashtable继承于Dictionary；
线程安全不同。Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。而HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理；
null值。HashMap的key、value都可以为null。Hashtable的key、value都不可以为null；
迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException。
容量的初始值和增加方式都不一样：HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；
添加key-value时的hash值算法不同：HashMap添加元素时，是使用自定义的哈希算法。Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。
速度。由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。

阈值为８

TreeNodes占用空间是普通Nodes的两倍
理想情况下使用随机的哈希码，容器中节点分布在hash桶中的频率遵循泊松分布，按照泊松分布的计算公式计算出了桶中元素个数和频率的对照表，可以看到链表中元素个数为8时的概率已经非常非常小，所以根据概率统计选择了8。

理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006

元素个数小于8，查询成本高，新增成本低。

元素个数大于8，查询成本低，新增成本高。

线程不安全

https://blog.csdn.net/mydreamongo/article/details/8960667

put操作，在hashmap做put操作的时候会调用到以上的方法。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

delete, 当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改

final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
 
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
 
        return e;
    }

resize, 当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

HashMap源码