Home Tags Posts tagged with "HashMap"

HashMap

0 39

本文整理来自于 《极客时间—数据结构与算法之美》王争

一、带着问题去学习

Word 这种文本编辑器你平时应该经常用吧,那你有没有留意过它的拼写检查功能呢?一旦我们在 Word 里输入一个错误的英文单词,它就会用标红的方式提示“拼写错误”。Word 的这个单词拼写检查功能,虽然很小但却非常实用。你有没有想过,这个功能是如何实现的呢?

二、散列思想(散列表的理论基础)

散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash 表”,你一定也经常听过它

散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

我用一个例子来解释一下。假如我们有 89 名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这 89 名选手的编号依次是 1 到 89。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息。

你会怎么做呢?

我们可以把这 89 名选手的信息放在数组里。编号为 1 的选手,我们放到数组中下标为 1 的位置;编号为 2 的选手,我们放到数组中下标为 2 的位置。以此类推,编号为 k 的选手放到数组中下标为 k 的位置。因为参赛编号跟数组下标一一对应,当我们需要查询参赛编号为 x 的选手的时候,我们只需要将下标为 x 的数组元素取出来就可以了,时间复杂度就是 O(1)。这样按照编号查找选手信息,效率是不是很高?实际上,这个例子已经用到了散列的思想。在这个例子里,参赛编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的时候,时间复杂度是 O(1) 这一特性,就可以实现快速查找编号对应的选手信息。

你可能要说了,这个例子中蕴含的散列思想还不够明显,那我来改造一下这个例子。

假设校长说,参赛编号不能设置得这么简单,要加上年级、班级这些更详细的信息,所以我们把编号的规则稍微修改了一下,用 6 位数字来表示。比如 051167,其中,前两位 05 表示年级,中间两位 11 表示班级,最后两位还是原来的编号 1 到 89。这个时候我们该如何存储选手信息,才能够支持通过编号来快速查找选手信息呢?

思路还是跟前面类似。尽管我们不能直接把编号作为数组下标,但我们可以截取参赛编号的后两位作为数组下标,来存取选手信息数据。当通过参赛编号查询选手信息的时候,我们用同样的方法,取参赛编号的后两位,作为数组下标,来读取数组中的数据。这就是典型的散列思想

其中,参赛选手的编号我们叫做键(key)或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数(或“Hash 函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash 值”“哈希值”)。

通过这个例子,我们可以总结出这样的规律:散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。

三、散列函数

散列函数,顾名思义,它是一个函数。

我们可以把它定义成 hash(key),其中 key 表示元素的键值,hash(key) 的值表示经过散列函数计算得到的散列值。那第一个例子中,编号就是数组下标,所以 hash(key) 就等于 key。

改造后的例子,写成散列函数稍微有点复杂。我用伪代码将它写成函数就是下面这样:

 

int hash(String key) {
// 获取后两位字符
string lastTwoChars = key.substr(length-2, length);
// 将后两位字符转换为整数
int hashValue = convert lastTwoChas to int-type;
return hashValue;
}

刚刚举的学校运动会的例子,散列函数比较简单,也比较容易想到。但是,如果参赛选手的编号是随机生成的 6 位数字,又或者用的是 a 到 z 之间的字符串,该如何构造散列函数呢?

如何设计散列函数?(三点基本要求)

我总结了三点散列函数设计的基本要求:

  • 散列函数计算得到的散列值是一个非负整数;
  • 如果 key1 = key2,那 hash(key1) == hash(key2);
  • 如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)。(很难做到,几乎不可能,所以产生了散列冲突问题)

我来解释一下这三点。

其中,第一点理解起来应该没有任何问题。因为数组下标是从 0 开始的,所以散列函数生成的散列值也要是非负整数。

第二点也很好理解。相同的 key,经过散列函数得到的散列值也应该是相同的。

第三点理解起来可能会有问题,我着重说一下。这个要求看起来合情合理,但是在真实的情况下,要想找到一个不同的 key 对应的散列值都不一样的散列函数,几乎是不可能的。

即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突。

而且,因为数组的存储空间有限,也会加大散列冲突的概率。所以我们几乎无法找到一个完美的无冲突的散列函数,即便能找到,付出的时间成本、计算成本也是很大的,所以针对散列冲突问题,我们需要通过其他途径来解决。

四、散列冲突(再好的散列函数也无法避免散列冲突,因此采用开放寻址发和链表法)

再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢?

我们常用的散列冲突解决方法有两类,开放寻址法(open addressing)链表法(chaining)。

1. 开放寻址法(线性探测,二次探测,双重探测)

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。

那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线性探测(Linear Probing)。当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。我说的可能比较抽象,我举一个例子具体给你说明一下。这里面黄色的色块表示空闲位置,橙色的色块表示已经存储了数据。

从图中可以看出,散列表的大小为 10,在元素 x 插入散列表之前,已经 6 个元素插入到散列表中。x 经过 Hash 算法之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。

于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是我们再从表头开始找,直到找到空闲位置 2,于是将其插入到这个位置。

