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)
根据该 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);
}
网友评论