秋招知识库

主题

《面渣逆袭》Java集合框架 篇 · 第 3/4 章。原版 PDF（下载 / 打印）

Map 中，毫无疑问，最重要的就是HashMap ，面试基本被盘出包浆了，各种问法，一定要好好准备。

8.能说一下HashMap的数据结构吗？ ​

JDK1.7 的数据结构是数组+链表，JDK1.7 还有人在用？不会吧… …

说一下JDK1.8 的数据结构吧：

JDK1.8 的数据结构是数组+链表+红黑树。

数据结构示意图如下：

配图

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素如果链表长度> 8& 数组大小> =64 ，链表转为红黑树如果红黑树节点个数< 6 ，转为链表

9.你对红黑树了解多少？为什么不用二叉树/平衡树呢？ ​

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

  1. 每个节点要么是红色，要么是黑色；

  2. 根节点永远是黑色的；

  3. 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；

  4. 每个红色节点的两个子节点一定都是黑色；

  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

配图

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn) ，避免了二叉树最坏情况下的O (n) 时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

10.红黑树怎么保持平衡的知道吗？ ​

红黑树有两种方式保持平衡：旋转和染色。

旋转：旋转分为两种，左旋和右旋

配图

配图

染色：

配图

11.HashMap的put流程知道吗？ ​

先上个流程图吧:

配图

1.首先进行哈希值的扰动，获取一个新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h

>>>16);

  1. 判断t ab 是否位空或者长度为0 ，如果是则进行扩容操作。
if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  1. 根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆盖。tab[i=

(n-1)&hash])

  1. 判断t ab[i] 是否为树节点，否则向链表中插入数据，是则向树中插入节点。

  2. 如果链表中插入节点的时候，链表长度大于等于8 ，则需要把链表转换为红黑

树。treeifyBin(tab, hash);
  1. 最后所有元素处理完成后，判断是否超过阈值；threshold，超过则扩容。

12.HashMap怎么查找元素的呢？ ​

先看流程图：

配图

HashMap 的查找就简单很多：

  1. 使用扰动函数，获取新的哈希值

  2. 计算数组下标，获取节点

  3. 当前节点和k ey 匹配，直接返回

  4. 否则，当前节点是否为树节点，查找红黑树

  5. 否则，遍历链表查找

13.HashMap的哈希/扰动函数是怎么设计的? ​

HashMap 的哈希函数是先拿到 key 的hashcode ，是一个3 2 位的i nt 类型的数值，然后让hashcode 的高16 位和低1 6 位进行异或操作。

    static final int hash(Object key) {
        int h;
        // key的hashCode和key的hashCode右移16位做异或运算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这么设计是为了降低哈希碰撞的概率。

14.为什么哈希/扰动函数能降hash碰撞？ ​

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。i nt 值范围为**-2147483648~2147483647**，加起来大概 40 亿的映射空间。

只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。

假如 HashMap 数组的初始大小才 16 ，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

源码中模运算就是把散列值和数组长度 -1 做一个 "与&" 操作，位运算比取余 % 运算要快。

bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
     return h & (length-1);
}

顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 -

  1. 正好相当于一个 “ 低位掩码” 。与操作的结果就是散列值的高位全部归零，只保留低位值，用来做

数组下标访问。以初始长度 16 为例，1 6-1=15 。2 进制表示是0000000000000000000000000000

1111。和某个散列值做与操作如下，结果就是截取了最低的四位值。

配图

这样是要快捷一些，但是新的问题来了，就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。

这时候扰动函数的价值就体现出来了，看一下扰动函数的示意图：

配图

右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

15.为什么HashMap的容量是2的倍数呢？ ​

第一个原因是为了方便哈希取余：

将元素放在table 数组上面，是用hash 值% 数组大小定位位置，而HashMap 是用hash 值& ( 数组大小- 1) ，却能和前面达到一样的效果，这就得益于HashMap 的大小是2 的倍数，2 的倍数意味着该数的二进制位只有一位为1 ，而该数- 1 就可以得到二进制位上1 变成0 ，后面的0 变成1 ，再通过& 运算，就可以得到和% 一样的效果，并且位运算比% 的效率高得多

HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111*111这样形式的，这样与添加元素的

hash 值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap 的每个位置上，减少

hash 碰撞。

第二个方面是在扩容时，利用扩容后的大小也是2 的倍数，将已经产生hash 碰撞的元素完美的转移到新的table 中去我们可以简单看看HashMap 的扩容机制，HashMap 中的元素在超过负载因子* HashMap大小时就会产生扩容。

配图

16.如果初始化HashMap，传一个17的值new HashMap<> ，它会怎么处 理？ ​

简单来说，就是初始化时，传的不是2 的倍数时，HashMap 会向上寻找离得最近的2 的倍数，所以传入17 ，但HashMap 的实际容量是3 2 。

我们来看看详情，在HashMap 的初始化中，有这样一段方法；

java
public HashMap(int initialCapacity, float loadFactor) {

...

 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}

阀值 threshold ，通过方法tableSizeFor进行计算，是根据初始化传的参数来计算的。

同时，这个方法也要要寻找比初始值大的，最小的那个2 进制数值。比如传了1 7 ，我应该找到的是32 。

static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

MAXIMUM_CAPACITY=1<<30 ，这个是临界范围，也就是最大的M ap 集合。

计算过程是向右移位1 、2 、4 、8 、1 6 ，和原来的数做**|**运算，这主要是为了把二进制的各个位置都填上1 ，当二进制的各个位置都是1 以后，就是一个标准的2 的倍数减1 了，最后把结果加1 再返回即可。

以1 7 为例，看一下初始化计算table 容量的过程：

配图

17.你还知道哪些哈希函数的构造方法呢？ ​

HashMap 里哈希构造函数的方法叫：

除留取余法：H （k ey)=key%p （p <=N ）, 关键字除以一个不大于哈希表长度的正整数p ，所得余数为地址，当然HashMap 里进行了优化改造，效率更高，散列也更均衡。

除此之外，还有这几种常见的哈希函数构造方法：

直接定址法

直接根据key来映射到对应的数组位置，例如1 232 放到下标1 232 的位置。

数字分析法

取key的某些数字（例如十位和百位）作为映射的位置

平方取中法

取key平方的中间几位作为映射的位置

折叠法

将key分割成位数相同的几段，然后把它们的叠加和作为映射的位置

配图

18.解决哈希冲突有哪些方法呢？ ​

我们到现在已经知道，HashMap 使用链表的原因为了处理哈希冲突，这种方法就是所谓的：

链地址法：在冲突的位置拉一个链表，把冲突的元素放进去。

除此之外，还有一些常见的解决冲突的办法：

开放定址法：开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。

找到空闲位置的方法也有很多种：

线行探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置平方探查法: 从冲突的位置x 开始，第一次增加1^2个位置，第二次增加2^2… ，直至找到空闲的位置… …

配图

再哈希法：换种哈希函数，重新计算冲突元素的地址。

建立公共溢出区：再建一个数组，把冲突的元素放进去。

19.为什么HashMap链表转红黑树的阈值为8呢？ ​

树化发生在table 数组的长度大于6 4 ，且链表的长度大于8 的时候。

为什么是8 呢？源码的注释也给出了答案。

配图

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选8 呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，节点个数为8 的情况，发生概率仅为0.00000006。

至于红黑树转回链表的阈值为什么是6 ，而不是8 ？是因为如果这个阈值也设置成8 ，假如发生碰撞，节点增减刚好在8 附近，会发生链表和红黑树的不断转换，导致资源浪费。

20.扩容在什么时候呢？为什么扩容因子是0.75？ ​

为了减少哈希冲突发生的概率，当当前HashMap 的元素个数达到一个临界值的时候，就会触发扩容，把所有元素rehash 之后再放在扩容后的容器中，这是一个相当耗时的操作。

而这个临界值threshold就是由加载因子和当前容器的容量大小来确定的，假如采用默认的构造方法：