在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。

散列表跟数组一样,不仅支持插入、查找操作,还支持删除操作。

对于使用线性探测法解决冲突的散列表,删除操作稍微有些特别。

我们不能单纯地把要删除的元素设置为空。这是为什么呢?还记得我们刚讲的查找操作吗?在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。这个问题如何解决呢?我们可以将删除的元素,特殊标记为 deleted。当线性探测查找的时候,遇到标记为 deleted 的空间,并不是停下来,而是继续往下探测。

你可能已经发现了,线性探测法其实存在很大问题。

当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,我们可能需要探测整个散列表,所以最坏情况下的时间复杂度为 O(n)。

同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找或者删除的数据。

对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)双重散列(Double hashing)。

所谓二次探测,跟线性探测很像,线性探测每次探测的步长是 1,那它探测的下标序列就是 hash(key)+0,hash(key)+1,hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”,也就是说,它探测的下标序列就是 hash(key)+0,hash(key)+12,hash(key)+22……

所谓双重散列,意思就是不仅要使用一个散列函数。我们使用一组散列函数 hash1(key),hash2(key),hash3(key)……我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。

 

装载因子

不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。

为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。

我们用装载因子(load factor)来表示空位的多少。装载因子的计算公式是:散列表的装载因子=填入表中的元素个数/散列表的长度装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

 

2. 链表法

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

插入操作

当插入的时候,我们只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是 O(1)。

查找和删除操作

当查找、删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或者删除。

那查找或删除操作的时间复杂度是多少呢?实际上,这两个操作的时间复杂度跟链表的长度 k 成正比,也就是 O(k)。对于散列比较均匀的散列函数来说,理论上讲,k=n/m,其中 n 表示散列中数据的个数,m 表示散列表中“槽”的个数。

 

解答开篇

有了前面这些基本知识储备,我们来看一下开篇的思考题:

Word 文档中单词拼写检查功能是如何实现的?

常用的英文单词有 20 万个左右,假设单词的平均长度是 10 个字母,平均一个单词占用 10 个字节的内存空间,那 20 万英文单词大约占 2MB 的存储空间,就算放大 10 倍也就是 20MB。

对于现在的计算机来说,这个大小完全可以放在内存里面。所以我们可以用散列表来存储整个英文单词词典。当用户输入某个英文单词时,我们拿用户输入的单词去散列表中查找。

如果查到,则说明拼写正确;如果没有查到,则说明拼写可能有误,给予提示。借助散列表这种数据结构,我们就可以轻松实现快速判断是否存在拼写错误。

内容小结

今天我讲了一些比较基础、比较偏理论的散列表知识,包括散列表的由来、散列函数、散列冲突的解决方法。散列表来源于数组,它借助散列函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性。散列表两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法,开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率,也就决定散列表的性能。针对散列函数和散列冲突,今天我只讲了一些基础的概念、方法,下一节我会更贴近实战、更加深入探讨这两个问题。

课后思考

  1. 假设我们有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?
  2. 有两个字符串数组,每个数组大约有 10 万条字符串,如何快速找出两个数组中相同的字符串?

回答:

1. 假设我们有 10 万条 URL 访问日志,如何按照访问次数给 URL 排序?

遍历 10 万条数据,以 URL 为 key,访问次数为 value,存入散列表,同时记录下访问次数的最大值 K,时间复杂度 O(N)。

如果 K 不是很大,可以使用桶排序,时间复杂度 O(N)。如果 K 非常大(比如大于 10 万),就使用快速排序,复杂度 O(NlogN)。

2. 有两个字符串数组,每个数组大约有 10 万条字符串,如何快速找出两个数组中相同的字符串?

以第一个字符串数组构建散列表,key 为字符串,value 为出现次数。再遍历第二个字符串数组,以字符串为 key 在散列表中查找,如果 value 大于零,说明存在相同字符串。时间复杂度 O(N)。

接着上一篇博客,上一篇博客说明了HashMap的初始容量都是2的n次幂的形式存在的,而扩容也是2倍的原来的容量进行扩容,也就是扩容后的容量也是2的n次幂的形式存在的,下面就来说明一下为什么是2的n次幂的形式!

先来看一下源码,也就是向HashMap中添加元素,或者扩容时是怎么存放元素的。

 

第一个截图是向HashMap中添加元素putVal()方法的部分源码,可以看出,向集合中添加元素时,会使用(n – 1) & hash的计算方法来得出该元素在集合中的位置;而第二个截图是HashMap扩容时调用resize()方法中的部分源码,可以看出会新建一个tab,然后遍历旧的tab,将旧的元素进过e.hash & (newCap – 1)的计算添加进新的tab中,也就是(n – 1) & hash的计算方法,其中n是集合的容量,hash是添加的元素进过hash函数计算出来的hash值。

