广告位联系
返回顶部
分享到

在Java中实现一个散列表的教程

java 来源:互联网 作者:秩名 发布时间:2022-04-21 17:07:24 人浏览
摘要

假设现在有一篇很长的文档,如果希望统计文档中每个单词在文档中出现了多少次,应该怎么做呢? 很简单! 我们可以建一个HashMap,以String类型为Key,Int类型为Value; 遍历文档中的每

假设现在有一篇很长的文档,如果希望统计文档中每个单词在文档中出现了多少次,应该怎么做呢?

很简单!

我们可以建一个HashMap,以String类型为Key,Int类型为Value;

  • 遍历文档中的每个单词 word ,找到键值对中key为 word 的项,并对相关的value进行自增操作。
  • 如果该key= word 的项在 HashMap中不存在,我们就插入一个(word,1)的项表示新增。
  • 这样每组键值对表示的就是某个单词对应的数量,等整个文档遍历完成,我们就可以得到每个单词的数量了。

简单实现下,代码示例如下:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

import java.util.HashMap;

import java.util.Map;

public class Test {

    public static void main(String[] args) {

        Map map = new HashMap<>();

        String doc = "yue ban fei yu";

        String[] words = doc.split(" ");

        for (String s : words) {

            if (!map.containsKey(s)) {

                map.put(s, 1);

            } else {

                map.put(s, map.get(s) + 1);

            }

        }

        System.out.println(map);

    }

}

那HashMap是怎么做到高效统计单词对应数量的?我们下面会逐步来研究一下!

首先我们先来看看如果只统计某一个单词的数量?

只需要开一个变量,同样遍历所有单词,遇到和目标单词一样的,才对这个变量进行自增操作;

  • 等遍历完成,我们就可以得到该单词的数量了。
  • 我们可以把所有可能出现的单词都列出来,每个单词,单独用一个变量去统计它出现的数量,遍历所有单词,判断当前单词应该被累计到哪个变量中。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

import java.util.HashMap;

import java.util.Map;

public class Main {

    public static void main(String[] args) {

        int[] cnt = new int[20000];

        String doc = "a b c d";

        String[] words = doc.split(" ");

        int a = 0;

        int b = 0;

        int c = 0;

        int d = 0;

        for (String s : words) {

           if (s == "a") a++;

           if (s == "b") b++;

           if (s == "c") c++;

           if (s == "d") d++;  

        }

    }

}

注意:这样的代码显然有两个很大的问题:

  • 对单词和计数器的映射关系是通过一堆if-else写死的,维护性很差;
  • 必须已知所有可能出现的单词,如果遇到一个新的单词,就没有办法处理它了。

优化1

我们可以开一个数组去维护计数器。

具体做法就是,给每个单词编个号,直接用编号对应下标的数组元素作为它的计数器就好啦。

我们可以建立两个数组:

  • 第一个数组用于存放所有单词,数组下标就是单词编号了,我们称之为字典数组;
  • 第二个数组用于存放每个单词对应的计数器,我们称之为计数数组。

每遇到一个新的单词,都遍历一遍字典数组,如果没有出现过,我们就将当前单词插入到字典数组结尾。

这样做,整体的时间复杂度较高,还是不行。

优化2

优化方式:

  • 一种是我们维护一个有序的数据结构,让比较和插入的过程更加高效,而不是需要遍历每一个元素判断逐一判断。
  • 另一种思路就是我们是否能寻找到一种直接基于字符串快速计算出编号的方式,并将这个编号映射到一个可以在O(1)时间内基于下标访问的数组中。

以单词为例,英文单词的每个字母只可能是 a-z。

我们用0表示a、1表示b,以此类推,用25表示z,然后将一个单词看成一个26进制的数字即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

import java.util.HashMap;

import java.util.Map;

public class Main {

    public static void main(String[] args) {

        int[] cnt = new int[20000];

        String doc = "a b c d";

        String[] words = doc.split(" ");

        for (String s : words) {

            int tmp = 0;

            for (char c: s.toCharArray()) {

                tmp *= 26;

                tmp += (c - 'a');

            }

            cnt[tmp]++;

        }

        String target = "a";

        int hash = 0;

        for (char c: target.toCharArray()) {

            hash *= 26;

            hash += c - 'a';

        }

        System.out.println(cnt[hash]);

    }

}

