【Java自顶向下】面试官:HashMap源码看过吗?我:看过!面试官:好极了,那么来扒一扒吧!

时间:2021-2-27 作者:admin

HashMap

关于hash表的基础内容,请看文章

【数据结构-查找】3.散列表详解
【Java自顶向下】HashMap面试题(2021最新版)

顶层应用

public class HashMapTest {
    public static void main(String[] args) {
        HashMap<String, String> stringStringHashMap = new HashMap<>();
        // 1.put存储键值对
        stringStringHashMap.put("ffideal","宇定");
        stringStringHashMap.put("床前明月光","疑是地上霜");
        // 2.get利用key获取value
        String name = stringStringHashMap.get("ffideal");
        System.out.println(name);
        // 3.containsKey是否存在某个键值
        if (stringStringHashMap.containsKey("ffideal")) {
            System.out.println("ffideal存在");
        } else {
            System.out.println("ffideal不存在");
        }
        // 4.replace修改key-value
        stringStringHashMap.replace("ffideal","宇定2");
        String name3 = stringStringHashMap.get("ffideal");
        System.out.println(name3);
        // 5.遍历HashMap中的键值对
        Set<String> strings = stringStringHashMap.keySet();
        for (String s: strings) {
            System.out.println("遍历数据:" + s);
        }
        // 6.clear清空HashMap中的元素
        stringStringHashMap.clear();
        Set<String> strings2 = stringStringHashMap.keySet();
        for (String s: strings2) {
            System.out.println("清空后的数据" + s);
        }
    }
}

底层原理

put => key => HashCode => 位置index

get => key => HashCode => 位置index

问:HashMap数组大小初始值是多少?最大是多少?如果为给定初始值,初始大小是多少?

答:16(

2

4

2^4

24);

2

30

2^{30}

230;大于等于参数的最小2的幂次方

private static final int tableSizeFor(int c) {
    	// 传入32或20
        int n = c - 1;
    	// n=31或19
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
    	// 此时n=31或31,最后经过两次判断后返回值为32
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

问:HashMap 在 Java 7 与Java 8 中底层的不同?

答:Java 7 中的HashMap的底层是一个数组+链表的设计,每个hash值的第一个值放在数组里,之后经过hash运算得到相同的hash值锁定数组下标,数组中的每一个元素都是一个单向链表(碰撞,列表)。

  1. capacity:当前数组容量,始终保持

    2

    n

    2^n

    2n,可以扩容,扩容后数组大小为当前的 2 倍。

  2. loadFactor:负载因子,默认为 0.75。
  3. threshold:扩容的阈值,等于 capacity * loadFactor。

【Java自顶向下】面试官:HashMap源码看过吗?我:看过!面试官:好极了,那么来扒一扒吧!

HashMap的数据插入原理

【Java自顶向下】面试官:HashMap源码看过吗?我:看过!面试官:好极了,那么来扒一扒吧!

存储结构的变化

Java 8 中的HashMap的底层是数组+链表+红黑树的方式实现。

为什么要使用红黑树而不使用AVL树

红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树

AVL树用于自平衡的计算牺牲了插入删除性能,但是因为最多只有一层的高度差,查询效率会高一些。

改进的是在数据量较大的情况下(Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树)单向链表的时间复杂是O(N),采用红黑树将时间复杂度降到O(logN)。

static final int TREEIFY_THRESHOLD = 8;

那么, 如果我们在删除容器中的元素的时候,删到多少才使得红黑树的存储结构转为链表呢?答案是6。

static final int UNTREEIFY_THRESHOLD = 6;

也就是说,在JDK8之后,创建HashMap对象=>添加数组中同一个位置元素超过8个=>该位置链表转为红黑树=>删除数组中同一个位置元素少于6个=>该位置红黑树转为列表。

最小树形化的策略

最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树), 否则,若桶内元素太多时,则直接扩容,而不是树形化。为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD。

也就是说,当数组中某个桶中的元素大于8,数组容量小于64时,使用容量进行两倍扩容(其实就是用扩容代替链表转红黑树操作)。当数组中某个桶中的元素大于8且数组容量大于64时,链表转红黑树操作。

hashMap并不是在链表元素个数大于8就一定会转换为红黑树,而是先考虑扩容,扩容达到默认限制后才转换

hashMap的红黑树不一定小于等于6的时候就会转换为链表,而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD(6) 进行转换

【Java自顶向下】面试官:HashMap源码看过吗?我:看过!面试官:好极了,那么来扒一扒吧!

HashMap怎么解决碰撞问题的?

Java中HashMap是利用“拉链法”处理HashCode的碰撞问题。

在调用HashMap的put方法或get方法时,都会首先调用hashcode方法,去查找相关的key,当有冲突时,再调用equals方法。

hashMap基于hasing原理,我们通过put和get方法存取对象。当我们将键值对传递给put方法时,他调用键对象的hashCode()方法来计算hashCode,然后找到bucket(哈希桶)位置来存储对象。

当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。

HashMap使用链表来解决碰撞问题,当碰撞发生了,对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时,他们会存储在同一个bucket位置的链表中。

键对象的equals()来找到键值对。

HashMap的一些特点

HashMap的5个特点
HashMap键不可重复,值可重复
底层hash表
具有很快的访问速度,遍历顺序不确定
线程不安全,若需要线程安全则需要使用Collections中的synchronizedMap方法来保障
允许key值为null,value值也为null

一些误区

问1:是否可以两个key值为null?

答1:不可以,后者会把前者覆盖

问2:HashMap插入时,使用头插法还是尾插法?

答2:在插入时采用尾插法(1.7是头插法),在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。

头插法和尾插法
【Java自顶向下】面试官:HashMap源码看过吗?我:看过!面试官:好极了,那么来扒一扒吧!

头插法带来的环状
【Java自顶向下】面试官:HashMap源码看过吗?我:看过!面试官:好极了,那么来扒一扒吧!

一些不足和解决方式

HashMap不是线程安全的.

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

HashTable是直接在操作方法上加synchronized关键字,锁住整个数组,粒度比较大。因为synchronized关键字每次执行都会调用操作系统的锁来保证线程安全,也就是每次执行代码块,都要涉及 “用户态” 到 “内核态” 的转变,十分消耗资源。

Collections.synchronizedMap是使用 Collections集合工具的内部类,通过传入Map封装出一个SynchronizedMap对象,内部定义了一个对象锁,方法内通过对象锁实现。

ConcurrentHashMap使用分段锁,降低了锁粒度,让并发度大大提高我们一般都会使用HashTable或者ConcurrentHashMap,但是因为前者的并发度的原因基本上没啥使用场景了,所以存在线程不安全的场景我们都使用的是ConcurrentHashMap。

HashTable我看过他的源码,很简单粗暴,直接在方法上锁,并发度很低,最多同时允许一个线程访问,ConcurrentHashMap就好很多了,1.7和1.8有较大的不同,不过并发度都比前者好太多了

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。