关于HashMap的一些知识点

发布于:2023-01-09 ⋅ 阅读:(605) ⋅ 点赞:(0)

1.首先说说HashMap的数据结构

        1)1.7 数组 + 链表

        2)1.8 数组 + (链表 | 红黑树)

2.为什么要有红黑树?

 什么时候会变成红黑树:当链表长度超过树化阈值 8 时,先尝试扩容来减少链表长度,如果数组容量已经 >=64,才会进行树化

        1)hash 值如果足够随机,则在 hash 表内按泊松分布,在负载因子 0.75 的情况下,长度超过 8 的链表出现概率是 0.00000006,树化阈值选择 8 就是为了让树化几率足够小

        2)所以红黑树用来避免 DoS 攻击,防止链表超长时性能下降,树化应当是偶然情况,是保底策略

        3)hash 表的查找,更新的时间复杂度是 O(1),而红黑树的查找,更新的时间复杂度是 O(log2⁡n ),TreeNode 占用空间也比普通 Node 的大,如非必要,尽量还是使用链表

什么时候红黑树会变成链表:

        1)情况1:在扩容时如果拆分树时,树元素个数 <= 6 则会退化链表

        2)remove 树节点时,若 root、root.left、root.right、root.left.left 有一个为 null ,也会退化为链表

3.索引计算

首先,计算对象的 hashCode(),再进行调用 HashMap 的 hash() 方法进行二次哈希(二次 hash() 是为了综合高位数据,让哈希分布更为均匀),最后 & (capacity – 1) 得到索引

为什么数组容量是 2 的 n 次幂:

1)计算索引时效率更高:如果是 2 的 n 次幂可以使用位与运算代替取模

2)扩容时重新计算索引效率更高: hash & oldCap == 0 的元素留在原来位置 ,否则新位置 = 旧位置 + oldCap

注意:

        1)二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提,如果 hash 表的容量不是 2 的 n 次幂,则不必二次 hash

        2)容量是 2 的 n 次幂 这一设计计算索引效率更好,但 hash 的分散性就不好,需要二次 hash 来作为补偿,没有采用这一设计的典型例子是 Hashtable(它的扩容机制是2n+1)

4.put 与扩容

  1. HashMap 是懒惰创建数组的,首次使用才创建数组

  2. 计算索引(桶下标)

  3. 如果桶下标还没人占用,创建 Node 占位返回

  4. 如果桶下标已经有人占用

    1. 已经是 TreeNode 走红黑树的添加或更新逻辑

    2. 是普通 Node,走链表的添加或更新逻辑,如果链表长度超过树化阈值,走树化逻辑

  5. 返回前检查容量是否超过阈值,一旦超过进行扩容

1.7 与 1.8 的区别

  1. 链表插入节点时,1.7 是头插法,1.8 是尾插法

  2. 1.7 是大于等于阈值且没有空位时才扩容,而 1.8 是大于阈值就扩容

  3. 1.8 在扩容计算 Node 索引时,会优化

扩容(加载)因子为何默认是 0.75f

  1. 在空间占用与查询时间之间取得较好的权衡

  2. 大于这个值,空间节省了,但链表就会比较长影响性能

  3. 小于这个值,冲突减少了,但扩容就会更频繁,空间占用也更多

5.并发问题

扩容死链(1.7 会存在)

数据错乱(1.7,1.8 都会存在)

6.key 的设计

  1. HashMap 的 key 可以为 null,但 Map 的其他实现则不然

  2. 作为 key 的对象,必须实现 hashCode 和 equals,并且 key 的内容不能修改(不可变)

  3. key 的 hashCode 应该有良好的散列性

如果 key 可变,例如修改了 age 会导致再次查询时查询不到

​​​​​​

public class HashMapMutableKey {
    public static void main(String[] args) {
        HashMap<Student, Object> map = new HashMap<>();
        Student stu = new Student("张三", 18);
        map.put(stu, new Object());

        System.out.println(map.get(stu));

        stu.age = 19;
        System.out.println(map.get(stu));
    }

    static class Student {
        String name;
        int age;

        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getAge() {
            return age;
        }

        public void setAge(int age) {
            this.age = age;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return age == student.age && Objects.equals(name, student.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name, age);
        }
    }
}

控制台输出:

String 对象的 hashCode() 设计

  • 目标是达到较为均匀的散列效果,每个字符串的 hashCode 足够独特

  • 字符串中的每个字符都可以表现为一个数字,称为 $S_i$,其中 i 的范围是 0 ~ n - 1

  • 散列公式为: $S_0∗31^{(n-1)}+ S_1∗31^{(n-2)}+ … S_i ∗ 31^{(n-1-i)}+ …S_{(n-1)}∗31^0$

  • 31 代入公式有较好的散列特性,并且 31 * h 可以被优化为

    • 即 $32 ∗h -h $

    • 即 $2^5 ∗h -h$

    • 即 $h≪5 -h$

源码部分:

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

以下是关于hashmap图形化的扩容展示,很形象,需要的话可以去网盘中获取

网盘链接:​​​​​​百度网盘 请输入提取码百度网盘为您提供文件的网络备份、同步和分享服务。空间大、速度快、安全稳固,支持教育网加速,支持手机端。注册使用百度网盘即可享受免费存储空间https://pan.baidu.com/s/1qqEzw_6L2y_jJa_ZWA4iyA

提取码:yyds

找到jar包目录,cmd,然后输入:

java -jar --add-exports java.base/jdk.internal.misc=ALL-UNNAMED hash-demo.jar

访问localhost:8080会出现如下:

以上内容是我看黑马面试题中的笔记,分享给大家


网站公告

今日签到

点亮在社区的每一天
去签到