这样我们统计N个单词出现数量的时候,整体只需要O(N)的复杂度,相比于原来的需要遍历字典的做法就明显高效的多。

这其实就是散列的思想了。

优化3

使用散列!

散列函数的本质,就是将一个更大且可能不连续空间(比如所有的单词),映射到一个空间有限的数组里,从而借用数组基于下标O(1)快速随机访问数组元素的能力。

但设计一个合理的散列函数是一个非常难的事情。

  • 比如对26进制的哈希值再进行一次对大质数取mod的运算,只有这样才能用比较有限的计数数组空间去表示整个哈希表。

取了mod之后,我们很快就会发现,现在可能出现一种情况,把两个不同的单词用26进制表示并取模之后,得到的值很可能是一样的。

这个问题被称之为哈希碰撞。

如何实现

最后我们考虑一下散列函数到底需要怎么设计。

以JDK(JDK14)的HashMap为例:

  • 主要实现在 java.util 下的 HashMap 中,这是一个最简单的不考虑并发的、基于散列的Map实现。

找到其中用于计算哈希值的hash方法:

1

2

3

4

static final int hash(Object key) {

    int h;

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

可以发现就是对key.hashCode()进行了一次特别的位运算。

hashcode方法

在Java中每个对象生成时都会产生一个对应的hashcode。

  • 当然数据类型不同,hashcode的计算方式是不一样的,但一定会保证的是两个一样的对象,对应的hashcode也是一样的;

所以在比较两个对象是否相等时,我们可以先比较hashcode是否一致,如果不一致,就不需要继续调用equals,大大降低了比较对象相等的代价。

我们就一起来看看JDK中对String类型的hashcode是怎么计算的,我们进入 java.lang 包查看String类型的实现:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

public int hashCode() {

    // The hash or hashIsZero fields are subject to a benign data race,

    // making it crucial to ensure that any observable result of the

    // calculation in this method stays correct under any possible read of

    // these fields. Necessary restrictions to allow this to be correct

    // without explicit memory fences or similar concurrency primitives is

    // that we can ever only write to one of these two fields for a given

    // String instance, and that the computation is idempotent and derived

    // from immutable state

    int h = hash;

    if (h == 0 && !hashIsZero) {

        h = isLatin1() ? StringLatin1.hashCode(value)

                       : StringUTF16.hashCode(value);

        if (h == 0) {

            hashIsZero = true;

        } else {

            hash = h;

        }

    }

    return h;

}

Latin和UTF16是两种字符串的编码格式,实现思路其实差不多,我们来看看StringUTF16中hashcode的实现:

1

2

3

4

5

6

7

8

public static int hashCode(byte[] value) {

    int h = 0;

    int length = value.length >> 1;

    for (int i = 0; i < length; i++) {

        h = 31 * h + getChar(value, i);

    }

    return h;

}

其实就是对字符串逐位按照下面的方式进行计算,和展开成26进制的想法本质上是相似的。

1

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

为什么选择了31?

首先在各种哈希计算中,我们比较倾向使用奇素数进行乘法运算,而不是用偶数。

因为用偶数,尤其是2的幂次,进行乘法,相当于直接对原来的数据进行移位运算;这样溢出的时候,部分位的信息就完全丢失了,可能增加哈希冲突的概率。

为什么选择了31这个奇怪的数,这是因为计算机在进行移位运算要比普通乘法运算快得多,而31*i可以直接转化为(i << 5)- i ,这是一个性能比较好的乘法计算方式,现代的编译器都可以推理并自动完成相关的优化。

具体可以参考《Effective Java》中的相关章节。

h>>>16

我们现在来看 ^ h >>> 16 又是一个什么样的作用呢?

它的意思是就是将h右移16位并进行异或操作,为什么要这么做呢?

因为那个hash值计算出来这么大,那怎么把它连续地映射到一个小一点的连续数组空间呢?

所以需要取模,我们需要将hash值对数组的大小进行一次取模。

我们需要对2的幂次大小的数组进行一次取模计算。

但对二的幂次取模相当于直接截取数字比较低的若干位,这在数组元素较少的时候,相当于只使用了数字比较低位的信息,而放弃了高位的信息,可能会增加冲突的概率。

所以,JDK的代码引入了^ h >>> 16 这样的位运算,其实就是把高16位的信息叠加到了低16位,这样我们在取模的时候就可以用到高位的信息了。

如何处理哈希冲突呢?

JDK中采用的是开链法。

哈希表内置数组中的每个槽位,存储的是一个链表,链表节点的值存放的就是需要存储的键值对。

如果碰到哈希冲突,也就是两个不同的key映射到了数组中的同一个槽位,我们就将该元素直接放到槽位对应链表的尾部。

总结

手写数据结构统计单词的数量正确的思路就是:

根据全文长度大概预估一下会有多少个单词,开一个数倍于它的数组,再设计一个合理的hash函数,把每个单词映射到数组的某个下标,用这个数组计数统计就好啦。

当然在实际工程中,我们不会为每个场景都单独写一个这样的散列表实现,也不用自己去处理复杂的扩容场景。


版权声明 : 本文内容来源于互联网或用户自行发布贡献,该文观点仅代表原作者本人。本站仅提供信息存储空间服务和不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权, 违法违规的内容, 请发送邮件至2530232025#qq.cn(#换@)举报,一经查实,本站将立刻删除。
原文链接 : https://juejin.cn/post/7084560466436948005
相关文章
  • SpringBoot自定义错误处理逻辑介绍

    SpringBoot自定义错误处理逻辑介绍
    1. 自定义错误页面 将自定义错误页面放在 templates 的 error 文件夹下,SpringBoot 精确匹配错误信息,使用 4xx.html 或者 5xx.html 页面可以打印错误
  • Java实现手写一个线程池的代码

    Java实现手写一个线程池的代码
    线程池技术想必大家都不陌生把,相信在平时的工作中没有少用,而且这也是面试频率非常高的一个知识点,那么大家知道它的实现原理和
  • Java实现断点续传功能的代码

    Java实现断点续传功能的代码
    题目实现:网络资源的断点续传功能。 二、解题思路 获取要下载的资源网址 显示网络资源的大小 上次读取到的字节位置以及未读取的字节
  • 你可知HashMap为什么是线程不安全的
    HashMap 的线程不安全 HashMap 的线程不安全主要体现在下面两个方面 在 jdk 1.7 中,当并发执行扩容操作时会造成环形链和数据丢失的情况 在
  • ArrayList的动态扩容机制的介绍

    ArrayList的动态扩容机制的介绍
    对于 ArrayList 的动态扩容机制想必大家都听说过,之前的文章中也谈到过,不过由于时间久远,早已忘却。 所以利用这篇文章做做笔记,加
  • JVM基础之字节码的增强技术介绍

    JVM基础之字节码的增强技术介绍
    字节码增强技术 在上文中,着重介绍了字节码的结构,这为我们了解字节码增强技术的实现打下了基础。字节码增强技术就是一类对现有字
  • Java中的字节码增强技术

    Java中的字节码增强技术
    1.字节码增强技术 字节码增强技术就是一类对现有字节码进行修改或者动态生成全新字节码文件的技术。 参考地址 2.常见技术 技术分类 类
  • Redis BloomFilter布隆过滤器原理与实现

    Redis BloomFilter布隆过滤器原理与实现
    Bloom Filter 概念 布隆过滤器(英语:Bloom Filter)是1970年由一个叫布隆的小伙子提出的。它实际上是一个很长的二进制向量和一系列随机映射
  • Java C++算法题解leetcode801使序列递增的最小交换次

    Java C++算法题解leetcode801使序列递增的最小交换次
    题目要求 思路:状态机DP 实现一:状态机 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int minSwap(int[] nums1, int[] nums2) { int n
  • Mybatis结果集映射与生命周期介绍

    Mybatis结果集映射与生命周期介绍
    一、ResultMap结果集映射 1、设计思想 对简单的语句做到零配置,对于复杂一点的语句,只需要描述语句之间的关系就行了 2、resultMap的应用场
  • 本站所有内容来源于互联网或用户自行发布,本站仅提供信息存储空间服务,不拥有版权,不承担法律责任。如有侵犯您的权益,请您联系站长处理!
  • Copyright © 2017-2022 F11.CN All Rights Reserved. F11站长开发者网 版权所有 | 苏ICP备2022031554号-1 | 51LA统计