HashMap全方位剖析

常见HashMap面试问答

HashMap是不是有序的？

不是有序的。

有没有有序的Map实现类？

TreeMap和linkedHashMap。

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

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

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

---

1. 为什么要用HashMap？

• HashMap是一个散列桶（数组和链表），它存储的内容是键值对key-value映射
• HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
• HashMap是非synchronized,所以HashMap很快
• HashMap可以接受null键和值，而HashTable则不能（原因就是equals() 方法需要对象，因为HashMap是活出的API经过处理才可以）

2. HashMap的工作原理是什么？

• HashMap 是基于hashing的原理
  当我们使用put(key,value)存储对象到hashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用HashCode()方法，计算并返回的HashCode 是用于找到Map 数组的bucket位置来存储Node对象。
  这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Node。

  
  bucket模型图

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()方法去找到链表中正确的节点，最终找到要找的对象。

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

• 扰动函数可以减少碰撞

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

• 使用不变的、声明做final对象，并且采用合适的equals()和HashCode()方法，将会减少碰撞发生
  不可变性使得能够魂村不同键的HashCode，这将提高整个获取对象的速度，使用String、Integer这样的wrapper类作为键是非常好的选择。

• 为什么String、Integer这样的wrapper类适合作为键？
  因为String是常量类final类型的，在内部实现过程中已经重写equals()和HashCode()方法，常量类型不可变性作为前提条件，要计算HashCode(),必须保证键值改变，如果键值在put和get时返回的HashCode不同，就会导致HashMap中找不到相应的对象。

4. 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

简单来说就是：

• 高16bit不变，低16bit做了一个异或（得到的HashCode转化为32位二进制，前16位和后16位低16bit和高16bit做了一个异或）
• (n-1)&hash = 得到下标

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

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

6. 对红黑树的认知

• [ ] 每个节点非红即黑
• [ ] 根节点的颜色总是黑色的
• [ ] 如果节点是红色的，则它的每个子节点必须是黑色的（反之不一定）
• [ ] 每个叶子节点都是黑色的空节点（NIL节点）
• [ ] 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

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

• 开放定址法
  当冲突发生时，使用某种探测技术在散列表中形成一个探查序列。沿此探测序列逐个单元的去查找，知道找到给定的地址。按照形成探查序列的方法不同，可将开放定址法区分为限行探测方法、二次探测法、双重散列法等。
  下面给一个限行探查法的例子：
  问题：已知一组关键字为（26、36、41、38、44、15、68、12、06、51），用除余法因子是13的散列函数计算出的上述关键字的散列表。
  为了减少冲突，通常令装填因子α由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为（0，10，2，12，5，2，3，12，6，12）
  前5个关键字插入时，其相应的地址均为开放地址，故将他们直接插入T[0]、T[10]、T[2]、T[12]和T[5]中。
  当插入第5个关键字15时，其散列地址2（即h(15)= 15%13=2）已被关键字41（15和41互为同义词）占用。探查到h1(2+1)%13=3,此地址开放，所以讲15放入T[3]中。
  当插入第7个关键字68时，散列地址3已被非同义词15先占用，故将其插入到T[4]中。
  当插入第8个关键字12时，散列地址12已被同义词38占用，故探查h1=(2+3)%13=0,而T[0]也被26占用
  再探查h2=(12+2)%13=1，此地址开放，可将12插入其中。
  类似的，第9个关键字06直接插入T[6]中；而最后一个关键字51插入时，因探测地址12，0，1，。。。6均为非空，故51插入T[7]中。

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（质数为宜）
• put操作:首先进行所以计算（key.hashCode()&0x7FFFFFFF）%table.length;若在链表中找到了，则替换旧值，若未找到则继续；当总元素个数超过容量 * 加载因子时，扩容为原来2倍并重新散列；将新元素加到链表头部
• 对修改HashTable内部贡献数据的方法添加了synchronized,保证线程安全

11.HashMap与HashTable区别

• 默认容量不一样，扩容不同
• 线程安全性：HashTable安全
• 效率不同：HashTable要慢，因为加锁

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

• HashTable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它不仅仅根据同步级别对map的一部分进行上锁
• ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性
• ConcurrentHashMap和HashTable都可以用于多线程环境，但是当HashTable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要锁定很长时间。由于ConcurrentHashMap引入了分割（segmentation）,不论它变得多么大，仅仅需要锁定Map的某个部分，其他的线程不需要等到迭代完成才能访问Map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定Map的某个部分，而HashTable则会锁定整个Map

13.ConcurrentHashMap(jdk 1.7)

• ConcurrentHashMap由Segment数组和hashEntry数组和链表组成
• Segment是基于重入锁（ReentrantLock）:一个数据段竞争锁。每个HashEntry一个链表结构的元素，利用Hash算法得到索引确定归属的数据段，也就是对应到在修改时需要竞争获取的锁。ConcurrentHashMap支持CurrencyLevel（segment数组数量）的线程并发。每当一个线程占用锁访问一个segment时，不会影响到其他segment
• 核心数据如Value，以及链表都是volatile修饰的，保证了获取时的可见性
• 首先是通过key定位到segment，之后对应的segment中进行具体的put操作如下：
  1. 将当前segment中的Table通过可以的HashCode定位到hashEntry
  2. 遍历该hashEntry，如果不为空则判断传入的key 和当前遍历的key是否相等，相等则覆盖旧的Value
  3. 不为空则需要新建一个HashEntry并加入到Segment中，同时会先判断是否需要扩容
  4. 最后会接触在1中所获取当前的Segment的锁
• 虽然hashEntry中的Value是用volatile关键词修饰的，但是并不能保证并发的原子性，所以put操作时仍然需要加锁处理

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

• 尝试自旋获取锁
• 如果重试的次数达到了MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功。最后解除当前Segment的锁

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来实现的：

• -1代表table正在初始化
• N表示有-N-1个线程正在进行扩容操作
• 如果table未初始化，表示table需要初始化的大小
• 如果table初始化完成，表示table的容量，默认是table大小的0.75倍，用这个公式算0.75（n-(n>>>2))

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);
        });
    }
}