HashMap的容量为什么是2的n次幂,和这个(n – 1) & hash的计算方法有着千丝万缕的关系,符号&是按位与的计算,这是位运算,计算机能直接运算,特别高效,按位与&的计算方法是,只有当对应位置的数据都为1时,运算结果也为1,当HashMap的容量是2的n次幂时,(n-1)的2进制也就是1111111***111这样形式的,这样与添加元素的hash值进行位运算时,能够充分的散列,使得添加的元素均匀分布在HashMap的每个位置上,减少hash碰撞,面举例进行说明。

当HashMap的容量是16时,它的二进制是10000,(n-1)的二进制是01111,与hash值得计算结果如下:

上面四种情况我们可以看出,不同的hash值,和(n-1)进行位运算后,能够得出不同的值,使得添加的元素能够均匀分布在集合中不同的位置上,避免hash碰撞。

下面就来看一下HashMap的容量不是2的n次幂的情况,当容量为10时,二进制为01010,(n-1)的二进制是01001,向里面添加同样的元素,结果为:

可以看出,有三个不同的元素进过&运算得出了同样的结果,严重的hash碰撞了。

终上所述,HashMap计算添加元素的位置时,使用的位运算,这是特别高效的运算;另外,HashMap的初始容量是2的n次幂,扩容也是2倍的形式进行扩容,是因为容量是2的n次幂,可以使得添加的元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!
————————————————
版权声明:本文为CSDN博主「猿人小郑」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/apeopl/article/details/88935422

0 47

HashMap作为集合框架中的重要组成部分,使用的地方有很多,例如最近所使用到的Mybatis通过Map传参等,HashMap的思想是键值对映射,例如进行多条件判断,一样可以通过HashMap来实现

在讨论其优化之前,我们先提一句HashMap的使用(题外话,能跟潇同学联系上真的蛮开心的)

package Test;

import java.util.HashMap;
public class HashMap2 {

    /**
     * 使用键值对的思想可以干很多事情
     * Map<key,value>键和value可以定义为任意的数据类型
     * 通常用于多种相同性质的属性(或事件)执行操作,都是通过key去得到value
     * 开始实战:
     *      模拟case取整数值执行不同的流程
     *
     */
    public static void main(String[] args) {
        Person p1 = new Person();
        p1.setName("白衣");
        p1.setType("老师");
        Person p2 = new Person();
        p2.setName("杨深建");
        p2.setType("学生");
        HashMap map = doMethod(p1, p2);
        //在此处控制传参即可执行不同的流程;
        Decide(map,1);
    }
    static HashMap doMethod(Person p1,Person p2){
        //制作HashMap
        HashMap<Integer,Person> hashMap = new HashMap<Integer, Person>();
        hashMap.put(1,p1);
        hashMap.put(2,p2);
        return hashMap;
    }
    static void Decide(HashMap hashMap,Integer integer){
        //显示数据,判断程序是否成功
        System.out.println(hashMap.get(integer).toString());
    }
}
//实体类
class Person{
    //定义字段;
    private String name;
    private String type;

    public String getName() {
        return name;
    }

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

    public String getType() {
        return type;
    }

    public void setType(String type) {
        this.type = type;
    }

    @Override
    public String toString() {
        return  "Person{" +
                "name='" + name + '\'' +
                ", type='" + type + '\'' +
                '}';
    }
}

这只是我的一次小小尝试,仅为了说明HashMap的思想,也许实际开发中我们不会这么去用,而是创造接口实现,本质也是抽象思想
思想最重要!!!

下面开始分析其遍历模式及优化:


转载自https://mp.weixin.qq.com/s?__biz=MzU1NTkwODE4Mw==&mid=2247485208&idx=1&sn=62be917b1431243b898354d17112b06f&chksm=fbcc6a20ccbbe3365f985fc8e9e19ca5e420d8907dab59358181eab8612b9835c56fcdcca1c5&scene=178&cur_album_id=1337160373983690752#rd

随着 JDK 1.8 Streams API 的发布,使得 HashMap 拥有了更多的遍历的方式,但应该选择那种遍历方式?反而成了一个问题。

本文先从 HashMap 的遍历方法讲起,然后再从性能、原理以及安全性等方面,来分析 HashMap 各种遍历方式的优势与不足,本文主要内容如下图所示:

HashMap遍历四大类:

  • 1.迭代器(Iterator)方式遍历
  • 2.For Each方式遍历;
  • 3.Lambda表达式遍历(JDK1.8+);
  • 4.Streams API遍历(JDK1.8+);

每种类型下又有不同的实现方式,因此具体的遍历方式又可以分为以下7种:

  • 使用迭代器(Iterator)EntrySet 的方式进行遍历;
  • 使用迭代器(Iterator)KeySet 的方式进行遍历;
  • 使用 For Each EntrySet 的方式进行遍历;
  • 使用 For Each KeySet 的方式进行遍历;
  • 使用 Lambda 表达式的方式进行遍历;
  • 使用 Streams API 单线程的方式进行遍历;
  • 使用 Streams API 多线程的方式进行遍历。

1.迭代器EntrySet

