一网打尽-HashMap面试题（hashmap数据结构面试）

全文4896字。读完五分钟，即可获得HashMap理解全部面经和原理。坚持就是胜利

1、实现原理

HashMap 是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的。

2、HashMap的工作原理

HashMap基于hashing原理，当我们往HashMap中 put 元素时，先根据key的hash 值得到这个Entry 元素在数组中的位置(即下标)，然后把这个Entry元素放到对应的位置中，如果这个Entry 元素所在的位子上已经存放有其他元素就在同一个位子上的Entry 元素以链表的形式存放，新加入的放在链头(JDK 1.8以前碰撞节点会在链表头部插入，而JDK 1.8开始碰撞节点会在链表尾部插入）。

对于扩容操作后的节点转移，JDK 1.8以前转移前后链表顺序会倒置，而JDK 1.8 中依然保持原序（这点很重要）。从HashMap中 get Entry元素时先计算 key的 hashcode，找到数组中对应位置的某一 Entry 元素，然后通过 key的equals 方法在对应位置的链表中找到需要的Entry 元素，所以HashMap的数据结构是数组和链表的结合，此外HashMap中key和 value都允许为 null, key为 null的键值对永远都放在以table[0] 为头结点的链表中。HashMap在每个链表节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么？

它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对

3、属性和构造函数

• 初始容量:表示哈希表在其容量自动增加之前可以达到多满的一种尺度
• 加载因子:当哈希表中的条目超过了容量和加载因子的乘积的时候，就会进行重哈希操作。

static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
       final K key;//键
       V value;//值
       // 指向下一个节点
       Node<K,V> next;
       Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        // 重写hashCode()方法
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重写 equals() 方法
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
}

3、扩容机制resize

当元素个数＞数组大小（默认16）负载因子（默认0.75f）时开始扩容，即默认情况下元素个数大于12个时，数组大小扩为216＝32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap 中元素的个数，那么预设元素的个数能够有效地提高 HashMap的性能。

注意：是使用一个新的数组代替已有的容量小的数组。

什么时候触发，扩容时需要再次计算hash么？JDK8之前之后有什么改变？

扩容时如何保证可操作，扩容时避免rehash的优化？

• 当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中
• 加载因子（默认0.75）：如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长
• 这样查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多）
• 在JDK1.8之前，需要rehash，1.8开始不需要rehash，因为经过rehash之后，元素的位置要么是在原位置，要么是在原位置+原数组长度的位置
• 1.7中是重新进行hash运算，而jdk1.8中是用了原位置+原数组长度这样一种很巧妙的方式，而这个结果与hash运算得到的结果是一致的，只是会更块。
• 至于为什么新位置要么是原位置，要么是原位置+原数组长度的位置是由于每次扩容相当于数组长度的高位多了一个1，新的hash运算取决于hashCode在这一位上的值是0还是1，如果是0则无需变化位置，如果是1则位置为原位置+原数组长度的位置

4、HashMap 并发问题

多线程put后可能导致get死循环

由于HashMap是线程不安全的，高并发情况下会出现死循环，即会出现环形链表，进而导致CPU被占满的情况。

具体分析：

单线程情况下，HashMap重复插入某个值的时候，会覆盖之前的值，这个没错。但在多线程访问的时候，由于其内部实现机制（在多线程环境且未作同步的情况下，对同一个HashMap 做put操作可能导致两个或以上线程同时做rehash 动作，就可能导致循环键表出现，一旦出现线程将无法终止，持续占用CPU，导致CPU使用率居高不下），就可能出现安全问题了。

办法：使用jstack工具dump出问题的那台服务器的栈信息，查看具体日志信息。

注意：不合理使用HashMap导致出现的是死循环而不是死锁。

多线程put的时候可能导致元素丢失

主要问题出在addEntry方法的new Entry（hash，key，value，e），如果两个线程都同时取得了e，则他们下一个元素都是e，然后赋值给table元素的时候有一个成功有一个丢失。

三种解决方案

·Hashtable替换HashMap

·
Collections.synchronizedMap将HashMap包装起来

·ConcurrentHashMap替换HashMap（推荐）

5、哈希

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单地说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。

常见的Hash函数有以下几个：

直接定址法：直接以关键字k或者k加上某个常数 (k+c)作为哈希地址。 
数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。 
除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。 
分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。 平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。 
伪随机数法：采用一个伪随机数当作哈希函数。

解决碰撞的方法：

1．开放定址法： 开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。 
2．链地址法： 将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。 
3．再哈希法： 当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。
4．建立公共溢出区 将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。

OK，接下来我们梳理下put方法的过程：

根据代码可以总结插入逻辑如下:

1. 先调用 hash() 方法计算哈希值
2. 然后调用 putVal() 方法中根据哈希值进行相关操作
3. 如果当前 哈希表内容为空，新建一个哈希表
4. 如果要插入的桶中没有元素，新建个节点并放进去
5. 否则从桶中第一个元素开始查找哈希值对应位置

