JAVA面试点滴整理——全面剖析

JAVA面试必选——HashMap全方位剖析

2019-01-28  本文已影响21人  从林战士们

HashMap全方位剖析

常见HashMap面试问答

HashMap是不是有序的？

不是有序的。

有没有有序的Map实现类？

TreeMap和linkedHashMap。

TreeMap和LinkedHashMap是如何保证它的顺序的？

TreeMap是通过实现SortMap接口，能够把它保存的键值对根据key排序，基于红黑树，从而保证TreeMap中所有键值对处于有序状态。LinkedHashMap则是通过插入排序（就是PUT的时候的顺序是什么，取出来的时候就是什么顺序）和访问顺序（改变排序把访问过的放到底部）让键值有序。

TreeMap和LinkedHashMap的有序实现那个更好呢？

  1. 为什么要用HashMap？
  1. HashMap的工作原理是什么？

HashMap的简化的模拟数据结构:

Node[] table = new Node[16];//散列桶初始化，Table
class Node {
    hash; //hash值
    key; //键
    value; //值
    node next; //用于指向链表的下一层（产生冲突，使用拉链法）
}

以下是具体的put过程（1.8）

  1. 对key求Hash值，然后再计算下标
  2. 如果没有碰撞，直接放入桶中（碰撞的意思是计算得到的Hash值相同，需要放到一个bucket中）
  3. 如果碰撞发生了，以链表的方式链接到后面
  4. 如果链表长度超过阈值（TREEIFY THRESHOLD==8），就把链表转成红黑树，链表长度低于6，就把红黑树转回链表
  5. 如果节点已经存在就替换旧值
  6. 如果桶满了（容量16*加载因子0.75），就需要resize（扩容2倍后重排）

以下是具体get过程
考虑特殊情况：如果两个键的HashCode相同，如何获取值对象？
当我们调用get()方法，HashMap会使用键对象的HashCode找到bucket位置，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的对象。

  1. 有什么方法可以减少碰撞？

原理：两个不相等的对象返回不同的HashCode，碰撞可能发生的机会小一些。同时也意味着存链表结构减小，使用GET方法取值的话就不会频繁调用equal()方法，从而提高HashMap的性能，扰动函数的作用就是Hash()方法内部的算法实现，目的是让不同对象返回不同的HashCode。

  1. HashMap 中hash函数是如何实现的？

HashMap中想要找到某个元素，需要根据key的hash值来找到对应数据中具体的位置。
由于HashMap的数据结构是数组和链表结合，一般情况我们希望HashMap中的元素位置尽可能均匀分布，最好的情况就是每个位置上只有一个元素。这样使用hash算法计算这个位置的时候，立刻就能知道对应位置的元素是我们需要的，同时也不用去遍历链表。因此，首先需要把HashCode对数组长度取模运算，这样的好处就是元素分布的相对均匀。
但由于取模运算消耗相对比较大，有没有更快速、消耗更小的方式处理，通过读JDK1.8源码了解到如下：

Jdk源码hash()方法

static final int hash(Object key){
    if(key == null){
        return 0；
    }
    int h;
    h = key.hashCode();返回散列值也就是HashCode
    
    return （n-1）&(h ^ (h >>> 16));
}

h = hashCode(): 1111 1111 1111 1111 1111 0000 1110 1010
调用hashCode()

h: 1111 1111 1111 1111 1111 0000 1110 1010
h >>> 16: 0000 0000 0000 0000 1111 1111 1111 1111
计算Hash

hash = h ^(h >>> 16): 1111 1111 1111 1111 0000 1111 0001 0101

(n-1) & hash: 0000 0000 0000 0000 0000 0000 0000 1111
1111 1111 1111 1111 1111 1111 0001 0101
计算下标

0101 = 5

简单来说就是：

  1. 拉链法导致的链表过深，选择红黑树的好处是什么，为什么不用二叉树代替？但在链表长度比较短的时候又不选择使用红黑树？