临界值（threshold ）= 默认容量（DEFAULT_INITIAL_CAPACITY ） * 默认扩容因子（D EFAULT_LOAD_FACTOR ）

配图

那就是大于16x0.75=12时，就会触发扩容操作。

那么为什么选择了0 .75 作为HashMap 的默认加载因子呢？

简单来说，这是对空间成本和时间成本平衡的考虑。

在HashMap 中有这样一段注释：

配图

我们都知道，HashMap 的散列构造方式是Hash 取余，负载因子决定元素个数达到多少时候扩容。

假如我们设的比较大，元素比较多，空位比较少的时候才扩容，那么发生哈希冲突的概率就增加了，查找的时间成本就增加了。

我们设的比较小的话，元素比较少，空位比较多的时候就扩容了，发生哈希碰撞的概率就降低了，查找时间成本降低，但是就需要更多的空间去存储元素，空间成本就增加了。

21.那扩容机制了解吗？ ​

HashMap 是基于数组+ 链表和红黑树实现的，但用于存放k ey 值的桶数组的长度是固定的，由初始化参数确定。

那么，随着数据的插入数量增加以及负载因子的作用下，就需要扩容来存放更多的数据。而扩容中有一个非常重要的点，就是j dk1.8 中的优化操作，可以不需要再重新计算每一个元素的哈希值。

因为HashMap 的初始容量是2 的次幂，扩容之后的长度是原来的二倍，新的容量也是2 的次幂，所以，元素，要么在原位置，要么在原位置再移动2 的次幂。

看下这张图，n 为table 的长度，图a表示扩容前的k ey1 和k ey2 两种k ey 确定索引的位置，图b表示扩容后k ey1 和k ey2 两种k ey 确定索引位置。

配图

元素在重新计算hash 之后，因为n 变为2 倍，那么n -1 的mask 范围在高位多1 bit( 红色) ，因此新的index就会发生这样的变化：

配图

所以在扩容时，只需要看原来的hash 值新增的那一位是0 还是1 就行了，是0 的话索引没变，是1 的化变成原索引+ oldCap，看看如1 6 扩容为3 2 的示意图：

配图

扩容节点迁移主要逻辑：

配图

22.jdk1.8对HashMap主要做了哪些优化呢？为什么？ ​

jdk1.8 的HashMap 主要有五点优化：

  1. 数据结构：数组 + 链表改成了数组 + 链表或红黑树

原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由**O(n)**降

为O(logn)
  1. 链表插入方式：链表的插入方式从头插法改成了尾插法

简单说就是插入时，如果数组位置上已经有元素，1 .7 将新元素放到数组中，原始节点作为新节点的后继节点，1 .8 遍历链表，将元素放置到链表的最后。

原因：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。

  1. 扩容re hash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1 .8

采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。

**原因：**提高扩容的效率，更快地扩容。

  1. 扩容时机：在插入时，1 .7 先判断是否需要扩容，再插入，1 .8 先进行插入，插入完成再判断是

否需要扩容；

  1. 散列函数：1 .7 做了四次移位和四次异或，j dk1.8 只做一次。

原因：做 4 次的话，边际效用也不大，改为一次，提升效率。

23.你能自己设计实现一个HashMap吗？ ​

这道题快手常考。

不要慌，红黑树版咱们多半是写不出来，但是数组+ 链表版还是问题不大的，详细可见： 手写

HashMap ，快手面试官直呼内行！。

整体的设计：

散列函数：hashCode()+除留余数法

冲突解决：链地址法扩容：节点重新hash 获取位置

配图

完整代码：

配图

24.HashMap 是线程安全的吗？多线程下会有什么问题？ ​

HashMap 不是线程安全的，可能会发生这些问题：

多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK1.7 和 JDK

  1. 8 中都存在。

put 和 get 并发时，可能导致 get 为 null 。线程 1 执行 put 时，因为元素个数超出 threshold而导致 rehash ，线程 2 此时执行 get ，有可能导致这个问题。这个问题在 JDK1.7 和 JDK1.8中都存在。

