全栈之路-map问题汇总

时间太宽,指缝太瘦,我从水墨江南打马过,从一生走到一世,追忆从前,却雨碎江南。而这独夜里的痴痴眸子,不知可曾记得的人还记得

Posted by yishuifengxiao on 2020-08-29

一 HashMap底层原理

1.1 HashMap的特性

  • HashMap存储键值对实现快速存取,允许为null。key值不可重复,若key值重复则覆盖。
  • 非同步,线程不安全。
  • 底层是hash表,不保证有序(比如插入的顺序)

1.2 HashMap的底层原理

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

HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

1.3 put是如何实现

  1. 计算关于key的hashcode值(与Key.hashCode的高16位做异或运算)
  2. 如果散列表为空时,调用resize()初始化散列表
  3. 如果没有发生碰撞,直接添加元素到散列表中去
  4. 如果发生了碰撞(hashCode值相同),进行三种判断
    4.1: 若key地址相同或者equals后内容相同,则替换旧值
    4.2: 如果是红黑树结构,就调用树的插入方法
    4.3:链表结构,循环遍历直到链表中某个节点为空,尾插法进行插入,插入之后判断链表个数是否到达变成红黑树的阙值8;也可以遍历到有节点与插入元素的哈希值和内容相同,进行覆盖。
  5. 如果桶满了大于阀值,则resize进行扩容

哈希冲突

如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

1.4 扩容原理

谈一下hashMap中什么时候需要进行扩容,扩容resize()又是如何实现的

调用场景

  • 初始化数组table

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

实现过程

1.通过判断旧数组的容量是否大于0来判断数组是否初始化过

否:进行初始化

  • 判断是否调用无参构造器,
    • 是:使用默认的大小和阙值
    • 否:使用构造函数中初始化的容量,当然这个容量是经过tableSizefor计算后的2的次幂数

是:进行扩容,扩容成两倍(小于最大值的情况下),之后在进行将元素重新进行与运算复制到新的散列表中

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

1.5 get是如何实现

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

1.6 hash函数是怎么实现

谈一下HashMap中hash函数是怎么实现的?还有哪些hash函数的实现方式

对key的hashCode做hash操作,与高16位做异或运算

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

1.7 为什么不直接将key作为哈希值而是与高16位做异或运算

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

HashMap默认初始化长度为16,并且每次自动扩展或者是手动初始化容量时,必须是2的幂。

1.8 谈一下当两个对象的hashCode相等时会怎么样

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

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

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

1.10 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办

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

1.11 HashMap和HashTable的区别

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

不同点:

  • HashMap允许Key-value为null,hashTable不允许;
  • hashMap没有考虑同步,是线程不安全的。hashTable是线程安全的,给api套上了一层synchronized修饰;
  • HashMap继承于AbstractMap类,hashTable继承与Dictionary类。
  • 迭代器(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()。

1.12 请解释一下HashMap的参数loadFactor,它的作用是什么

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

1.13 传统hashMap的缺点(为什么引入红黑树?

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

1.14 平时在使用HashMap时一般使用什么类型的元素作为Key

选择Integer,String这种不可变的类型,像对String的一切操作都是新建一个String对象,对新的对象进行拼接分割等,这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的,

二 ConcurrentHashMap原理

2.1 基本原理

ConcurrentHashMap是Java5中新增加的一个线程安全的Map集合,可以用来替代HashTable

ConcurrentHashMap采用了非常精妙的"分段锁"策略,ConcurrentHashMap的主干是个Segment数组。Segment继承了ReentrantLock,所以它就是一种可重入锁(ReentrantLock)。在ConcurrentHashMap,一个Segment就是一个子哈希表,Segment里维护了一个HashEntry数组,并发环境下,对于不同Segment的数据进行操作是不用考虑锁竞争的。

ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据,但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下,效率很高。坏处是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据,期间线程B调用get,则只能get到目前为止已经顺利插入的部分数据。

2.2 1.8版本下变化

JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树

  1. JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
  2. JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了
  3. JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档
  4. JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock,我觉得有以下几点
    1. 因为粒度降低了,在相对而言的低粒度加锁方式,synchronized并不比ReentrantLock差,在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优势就没有了
    2. JVM的开发团队从来都没有放弃synchronized,而且基于JVM的synchronized优化空间更大,使用内嵌的关键字比使用API更加自然
    3. 在大量的数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存,虽然不是瓶颈,但是也是一个选择依据

自定义评论 pages