public class IteratorEntryset {
    public static void main(String[] args) {

        //创建HashMap并赋值
        Map<Integer,String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");

        //遍历
        Iterator<Map.Entry<Integer,String>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<Integer,String> entry = iterator.next();
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }


    }
}

2.迭代器KeySet
public class IteratorKeySet {

    public static void main(String[] args) {

        //创建并赋值HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // IteratorKeySet遍历 得到的是Map中的键Key
        Iterator<Integer> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            //获取当前的Key
            Integer key = iterator.next();
            //打印Key
            System.out.println(key);
            //通过Key打印value;
            System.out.println(map.get(key));
        }
    }
}

3.Foreach EntrySet
public class ForEachKeySet {

    /**
     * 使用Foreach遍历,通过Entryset()方法
     * Foreach适用于只在集合或数组中进行遍历,for则在较复杂的循环中效率更高
     * Foreach不能对集合或者数组中的元素进行添加和删除操作,因此需要修改元素(添加,删除)则需要使用for循环
     * @param args
     */
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        //使用Foreach遍历,通过EntrySet()方法
        for (Map.Entry<Integer,String> entry : map.entrySet()) {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
    }
}
4.Foreach KeySet
public class ForEachEntrySet {
    /**
     * 使用Foreach遍历,通过keyset()方法
     * Foreach适用于只在集合或数组中进行遍历,for则在较复杂的循环中效率更高
     * Foreach不能对集合或者数组中的元素进行添加和删除操作,因此需要修改元素(添加,删除)则需要使用for循环
     * @param args
     */
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        //使用Foreach遍历,通过keyset()方法
        for (Integer key:map.keySet()) {
            System.out.println(key);
            System.out.println(map.get(key));
        }
    }
}


5.Lambda
public class Lambda {
    public static void main(String[] args) {

        /**
         * Lambda表达式实现Map遍历
         */
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // Lambda遍历:(参数类型 参数名称) ‐> { 代码语句 }
        map.forEach((key,value)->{
            System.out.println(key);
            System.out.println(map.get(key));
        });
    }
}

6.Streams API 单线程

public class StreamsOne {
    /**
     * SteamsAPI是对集合的一种操作;
     *
     * @param args
     */
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        //遍历
        map.entrySet().stream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}


7.Stream APT多线程
public class StreamsOne {
    /**
     * SteamsAPI是对集合的一种操作;
     * map.entrySet().Stream().forEach单线程
     * map.entrySet().parallelStream().forEach单线程
     * @param args
     */
    public static void main(String[] args) {
        // 创建并赋值 HashMap
        Map<Integer, String> map = new HashMap();
        map.put(1, "Java");
        map.put(2, "JDK");
        map.put(3, "Spring Framework");
        map.put(4, "MyBatis framework");
        map.put(5, "Java中文社群");
        // map.entrySet().Stream().forEach单线程
        // map.entrySet().parallelStream().forEach单线程
        map.entrySet().parallelStream().forEach((entry) -> {
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        });
    }
}

以上程序的执行结果为:(因为是多线程,所以与之前的结果不一样)

4

MyBatis framework

5

Java中文社群

1

Java

2

JDK

3

Spring Framework

 

性能测试:

其中 Units 为 ns/op 意思是执行完成时间(单位为纳秒),而 Score 列为平均执行时间, ± 符号表示误差。从以上结果可以看出,两个 entrySet 的性能相近,并且执行速度最快,接下来是 stream ,然后是两个 keySet,性能最差的是 Lambda。

结论

从以上结果可以看出 entrySet 的性能比 keySet 的性能高出了一倍之多,因此我们应该尽量使用 entrySet  来实现 Map 集合的遍历

从结果可以看出,除了 Lambda 和 Streams API 之外,通过迭代器循环和 for 循环的遍历的 EntrySet 最终生成的代码是一样的,他们都是在循环中创建了一个遍历对象 Entry ,代码如下:

public static void entrySet() {
    Iterator var0 = map.entrySet().iterator();
    while(var0.hasNext()) {
        Entry var1 = (Entry)var0.next();
        System.out.println(var1.getKey());
        System.out.println((String)var1.getValue());
    }
}
public static void forEachEntrySet() {
    Iterator var0 = map.entrySet().iterator();
    while(var0.hasNext()) {
        Entry var1 = (Entry)var0.next();
        System.out.println(var1.getKey());
        System.out.println((String)var1.getValue());
    }
}

而 KeySet 的代码也是类似的,如下所示:

public static void keySet() {
    Iterator var0 = map.keySet().iterator();
    while(var0.hasNext()) {
        Integer var1 = (Integer)var0.next();
        System.out.println(var1);
        System.out.println((String)map.get(var1));
    }
} 
public static void forEachKeySet() {
    Iterator var0 = map.keySet().iterator();
    while(var0.hasNext()) {
        Integer var1 = (Integer)var0.next();
        System.out.println(var1);
        System.out.println((String)map.get(var1));
    }
}

所以我们在使用迭代器或是 for 循环 EntrySet 时,他们的性能都是相同的,因为他们最终生成的字节码基本都是一样的;同理 KeySet 的两种遍历方式也是类似的。

