全栈 基础知识 底层原理 Map

全栈之路-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会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据
FEATURED TAGS
全栈 基础知识 底层原理 Map
FRIENDS