Android面试 HashMap算法

基于hashing的原理，jdk8后采用数组+链表+红黑树的数据结构。我们通过put和get存储和获取对象。当我们给put()方法传递键和值时，先对键做一个hashCode()的计算来得到它在bucket数组中的位置来存储Entry对象。当获取对象时，通过get获取到bucket的位置，再通过键对象的equals()方法找到正确的键值对，然后在返回值对象。

当数组table的size达到阙值时即++size > load factor capacity 时，也是在putVal函数中。

扩容需要重新分配一个新数组，新数组是老数组的2倍长，然后遍历整个老结构，把所有的元素挨个重新hash分配到新结构中去。

对key的hashCode进行hashing，与运算计算下标获取bucket位置，如果在桶的首位上就可以找到就直接返回，否则在树中找或者链表中遍历找，如果有hash冲突，则利用equals方法去遍历链表查找节点。

对key的hashCode做hash *** 作，与高16位做异或运算。

还有平方取中法，除留余数法，伪随机数法。

因为数组位置的确定用的是与运算，仅仅最后四位有效，设计者将key的哈希值与高16为做异或运算使得在做&运算确定数组的插入位置时，此时的低位实际是高位与低位的结合，增加了随机性，减少了哈希碰撞的次数。

会产生哈希碰撞，若key值相同则替换旧值，不然链接到链表后面，链表长度超过阙值8就转为红黑树存储。

HashCode相同，通过equals比较内容获取值对象。

超过阙值会进行扩容 *** 作，概括的讲就是扩容后的数组大小是原数组的2倍，将原来的元素重新hashing放入到新的散列表中去。

相同点：都是存储key-value键值对的

不同点：

loadFactor表示HashMap的拥挤程度，影响hash *** 作到同一个数组位置的概率。默认loadFactor等于075，当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，在HashMap的构造器中可以定制loadFactor。

JDK 18 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 18 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。但是链表大于8的概率是非常非常低的。

选择Integer，String这种不可变的类型，像对String的一切 *** 作都是新建一个String对象，对新的对象进行拼接分割等，这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的。如果要使用自定义类做为Key，就需要重写hashCode()以及equals()方法。红黑树在做比较的时候使用的是SystemidentityHashCode()方法，是不需要做特殊处理的。

更多内容戳这里（整理好的各种文集）

拉链法

创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

头插

尾插

在 transfer() 方法中，因为新的 Table 顺序和旧的不同，所以在多线程同时扩容情况下，会导致第二个扩容的线程next混乱，本来是 A -> B ，但t1线程已经 B -> A 了，所以就 成环 了。

18扔掉了 transfer() 方法，用 resize() 扩容：

使用 do while 循环一次将一个链表上的所有元素加到链表上，然后再放到新的 Table 上对应的索引位置。

JDK17的时候使用的是数组+ 单链表的数据结构。但是在JDK18及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率）

18的索引 只用了一次移位，一次位运算就确定了索引，计算过程优化。

二者的 hash 扰动函数也不同，17有4次移位和5次位运算，18只有一次移位和一次位运算

初始容量和加载因子会影响 HashMap 的性能：

常说的capacity指的是 DEFAULT_INITIAL_CAPACITY （初始容量），值是 1<<4 ，即16；

capacity() 是个方法，返回数组的长度。

在hashMap构造函数中，赋值为 DEFAULT_LOAD_FACTOR（075f）

加载因子可设为>1，即永不会扩容，(牺牲性能节省内存)

Map中现在有的键值对数量，每 put 一个entry， ++size

数组扩容阈值。

即：HashMap数组总容量 加载因子（16 075 = 12）。当前 size 大于或等于该值时会执行扩容 resize() 。扩容的容量为当前 HashMap 总容量的两倍。比如，当前 HashMap 的总容量为 16 ，那么扩容之后为 32

获取哈希码， object 的 hashCode() 方法是个本地方法，是由C实现的。

理论上hashCode是一个int值，这个int值范围在-2147483648和2147483648之间，如果直接拿这个hashCode作为HashMap中数组的下标来访问的话，正常情况下是不会出现hash碰撞的。

但是这样的话会导致这个HashMap的数组长度比较长，长度大概为40亿，内存肯定是放不下的，所以这个时候需要把这个hashCode对数组长度取余，用得到的余数来访问数组下标。

高低位异或，避免高位不同，低位相同的两个 hashCode 值 产生碰撞。

为什么 重写 equals 时必须重写 hashCode 方法？

equals()既然已能对比的功能了，为什么还要hashCode()呢？ 因为重写的equals()里一般比较的比较全面比较复杂，这样效率就比较低，而利用hashCode()进行对比，则只要生成一个hash值进行比较就可以了，效率很高。

hashCode()既然效率这么高为什么还要equals()呢？ 因为hashCode()并不是完全可靠，有时候不同的对象他们生成的hashcode也会一样（生成hash值得公式可能存在的问题），所以hashCode()只能说是大部分时候可靠，并不是绝对可靠，