性能分析

EntrySet 之所以比 KeySet 的性能高是因为,KeySet 在循环时使用了 map.get(key),而 map.get(key) 相当于又遍历了一遍 Map 集合去查询 key 所对应的值。为什么要用“又”这个词?那是因为在使用迭代器或者 for 循环时,其实已经遍历了一遍 Map 集合了,因此再使用 map.get(key) 查询时,相当于遍历了两遍

而 EntrySet 只遍历了一遍 Map 集合,之后通过代码“Entry<Integer, String> entry = iterator.next()”把对象的 key 和 value 值都放入到了 Entry 对象中,因此再获取 key 和 value 值时就无需再遍历 Map 集合,只需要从 Entry 对象中取值就可以了。

所以,EntrySet 的性能比 KeySet 的性能高出了一倍,因为 KeySet 相当于循环了两遍 Map 集合,而 EntrySet 只循环了一遍

因此选EntrySet方法!!!

安全性测试

从上面的性能测试结果和原理分析,我想大家应该选用那种遍历方式,已经心中有数的,而接下来我们就从「安全」的角度入手,来分析那种遍历方式更安全。

我们把以上遍历划分为四类进行测试:迭代器方式、For 循环方式、Lambda 方式和 Stream 方式,测试代码如下。

1.迭代器方式

Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<Integer, String> entry = iterator.next();
    if (entry.getKey() == 1) {
        // 删除
        System.out.println("del:" + entry.getKey());
        iterator.remove();
    } else {
        System.out.println("show:" + entry.getKey());
    }
}

以上程序的执行结果:

show:0

del:1

show:2

测试结果:迭代器中循环删除数据安全

2.For 循环方式

for (Map.Entry<Integer, String> entry : map.entrySet()) {
    if (entry.getKey() == 1) {
        // 删除
        System.out.println("del:" + entry.getKey());
        map.remove(entry.getKey());
    } else {
        System.out.println("show:" + entry.getKey());
    }
}

以上程序的执行结果:

测试结果:For 循环中删除数据非安全

3.Lambda 方式

map.forEach((key, value) -> {
    if (key == 1) {
        System.out.println("del:" + key);
        map.remove(key);
    } else {
        System.out.println("show:" + key);
    }
});

以上程序的执行结果:

测试结果:Lambda 循环中删除数据非安全

Lambda 删除的正确方式

// 根据 map 中的 key 去判断删除
map.keySet().removeIf(key -> key == 1);
map.forEach((key, value) -> {
    System.out.println("show:" + key);
});

以上程序的执行结果:

show:0

show:2

从上面的代码可以看出,可以先使用 Lambda 的 removeIf 删除多余的数据,再进行循环是一种正确操作集合的方式。

4.Stream 方式

map.entrySet().stream().forEach((entry) -> {
    if (entry.getKey() == 1) {
        System.out.println("del:" + entry.getKey());
        map.remove(entry.getKey());
    } else {
        System.out.println("show:" + entry.getKey());
    }
}); 以上程序的执行结果:

测试结果:Stream 循环中删除数据非安全

Stream 循环的正确方式

map.entrySet().stream().filter(m -> 1 != m.getKey()).forEach((entry) -> {
    if (entry.getKey() == 1) {
        System.out.println("del:" + entry.getKey());
    } else {
        System.out.println("show:" + entry.getKey());
    }
});

以上程序的执行结果:

show:0

show:2

从上面的代码可以看出,可以使用 Stream 中的 filter 过滤掉无用的数据,再进行遍历也是一种安全的操作集合的方式。

 

 

总结:本文我们讲了 HashMap 4 种遍历方式:迭代器、for、lambda、stream,以及具体的 7 种遍历方法,综合性能和安全性来看,我们应该尽量使用迭代器(Iterator)来遍历 EntrySet 的遍历方式来操作 Map 集合,这样就会既安全又高效了。

迭代器删除元素是安全的;

For删除元素不是安全的;

Lambda和Steam可以安全也可以不安全,取决于是否先判断删除(即不在循环中删除);

0 75

Java中集合框架是我们经常需要使用到的一个部分,以前我觉得它的用处是做Leetcode算法题,经过一段学习之后发现集合框架是Java体系的一块基石,例如Hash表在索引中的使用,List在实际开发用于保存各种类型的对象列表,Map键值对的形式用在查询或是记录信息上效率之高……

相信我,如果想要探索Java世界的奥秘,我们有必要了解集合;

 

本文转载自Githubhttps://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/Java集合框架常见面试题.md             JavaGuide

一、集合概述

1.1.1Java集合概览

除了以Map结尾的类之外,其他类都实现了Collection接口,并且,以Map结尾的类都实现了Map接口

1.1.2说说List,Set,Map三者的区别

  • List(对付顺序的好帮手):存储的元素是有序的,可重复的
  • Set(注重独一无二的性质):存储的元素是无序的、不可重复的
  • Map(用Key来搜索的专家):使用键值对(Key-value)存储,类似于数学上的函数y=f(x),“x”代表Key,“y”代表value,Key是无序、不可重复的,value是无序,可重复的,每个键最多映射到一个值

