东东
发布于 2022-10-09 / 29 阅读 / 0 评论 / 0 点赞

HashMap

#HashMap

概述

先看代码HashMap的节点

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;

Node是一个内部类，这里的key为键，value为值，next指向下一个元素，可以看出HashMap中的元素不是一个单纯的键值对，还包含下一个元素的引用。

  • 哈希表实现，元素无序
  • 键不可重复，键可以为null（只有一个null）
  • 值可以重复
  • 多线程不安全

如何能够线程安全
还可以使用Collections.synchronizedMap方法，对方法进行加同步锁
在竞争激烈的多线程环境下性能依然也非常差，不推荐使用！

底层实现原理

实现

数组+链表/红黑树

image-1666076061939

  • 当链表元素大于8时，且数组长度大于64时，会转为红黑树进行存储（避免链表过长，查询过慢）
  • 当链表元素小于6时，会转为链表进行存储
  • 6和8是为了避免个数频繁变化导致链表和红黑树频繁转换

java1.7 之前是数组+链表 ，之后是 数组+链表+红黑树

为什么是红黑树？

链表，是为了解决Hash碰撞、冲突，产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。引入了红黑树，数据查询时间复杂度为O(logN)

在链表中查找数据必须从第一个元素开始一层一层往下找，如果hash冲突多，那么查询的效率就越低，接近O(N)
实际上，使用普通二叉树也可以。但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。

为什么不直接采用红黑树？

因为红黑树需要进行左旋，右旋操作， 而单链表不需要；

  • 如果元素小于8个，查询成本高，新增成本低；
  • 如果元素大于8个，查询成本低，新增成本高。

用什么对象作为key比较合适？

一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。

  1. 因为字符串是不可变，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是 HashMap 中的键往往都使用字符串的原因。
  2. 因为获取对象的时候要用到equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了hashCode() 以及 equals() 方法。

特点

数组的特点：查询效率高，插入，删除效率低。
链表的特点：查询效率低，插入删除效率高。
在HashMap底层使用数组加（链表或红黑树）的结构完美的解决了数组和链表的问题，使得查询和插入，删除的效率都很高。

Hash方法

元素的hashCode

public native int hashCode();

调用hashCode()这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的对象地址和内容有关。

如何hash

static final int hash(Object key) {
    int h;
    //hashCode是父类的Object方法
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash

为什么要向右移动16位？为什么要进行与或运算？

其中>>>无符号右移，低位挤走，高位补0；^ 为按位异或，即转成二进制后，相异为 1，相同为 0

& 运算符，两个操作数中位都为1，结果才为1，否则结果为0，所以结果向 0 靠拢。
| 运算符，两个操作数中有一个为1，结果就为1，否则为0，所以结果会向 1 靠拢。

  1. 首先16位是因为hash后是int类型，32位，高位、低位各16位对半；
  2. 与原哈希值做异或运算，这样就混合了原哈希值中的高位和低位，不仅保留了低位的信息，还夹杂了高位的特征,大大增加了随机性,又可以让 0、1 均匀（不像&、| 靠拢），所以得出的hash值会更均匀，也就避免了hash冲突。
  3. 最终目的还是为了让哈希后的结果更均匀的分布，减少哈希碰撞，提升hashmap的运行效率

对于一个长度为length的数组，假设其为2的n次幂，length-1的结果就是n个1，其与任何数相与的结果都是保留其低位，间接性的实现了取模的效果。

为什么不直接取模？

但是我们为什么不直接取模呢，这是因为&运算直接使用二进制位计算，能更快的达到效果。由于数组长度恒为2的n次幂，所以该结论必然存在。
这也是我们每次扩容都是2倍的原因之一。

解决hash冲突的方法有哪些？HashMap用的哪种？

开放定址法、再哈希法、链地址法（拉链法），HashMap采用链地址法

  • 开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H§,如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。
  • 再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。
  • 链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

容量

HashMap中有两个重要的参数：初始容量大小和加载因子

默认容量

默认初始容量为16

扩容

  • 默认扩容的加载因子为0.75
  • 触发扩容时，容量自动变为两倍
  • 扩容后，元素会重新Hash并重新放入

扩容步骤

  1. 先生成新数组
  2. 遍历老数组中的每个位置上的链表或红黑树
  3. 如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去
  4. 如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置
    1. 统计每个下标位置的元素个数
    2. 如果该位置下的元素个数超过了8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置
    3. 如果该位置下的元素个数没有超过8，则生成一个链表，并将链表的头节点添加到新数组的对应位置
  5. 所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

jdk1.8的优化

  1. resize 之后，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）。不需要像 JDK1.7 的实现那样重新计算hash ，只需要看看原来的 hash 值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引 + oldCap ”。这个设计非常的巧妙，省去了重新计算 hash 值的时间。
  2. JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK1.8 不会倒置，使用尾插法。

添加元素 put()

使用尾插法
put

  1. 首先判断数组是否为空？如果为空则进行初始化；
  2. 计算该元素再数组中的索引位置；（使用h&(h-1)）
  3. 判断当前位置的table节点有无元素，如果没有元素，则新元素直接放入该节点，节点的next为null，并返回；
  4. 如果有元素，则需要分为以下几种情况；
    1. 如果和当前位置的元素的hash值相同，需要判断内容是否相同，如果相同，则进行覆盖；
    2. 如果当前位置是红黑树，则按照红黑树的方法插入或更改树节点；
    3. 如果当前位置位链表，则需要进行遍历至末尾进行尾插元素，如果在遍历的过程中发现相同key，则进行覆盖。如果插入元素后，链表的长度大于8，且数组长度大于64，则还需要将链表转为红黑树；
  5. 最后如果map内的元素个数超过了阈值，则需要进行扩容。

多线程

HashMap为什么线程不安全？

  • 多线程的put可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。
  • put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题。此问题在JDK 1.7和 JDK 1.8 中都存在。
  • 多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

HashMaph和HashTable的区别（了解）

  1. 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用ConcurrentHashMap 吧！）；
  2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
  3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
  4. 初始容量大小和每次扩充容量大小的不同 ： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2 的幂次方。
  5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
  6. 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

https://blog.csdn.net/androidstarjack/article/details/124507171
https://juejin.cn/post/6844903966103306247
https://www.javazhiyin.com/71751.html
https://blog.csdn.net/qq_31780525/article/details/77431970
https://www.cnblogs.com/zeroingToOne/p/9522814.html

HashSet
Vector