A：两个时候

Node[] table，即哈希桶数组，哈希桶数组table的长度length大小必须为2的n次方

075 2^n 得到的都是整数。

把bucket扩充为2倍，之后重新计算index，把节点再放到新的bucket中

hashCode是很长的一串数字，<font color = orange>(换成二进制，此元素的位置就是后四位组成的 ( 数组的长度为16，即4位 ))</font>

eg

<font color = gray>1111 1111 1111 1111 0000 1111 0001</font> 1111 (原索引是后面四个，索引是15)

扩容后：

<font color = gray>1111 1111 1111 1111 0000 1111 000</font> 1 1111 (新的索引多了一位)（多出来这个，或1或0 随机，完全看hash）

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于 新增的1bit是0还是1可以认为是随机的 （hashCode里被作为索引的数往前走了一个，走的这个可能是0，也可能是1），因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

用Iterator有两种方式，分别把迭代器放到entry和keyset上，第一种更推荐，因为不需要再 get(key)

可减少哈希碰撞

可以，null的索引被设置为0，也就是Table[0]位置

在JDK7中，调用了 putForNullKey() 方法，处理空值

JDK8中，则修改了hash函数，在hash函数中直接把 key==null 的元素hash值设为0，

再通过计算索引的步骤

得到索引为0；

对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回； 如果有冲突，则通过keyequals(k)去查找对应的Entry;

调用 putValue :

是以31为权，每一位为字符的ASCII值进行运算，用int的自然溢出来等效取模。

假设String是ABC，

可以使用ConcurrentHashmap，Hashtable等线程安全等集合类。

Divenier总结：

要看作为key的元素的类如何实现的，如果修改的部分导致其 hashcode 变化，则修改后不能 get() 到；

如修改部分对 hashcode 无影响，则可以修改。

开放定址法、链地址法(拉链法)、再Hash法

部分

参考资料：

>

  1底层由链表+数组实现

  2可以存储null键和null值

  3线性不安全

  4初始容量为16，扩容每次都是2的n次幂（保证位运算）

  5加载因子为075，当Map中元素总数超过Entry数组的075，触发扩容 *** 作

  6并发情况下，HashMap进行put *** 作会引起死循环，导致CPU利用率接近100%

  （1）HashMap底层实现数据结构为数组+链表的形式，JDK8及其以后的版本中使用了数组+链表+红黑树实现，解决了链表太长导致的查询速度变慢的问题。

  （2）简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。HashMap通过key的HashCode经过扰动函数处理过后得到Hash值，然后通过位运算判断当前元素存放的位置，如果当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。当Map中的元素总数超过Entry数组的075时，触发扩容 *** 作，为了减少链表长度，元素分配更均匀。

DEFAULT_INITIAL_CAPACITY ：默认的初始化容量，1<<4位运算的结果是16，也就是默认的初始化容量为16。当然如果对要存储的数据有一个估计值，最好在初始化的时候显示的指定容量大小，减少扩容时的数据搬移等带来的效率消耗。同时，容量大小需要是2的整数倍。

MAXIMUM_CAPACITY ：容量的最大值，1 << 30位，2的30次幂。

  DEFAULT_LOAD_FACTOR ：默认的加载因子，设计者认为这个数值是基于时间和空间消耗上最好的数值。这个值和容量的乘积是一个很重要的数值，也就是阈值，当达到这个值时候会产生扩容，扩容的大小大约为原来的二倍。

TREEIFY_THRESHOLD ：因为jdk8以后，HashMap底层的存储结构改为了数组+链表+红黑树的存储结构（之前是数组+链表），刚开始存储元素产生碰撞时会在碰撞的数组后面挂上一个链表，当链表长度大于这个参数时，链表就可能会转化为红黑树，为什么是可能后面还有一个参数，需要他们两个都满足的时候才会转化。

UNTREEIFY_THRESHOLD ：介绍上面的参数时，我们知道当长度过大时可能会产生从链表到红黑树的转化，但是，元素不仅仅只能添加还可以删除，或者另一种情况，扩容后该数组槽位置上的元素数据不是很多了，还使用红黑树的结构就会很浪费，所以这时就可以把红黑树结构变回链表结构，什么时候变，就是元素数量等于这个值也就是6的时候变回来（元素数量指的是一个数组槽内的数量，不是HashMap中所有元素的数量）。

   MIN_TREEIFY_CAPACITY ：链表树化的一个标准，前面说过当数组槽内的元素数量大于8时可能会转化为红黑树，之所以说是可能就是因为这个值，当数组的长度小于这个值的时候，会先去进行扩容，扩容之后就有很大的可能让数组槽内的数据可以更分散一些了，也就不用转化数组槽后的存储结构了。当然，长度大于这个值并且槽内数据大于8时，那就转化为红黑树吧。

以上就是关于Android面试 HashMap算法全部的内容，包括:Android面试 HashMap算法、HashMap面试问题整理、HashMap的底层数据结构以及主要参数等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！