1.1.3. 集合框架底层数据结构总结

先来看一下 Collection 接口下面的集合。

1.1.3.1. List

  • Arraylist: Object[]数组
  • VectorObject[]数组
  • LinkedList: 双向链表(JDK1.6 之前为循环链表,JDK1.7 取消了循环)

1.1.3.2. Set

  • HashSet(无序,唯一): 基于 HashMap 实现的,底层采用 HashMap 来保存元素
  • LinkedHashSetLinkedHashSet 是 HashSet 的子类,并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样,不过还是有一点点区别的
  • TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树)

再来看看 Map 接口下面的集合。

1.1.3.3. Map

  • HashMap: JDK1.8 之前 HashMap 由数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。JDK1.8 以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间
  • LinkedHashMap: LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。详细可以查看:《LinkedHashMap 源码详细分析(JDK1.8)》
  • Hashtable: 数组+链表组成的,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的
  • TreeMap: 红黑树(自平衡的排序二叉树)

1.1.4. 如何选用集合?

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合,需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap

当我们只需要存放元素值时,就选择实现Collection 接口的集合,需要保证元素唯一时选择实现 Set接口的集合比如 TreeSet 或 HashSet,不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList,然后再根据实现这些接口的集合的特点来选用。

1.1.5. 为什么要使用集合?

当我们需要保存一组类型相同的数据的时候,我们应该是用一个容器来保存,这个容器就是数组,但是,使用数组存储对象具有一定的弊端, 因为我们在实际开发中,存储的数据的类型是多种多样的,于是,就出现了“集合”,集合同样也是用来存储多个数据的。

数组的缺点是一旦声明之后,长度就不可变了;

同时,声明数组时的数据类型也决定了该数组存储的数据的类型;而且,数组存储的数据是有序的、可重复的,特点单一。

集合提高了数据存储的灵活性,Java 集合不仅可以用来存储不同类型不同数量的对象,还可以保存具有映射关系的数据。

1.2. Collection 子接口之 List

1.2.1. Arraylist 和 Vector 的区别?

  • ArrayList 是 List 的主要实现类,底层使用 Object[ ]存储,适用于频繁的查找工作,线程不安全 ;
  • Vector 是 List 的古老实现类,底层使用 Object[ ] 存储,线程安全的。

1.2.2. Arraylist 与 LinkedList 区别?

  1. 是否保证线程安全: ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;
  2. 底层数据结构: Arraylist 底层使用的是 Object 数组LinkedList 底层使用的是 双向链表 数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。注意双向链表和双向循环链表的区别,下面有介绍到!)
  3. 插入和删除是否受元素位置的影响: ① ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储,所以对于add(E e)方法的插入,删除元素时间复杂度不受元素位置的影响,近似 O(1),如果是要在指定位置i插入和删除元素的话((add(int index, E element)) 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
  4. 是否支持快速随机访问: LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  5. 内存空间占用: ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

1.2.2.1. 补充内容:双向链表和双向循环链表

双向链表: 包含两个指针,一个 prev 指向前一个节点,一个 next 指向后一个节点。

另外推荐一篇把双向链表讲清楚的文章:https://juejin.im/post/5b5d1a9af265da0f47352f14

双向链表

双向循环链表: 最后一个节点的 next 指向 head,而 head 的 prev 指向最后一个节点,构成一个环。

双向循环链表

1.2.2.2. 补充内容:RandomAccess 接口

public interface RandomAccess {
}

查看源码我们发现实际上 RandomAccess 接口中什么都没有定义。所以,在我看来 RandomAccess 接口不过是一个标识罢了。标识什么? 标识实现这个接口的类具有随机访问功能。

在 binarySearch() 方法中,它要判断传入的 list 是否 RamdomAccess 的实例,如果是,调用indexedBinarySearch()方法,如果不是,那么调用iteratorBinarySearch()方法

    public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

ArrayList 实现了 RandomAccess 接口, 而 LinkedList 没有实现。为什么呢?我觉得还是和底层数据结构有关!ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素,时间复杂度为 O(n),所以不支持快速随机访问。,ArrayList 实现了 RandomAccess 接口,就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识,并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的!

1.2.3. 说一说 ArrayList 的扩容机制吧

1.2.3. 说一说 ArrayList 的扩容机制吧

详见笔主的这篇文章:通过源码一步一步分析 ArrayList 扩容机制

1.3. Collection 子接口之 Set

1.3.1. comparable 和 Comparator 的区别

  • comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
  • comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序

一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo()方法或compare()方法,当我们需要对某一个集合实现两种排序方式,比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的 Collections.sort().

1.3.1.1. Comparator 定制排序

        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        arrayList.add(-1);
        arrayList.add(3);
        arrayList.add(3);
        arrayList.add(-5);
        arrayList.add(7);
        arrayList.add(4);
        arrayList.add(-9);
        arrayList.add(-7);
        System.out.println("原始数组:");
        System.out.println(arrayList);
        // void reverse(List list):反转
        Collections.reverse(arrayList);
        System.out.println("Collections.reverse(arrayList):");
        System.out.println(arrayList);

        // void sort(List list),按自然排序的升序排序
        Collections.sort(arrayList);
        System.out.println("Collections.sort(arrayList):");
        System.out.println(arrayList);
        // 定制排序的用法
        Collections.sort(arrayList, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        System.out.println("定制排序后:");
        System.out.println(arrayList);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList):
[-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList):
[-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后:
[7, 4, 3, 3, -1, -5, -7, -9]

1.3.1.2. 重写 compareTo 方法实现按年龄来排序

// person对象没有实现Comparable接口,所以必须实现,这样才不会出错,才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口,详细可以查看String类的API文档,另外其他
// 像Integer类等都已经实现了Comparable接口,所以不需要另外实现了
public  class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        super();
        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;
    }

    /**
     * T重写compareTo方法实现按年龄来排序
     */
    @Override
    public int compareTo(Person o) {
        if (this.age > o.getAge()) {
            return 1;
        }
        if (this.age < o.getAge()) {
            return -1;
        }
        return 0;
    }
}
    public static void main(String[] args) {
        TreeMap<Person, String> pdata = new TreeMap<Person, String>();
        pdata.put(new Person("张三", 30), "zhangsan");
        pdata.put(new Person("李四", 20), "lisi");
        pdata.put(new Person("王五", 10), "wangwu");
        pdata.put(new Person("小红", 5), "xiaohong");
        // 得到key的值的同时得到key所对应的值
        Set<Person> keys = pdata.keySet();
        for (Person key : keys) {
            System.out.println(key.getAge() + "-" + key.getName());

        }
    }