1.如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找

2.如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用 putTreeVal() 进行插入

3.否则还是从传统的链表数组中查找、替换，结束查找

4.当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化

6.最后检查是否需要扩容

插入过程中涉及到几个其他关键的方法 ：

• hash():计算对应的位置
• resize():扩容
• putTreeVal():树形节点的插入
• treeifyBin():树形化容器

1、HashMap 中的哈希函数 hash() 和 计算桶中位置

HashMap 中通过将「hashCode 进行无符号右移 16 位」和「hashCode本身」按位异或 ，即 hash = 【hc ^ hc>>>16】，得到这个键的哈希值，然后再用 (length - 1) & hash 计算出桶的位置。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//高位运算
}
//put（）方法中：
tab[(length - 1) & hash]//取模

为何Hash方法中要移位操作？

由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。

int 只有 32 位，右位移16位，正好是32bit的一半，自己的高半区和低半区做异或（即上下两排数字相同则0，不同则1），就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性，这样可以避免只靠低位数据来计算哈希时导致的冲突，计算结果由高低位结合决定，可以避免哈希值分布不均匀。

为什么哈希表的容量一定要是 2的整数次幂?

1. 首先，当capacity 为 2的整数次幂的话,计算桶的位置 h&(length-1) 就等于 length 取模,而且效率更高；（补充：a%b取模的形式都被替换成了a&(b-1) ，当hashtable的长度是2的幂的情况下，这两者是等价的）
2. capacity 为 2 的整数次幂的话为偶数，这样 capacity-1 为奇数，奇数的最后一位是 1，这样便保证了 h&(capacity-1) 的最后一位可能为 0，也可能为 1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性；（ 可以参考拓展篇-位异或等运算，）
3. 假如 capacity 为奇数的话，很明显 capacity-1 为偶数，它的最后一位是 0，这样 h&(capacity-1) 的最后一位肯定为 0（因为同为或运算：任何数&0 都= 0）即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。

因此，哈希表容量取 2 的整数次幂，有以下 2 点好处：

• 使用减法替代取模，提升计算效率；
• 为了使不同 hash 值发生碰撞的概率更小，尽可能促使元素在哈希表中均匀地散列。

如果重写了equals方法，却没有重写hashcode方法会有什么问题？

这会导致两个相等的对象具有不相等的散列码。

我们来看get方法的过程：首先计算key的hashcode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。所以，hashcode与equals方法对于找到对应元素是两个关键方法。

public static void main(String[] args) {
          Key k1 = new Key(1);
          Key k2 = new Key(1);
          HashMap<Key,String> hm = new HashMap<Key,String>();
          hm.put(k1, "Key with id is 1");
          System.out.println(hm.get(k2));
}

重写了equals方法，却没有重写hashcode方法后，k1和k2所计算出的hash值相同，此时key相同，但是hm.get(k2)任然返回Null，原因是没有重写Key对象的equals方法。

而HashMap是用链地址法来处理冲突，也就是说，在100号位置上，有可能存在着多个用链表形式存储的对象。

它们通过hashCode方法返回的hash值都是100。这个时候，就需要调用Key对象的equals方法来判断两者是否相等了。

由于我们在Key对象里没有定义equals方法，系统就不得不调用Object类的equals方法。由于Object的固有方法是根据两个对象的内存地址来判断，所以k1和k2一定不会相等，这就是为什么hm.get(k2)得到null的原因。

多线程下HashMap可能发生死循环问题详解

死循环是因为并发 HashMap 扩容导致的

• 归根结底，原因就是JDK1.7 链表新节点采用的是头插法，这样在线程一扩容迁移元素时，会将元素顺序改变，导致两个线程中出现元素的相互指向而形成循环链表。1.8采用了尾插法，从根源上杜绝了这种情况的发生

1. 死循环是因为并发 HashMap 扩容导致的，并发扩容的第一步，线程 T1 和线程 T2 要对 HashMap 进行扩容操作，假设两个线程的指针， T1 和 T2 指向的是链表的头结点元素 A，而 T1 和 T2 的下一个节点，也就是 T1.next 和 T2.next 指向的是 B 节点。
2. 线程 T2 时间片用完进入休眠状态，而线程 T1 开始执行扩容操作，一直到线程 T1 扩容完成后，线程 T2 才被唤醒
3. 可知线程 T1 执行之后，因为是头插法链表反转，但线程 T2 对于发生的一切是不可知的，所以它的指向元素依然没变，如上图展示的那样，T2 指向的是 A 元素，T2.next 指向的节点是 B 元素。
4. 如下图所示，T1 执行完之后的顺序是 B 到 A，而 T2 的顺序是 A 到 B，这样 A 节点和 B 节点就形成死循环了，这就是 HashMap 死循环导致的原因。

读完，已经回答了全部的HashMap的面试题了。你是否还有不理解的？欢迎评论区讨论，都会一一回复。

关注转发私信获得JAVA面经大全。