合集目录

Java语法专题3: HashMap

谈谈 HashMap 的特性 存储KV键值对, 实现快速存取, key和value都允许为null、key值唯一, 重复则覆盖.key为null时, 内部使用的是0这个值底层数据结构是数组非线程安全无顺序

谈谈 HashMap 的工作机制

谈谈 HashMap 的底层原理 从 JDK8 开始采用数组 + 链表 + 红黑树的数据结构, 一直到JDK11基本没变存储对象时, 先对键做 hash 计算(基于hashCode), 得到它在bucket数组中的位置, 存储Entry对象获取对象时, 同样地先定位到bucket的位置, 再通过键对象的equals()方法找到正确的键值对, 返回值对象

HashMap 中 get 是如何实现的

先对键做 hash 计算(基于hashCode), 得到它在bucket数组中的位置, 然后在这个bucket的树或者链表中遍历查找, 直到找到满足 equals 的节点.

HashMap 中 put 是如何实现的 计算关于key的hashcode(与Key.hashCode的高16位做异或运算)散列表为空时调用resize()初始化散列表如果没有发生碰撞，直接添加元素到散列表如果发生了碰撞(hashCode值相同), 进行三种判断

若key地址相同或者equals后内容相同，则替换旧值如果是红黑树结构，就调用树的插入方法如果是链表结构, 循环遍历: 若遍历到有节点与插入元素的哈希值和内容相同则进行覆盖; 若无相同则尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阈值8、如果桶容量超过阀值，则resize进行扩容

HashMap 的大小超过了负载因子定义的容量会怎样处理?

HashMap 的扩容是如何工作的

扩容的时机

HashMap 在初始化数组Table和当数组Table容量达到阈值时, 在putVal函数中触发扩容

阈值的计算

size > load factor * capacity

扩容的过程

扩容需要重新分配一个新数组, 新数组长度是旧数组的2倍, 遍历旧数组，将元素重新hash分配到新结构中去.

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

hash的计算方法是: 对key对象计算hashCode, 再将 hashCode 与 hashCode 的高16bit做XOR、如果key是null, 则直接返回0.

以下详细说明

hash 函数的代码

hash计算是 HashMap 实现机制中很重要的一环, 对任何对象(包括null), 返回一个int类型的hash值、其实现的代码为

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

Object 的 hashCode()

底层的实现, 实际上是 Object 的 hashCode() 函数, 这个函数是native的, 由 C/C++ 提供

public native int hashCode();

hashCode()这个函数有三个特性:

对同一个对象多次调用, 返回的结果一定相同对满足equals(Object)的两个对象分别调用, 返回的结果一定相同对于不满足equals(Object)的两个对象分别调用, 返回的结果不一定不同

为什么要对 hashCode() 的结果做高16位的异或运算 h >>> 16是无符号位移运算, Java的int是4个字节16bit, 这个运算将高16bit移动到低16bitHashMap 默认初始化容量为16, 每次自动扩展或者是手动初始化容量时, 必须是2的N次幂将结果与自身的高16bit进行XOR运算, 因为HashMap的增长使用容量是2的N次幂, 将这个作为掩码, 如果hash值只在比这个掩码更高位的bit上有变化, 那么产生的结果总是碰撞的、这时候需要将高位的变化体现到低位上降低碰撞的概率位移和XOR是代价最低的运算、XOR some shifted bits in the cheapest possible way to reduce systematic lossage.

在低位产生大量碰撞的例子

如果不做高位异或会造成碰撞的例子是均匀增长的浮点数, 参考以下代码

public static void main(String[] args) { float i; for (i = 0.1f; i < 1000; i++) { System.out.println(Float.valueOf(i).hashCode()); }}

i的初始值可以修改为0, 0.1f以及其他值, 观察输出, 可以看到在某些小数部分的情况下(例如0和0.1f), 最低位的结果是固定的0, 2, 4, 6, 8、如果将上面的循环步长调整为5,

public static void main(String[] args) { float i; for (i = 0.1f; i < 1000; i = i + 5) { System.out.println(Float.valueOf(i).hashCode()); }}

可以看到在输出的后半部分, 结果的个位全部为8

...1146963558114704547811471273981147209318114729123811473731581147455078

如果在实际应用中正好碰到了这种情况, HashMap 的效率将变得非常低、如果是 JDK7 没有红黑树结构, 时间复杂度就是O(n), JDK8红黑树结构下对应的时间复杂度也是O(logn).

默认容量为什么是2的N次幂？

为了数据的均匀分布，减少哈希碰撞

确定数组位置是用的位运算, 若数据不是2的次幂, 则会增加哈希碰撞的次数和浪费数组空间

HashMap和HashTable的区别?

相同点

都是存储key-value键值对

不同点

HashMap 允许 Key-value为null, HashTable不允许HashMap 线程不安全, HashTable 线程安全的HashMap 继承于AbstractMap, HashTable继承于DictionaryHashMap 的迭代器(Iterator)是fail-fast迭代器, 而 Hashtable 的enumerator迭代器不是fail-fast的、所以当有其它线程改变了 HashMap 的结构(增加或者移除元素), 将会抛出 ConcurrentModificationException.容量的初始值和增加方式不一样: HashMap 默认的容量是16, 扩容时每次翻倍、Hashtable 默认容量是11, 扩容时每次将容量变为(原容量 x 2 + 1)Hash值算法不同: HashMap使用自定义的hash方法, Hashtable 直接采用的key的hashCode()

谈谈 HashMap 的 loadFactor 参数的作用

loadFactor 是 HashMap 的负载因子, 表示数组的使用率上限、默认为0.75, 当容纳的元素已经达到数组长度的75%时, 就会进行扩容

HashMap的缺点, JDK8 为什么引入红黑树?

JDK7的 HashMap 实现是数组+链表, 因为哈希计算存在碰撞的可能性, 当大量的元素都存放到同一个桶中时, 就会形成一条很长的链表, 这时 HashMap 读取时就需要遍历这个链表, 时间复杂度就是 O(n)、JDK8 引入红黑树是为了解决这个问题, 将查找时间复杂度为优化到 O(logn).