Output:

5-小红
10-王五
20-李四
30-张三

1.3.2. 无序性和不可重复性的含义是什么

1、什么是无序性?无序性不等于随机性 ,无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ,而是根据数据的哈希值决定的。

2、什么是不可重复性?不可重复性是指添加的元素按照 equals()判断时 ,返回 false,需要同时重写 equals()方法和 HashCode()方法。

1.3.3. 比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

HashSet 是 Set 接口的主要实现类 ,HashSet 的底层是 HashMap,线程不安全的,可以存储 null 值;

LinkedHashSet 是 HashSet 的子类,能够按照添加的顺序遍历;

TreeSet 底层使用红黑树,能够按照添加元素的顺序进行遍历,排序的方式有自然排序和定制排序。

1.4. Map 接口

1.4.1. HashMap 和 Hashtable 的区别

  1. 线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!);
  2. 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它;
  3. 对 Null key 和 Null value 的支持: HashMap 可以存储 null 的 key 和 value,但 null 作为键只能有一个,null 作为值可以有多个;HashTable 不允许有 null 键和 null 值,否则会抛出 NullPointerException
  4. 初始容量大小和每次扩充容量大小的不同 : ① 创建时如果不指定容量初始值,Hashtable 默认的初始大小为 11,之后每次扩充,容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充,容量变为原来的 2 倍。② 创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小(HashMap 中的tableSizeFor()方法保证,下面给出了源代码)。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
  5. 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。

HashMap 中带有初始容量的构造函数:

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

1.4.2. HashMap 和 HashSet 区别

如果你看过 HashSet 源码的话就应该知道:HashSet 底层就是基于 HashMap 实现的。(HashSet 的源码非常非常少,因为除了 clone()writeObject()readObject()是 HashSet 自己不得不实现之外,其他方法都是直接调用 HashMap 中的方法。

HashMap HashSet
实现了 Map 接口 实现 Set 接口
存储键值对 仅存储对象
调用 put()向 map 中添加元素 调用 add()方法向 Set 中添加元素
HashMap 使用键(Key)计算 hashcode HashSet 使用成员对象来计算 hashcode 值,对于两个对象来说 hashcode 可能相同,所以 equals()方法用来判断对象的相等性

1.4.3. HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ,但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序,不过我们也可以指定排序的比较器。示例代码如下:

/**
 * @author shuang.kou
 * @createTime 2020年06月15日 17:02:00
 */
public class Person {
    private Integer age;

    public Person(Integer age) {
        this.age = age;
    }

    public Integer getAge() {
        return age;
    }


    public static void main(String[] args) {
        TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
            @Override
            public int compare(Person person1, Person person2) {
                int num = person1.getAge() - person2.getAge();
                return Integer.compare(num, 0);
            }
        });
        treeMap.put(new Person(3), "person1");
        treeMap.put(new Person(18), "person2");
        treeMap.put(new Person(35), "person3");
        treeMap.put(new Person(16), "person4");
        treeMap.entrySet().stream().forEach(personStringEntry -> {
            System.out.println(personStringEntry.getValue());
        });
    }
}

输出:

person1
person4
person2
person3