25.有什么办法能解决HashMap线程不安全的问题呢？ ​

 Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以实现线程

安全的 Map 。

HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出

一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；

ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

26.能具体说一下ConcurrentHashmap的实现吗？ ​

ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁实现，在jdk1.8是基于CAS+synchronized

实现。

1.7分段锁

从结构上说，1 .7 版本的ConcurrentHashMap 采用分段锁机制，里面包含一个Segment 数组，Segment

继承于ReentrantLock，Segment则包含HashEntry的数组，HashEntry本身就是一个链表的结构，具

有保存k ey 、value 的能力能指向下一个节点的指针。

实际上就是相当于每个Segment 都是一个HashMap ，默认的Segment 长度是1 6 ，也就是支持1 6 个线程的并发写，Segment 之间相互不会受到影响。

配图

put 流程

整个流程和HashMap 非常类似，只不过是先定位到具体的Segment ，然后通过ReentrantLock 去操作而已，后面的流程，就和HashMap 基本上是一样的。

  1. 计算hash ，定位到segment ，segment 如果是空就先初始化

  2. 使用ReentrantLock 加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获

取锁成功

3.遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链

表，链表同样操作

get 流程

get 也很简单，k ey 通过hash 定位到segment ，再遍历链表定位到具体的元素上，需要注意的是value 是

volatile的，所以get是不需要加锁的。
1.8 CAS+synchronized

jdk1.8 实现线程安全不是在数据结构上下功夫，它的数据结构和HashMap 是一样的，数组+ 链表+ 红黑树。它实现线程安全的关键点在于p ut 流程。

put 流程

  1. 首先计算hash ，遍历node 数组，如果node 是空的话，就通过CAS+ 自旋的方式初始化
 tab = initTable();

node 数组初始化：

java
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        //如果正在初始化或者扩容
        if ((sc = sizeCtl) < 0)
            //等待
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //CAS操作
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}
  1. 如果当前数组位置是空则直接通过CAS 自旋写入数据
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
  1. 如果hash==MOVED ，说明需要扩容，执行扩容
else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
    Node<K,V>[] nextTab; int sc;
    if (tab != null && (f instanceof ForwardingNode) &&
        (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
        int rs = resizeStamp(tab.length);

while(nextTab==nextTable&&table==tab&&

               (sc = sizeCtl) < 0) {

if((sc>>>RESIZE_STAMP_SHIFT)!=rs||sc==rs+1||

                sc == rs + MAX_RESIZERS || transferIndex <= 0)
                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}
  1. 如果都不满足，就使用synchronized 写入数据，写入数据同样判断链表、红黑树，链表写入和

HashMap 的方式一样，keyhash 一样就覆盖，反之就尾插法，链表长度超过8 就转换成红黑树

 synchronized (f){

… …

 }

配图

get 查询

get 很简单，和HashMap 基本相同，通过k ey 计算位置，table 该位置k ey 相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取。

27.HashMap 内部节点是有序的吗？ ​

HashMap 是无序的，根据 hash 值随机插入。如果想使用有序的M ap ，可以使用LinkedHashMap 或者 TreeMap 。

28.讲讲 LinkedHashMap 怎么实现有序的？ ​

 LinkedHashMap维护了一个双向链表，有头尾节点，同时 LinkedHashMap 节点 Entry 内部除了继

承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。

配图

可以实现按插入的顺序或访问顺序排序。

配图

29.讲讲 TreeMap 怎么实现有序的？ ​

TreeMap 是按照 Key 的自然顺序或者 Comprator 的顺序进行排序，内部是通过红黑树来实现。所以要么 key 所属的类实现 Comparable 交叉，或者自定义一个实现了 Comparator 交叉的比较器，传给

TreeMap 用于 key 的比较。

配图

本文整理自三分恶《面渣逆袭》系列的公开内容，仅供个人学习使用
本站为个人秋招复习知识库 · 仅供个人学习使用

本站仅供个人学习使用，请勿外传

秋招知识库