不选择二叉树的原因就是二叉查找树在特殊情况下会变成一条线性结构（就跟原有链表结构是相同的，造成了很深的层次），遍历查找会非常慢。而红黑树在插入新数据后可以通过使用左旋、右旋、变色这些操作来保持平衡。引入红黑树为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所消耗的资源要比遍历线性链表要少，所以在长度比较短的情况下，根本不需要引入红黑树，移入反而更慢；但是在长度大于阈值8的情况下，选择使用红黑树更快。

6. 对红黑树的认知

7. 解决hash碰撞的更多方法？

8.如果HashMap的大小超过了负载因子（load factor）定义的容量怎么办？

HashMap默认的负载因子大小为0.75.也就是说，当一个Map填满75%的bucket时候，和其他集合类一样（比如ArrayList），将会创建原来HashMap大小的两倍的bucket数组来重新调整Map大小，并将原来的对象放入新的bucket数组中。这个过程叫做rehashing。
因为它调用hash方法找到新的bucket位置。这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置。

9.重新调整HashMap大小存在什么问题

重新调整HashMap的大小的时候，确实存在条件竞争。
因为如果两个线程都发现HashMap需要重新调整大小了，他们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序有可能会反过来。因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部。是由于避免尾部遍历（tail traversing）。如果条件竞争发生了，那么久死循环了。多线程的环境下不使用HashMap。
为什么多线程会导致死循环，它是怎么发生的？
HashMap的容量是有限的。当经过多次元素插入，使得HashMap达到一定饱和度时，key映射位置发生冲突的几率会逐渐提高。这时候，HashMap需要扩展它的长度，也就是进行Resize.

  1. 扩容：创建一个新的Entry空数组，长度是原数组的2倍
  2. rehash：遍历原来的Entry数组，把所有的Entry重新Hash到新数组

10.HashTable

11.HashMap与HashTable区别

12.可以使用CocurrentHashMap代替HashTable吗？

13.ConcurrentHashMap(jdk 1.7)

首先第一步的时候会尝试获取锁，如果获取失败肯定就会有其他线程存在竞争，则利用scanAndLockForPut()自旋获取锁

13.ConcurrentHashMap(jdk1.8)

ConcurrentHashMap抛弃了Segment分段锁，采用了CAS + synchronized来保证并发安全性。其中val next都用了volatile修饰，保证了可见性。
最大特点是引入了CAS
借助Unsafe来实现native code.CAS有3个操作数，内存值V、旧的预期值A、要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做，Unsafe借助CPU指令cmpxchg来实现。
CAS使用实例
对sizeCtl的控制都是用CAS来实现的：

CAS会出现的问题：ABA

解决方案：对变量增加一个版本号，每次修改，版本号加1，比较的时候比较版本号

PUT过程

  1. 根据key计算HashCode
  2. 判断是否需要进行初始化
  3. 通过key定位出的Node，如果为空表示当前位置可以写入数据，利用CAS尝试写入，是被则自旋保证成功
  4. 如果当前位置的HashCode == MOVED == -1,则需要进行扩容
  5. 如果不满足，则利用synchronized锁写入数据
  6. 如果数量大于TREEIFY-THRESHOLD则要转换为红黑树

GET过程

  1. 根据计算出来的HashCode寻址，如果就在桶上那么直接返回值
  2. 如果是红黑树那就按照树的方式获取值
  3. 就不满足那就按照链表的方式遍历获取值

结尾
ConcurrentHashMap在Java8中存在一个bug会进入死循环，原因是递归创建ConcurrentHashMap对象，但是在JDK1.9已经修复了，具体案例如下代码：

public class ConcurrentHashMapDemo{
    private Map<Integer,Integer> cache = new ConcurrentHashMap<>(15);
    
    public static void main(String[] args){
        ConcurrentHashMapDemo ch = new ConcurrentHashMapDemo();
        System.out.println(ch.fibonaacci(80));
    }
    
    public int fibonaacci(Integer i){
        if(i == 0 || i == 1){
            return i;
        }
        
        return cache.computeIfAbsent(i,(key) ->{System.out.println("fibonaacci : "+ key);
        return fibonaacci(key -1)+fibonaacci(key -2);
        });
    }
}
上一篇 下一篇

猜你喜欢

热点阅读