可以看出,TreeMap 中的元素已经是按照 Person 的 age 字段的升序来排列了。

上面,我们是通过传入匿名内部类的方式实现的,你可以将代码替换成 Lambda 表达式实现的方式:

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
  int num = person1.getAge() - person2.getAge();
  return Integer.compare(num, 0);
});

综上,相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

1.4.4. HashSet 如何检查重复

以下内容摘自我的 Java 启蒙书《Head fist java》第二版:

当你把对象加入HashSet时,HashSet 会先计算对象的hashcode值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode 值作比较,如果没有相符的 hashcodeHashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让加入操作成功。

hashCode()与 equals() 的相关规定:

  1. 如果两个对象相等,则 hashcode 一定也是相同的
  2. 两个对象相等,对两个 equals() 方法返回 true
  3. 两个对象有相同的 hashcode 值,它们也不一定是相等的
  4. 综上,equals() 方法被覆盖过,则 hashCode() 方法也必须被覆盖
  5. hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode(),则该 class 的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

==与 equals 的区别

对于基本类型来说,== 比较的是值是否相等;

对于引用类型来说,== 比较的是两个引用是否指向同一个对象地址(两者在内存中存放的地址(堆内存地址)是否指向同一个地方);

对于引用类型(包括包装类型)来说,equals 如果没有被重写,对比它们的地址是否相等;如果 equals()方法被重写(例如 String),则比较的是地址里的内容。

1.4.5. HashMap 的底层实现

1.4.5.1. JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值,然后通过 (n – 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度),如果当前位置存在元素的话,就判断该元素与要存入的元素的 hash 值以及 key 是否相同,如果相同的话,直接覆盖,不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化,但是原理不变。

    static final int hash(Object key) {
      int h;
      // key.hashCode():返回散列值也就是hashcode
      // ^ :按位异或
      // >>>:无符号右移,忽略符号位,空位都以0补齐
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).

    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法 ,JDK 1.7 的 hash 方法的性能会稍差一点点,因为毕竟扰动了 4 次。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

jdk1.8之前的内部结构-HashMap

1.4.5.2. JDK1.8 之后

相比于之前的版本, JDK1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。

jdk1.8之后的内部结构-HashMap

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

1.4.6. HashMap 的长度为什么是 2 的幂次方

为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648 到 2147483647,前后加起来大概 40 亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢?

我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是 2 的幂次方。

1.4.7. HashMap 多线程操作导致死循环问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题,但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

详情请查看:https://coolshell.cn/articles/9606.html

1.4.8. HashMap 有哪几种常见的遍历方式?

HashMap 的 7 种遍历方式与性能分析!

1.4.9. ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

  • 底层数据结构: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;
  • 实现线程安全的方式(重要): ① 在 JDK1.7 的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。

两者的对比图:

HashTable:

HashTable全表锁

http://www.cnblogs.com/chengxiao/p/6842045.html>

JDK1.7 的 ConcurrentHashMap:

JDK1.7的ConcurrentHashMap

http://www.cnblogs.com/chengxiao/p/6842045.html>

JDK1.8 的 ConcurrentHashMap:

Java8 ConcurrentHashMap 存储结构(图片来自 javadoop)

JDK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表,而是 Node 数组 + 链表 / 红黑树。不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode。当冲突链表达到一定长度时,链表会转换成红黑树。

1.4.10. ConcurrentHashMap 线程安全的具体实现方式/底层具体实现

1.4.10.1. JDK1.7(上面有示意图)

首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成

Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁,扮演锁的角色。HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap 类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个 HashEntry 数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 的锁。

1.4.10.2. JDK1.8 (上面有示意图)

ConcurrentHashMap 取消了 Segment 分段锁,采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似,数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为 O(N))转换为红黑树(寻址时间复杂度为 O(log(N)))

synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。

1.5. Collections 工具类

Collections 工具类常用方法:

  1. 排序
  2. 查找,替换操作
  3. 同步控制(不推荐,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

1.5.1. 排序操作

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序,由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时,将list后distance个元素整体移到前面。当distance为负数时,将 list的前distance个元素整体移到后面

1.5.2. 查找,替换操作

int binarySearch(List list, Object key)//对List进行二分查找,返回索引,注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序,返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序,返回最大元素,排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素。
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引,找不到则返回-1,类比int lastIndexOfSubList(List source, list target).
boolean replaceAll(List list, Object oldVal, Object newVal), 用新元素替换旧元素

1.5.3. 同步控制

Collections 提供了多个synchronizedXxx()方法·,该方法可以将指定集合包装成线程同步的集合,从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSetTreeSetArrayList,LinkedList,HashMap,TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法,效率非常低,需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

方法如下:

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步(线程安全的)collection。
synchronizedList(List<T> list)//返回指定列表支持的同步(线程安全的)List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步(线程安全的)Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步(线程安全的)set。

详解集合线程安全:http://yangbili.co/%e7%ba%bf%e7%a8%8b%e5%ae%89%e5%85%a8%e4%b8%8e%e5%90%a6/