集合(3)Set和Map——HashSet和HashMap_hashmap set-程序员宅基地

技术标签: Java集合  java  hashmap  

目录

一、哈希表(散列表)

二、HashSet

1、Set简介

2、HashSet

二、HashMap

1、Map简介

2、HashMap

(1)基本映射操作

(2)更新映射项

(3)映射视图

(4)HashMap在不同jdk版本的变化

(5)计算索引


Set和Map的底层联系密切,例如,HashSet依赖于HashMap,它实际上是通过HashMap实现的;TreeSet依赖于TreeMap,它实际上是通过TreeMap实现的。

先看HashSet和HashMap,这两者都是基于哈希表实现的。

一、哈希表(散列表)

链表和数组可以按照人们的意愿排列元素的次序。但是,如果想要査看某个指定的元素,却又忘记了它的位置,就需要访问所有元素,直到找到为止。如果集合中包含的元素很多,将会消耗很多时间如果不在意元素的顺序,可以有几种能够快速査找元素的数据结构,其缺点是无法控制元素出现的次序,它们将按照有利于其操作目的的原则组织数据。

有一种众所周知的数据结构,可以快速地査找所需要的对象,这就是散列表。散列表为每个对象计算一个整数,称为散列码(hash table)。散列码是由对象的实例域产生的一个整数。更准确地说,具有不同数据域的对象将产生不同的散列码

如果自定义类,就要负责实现这个类的hashCode方法。注意,自己实现的hashCode方法应该与equals方法兼容,即如果a.equals(b)为true,a与b必须具有相同的散列码。

简单来说,散列表是根据Key的值而直接进行访问的数据结构。也就是说,它通过把Key值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

关于哈希表的更多:哈希表原理及实现

 在Java中,散列表用链表数组实现。每个列表被称为(bucket)。要想査找表中对象的位置,就要先计算它的散列码,然后与桶的总数取余,所得到的结果就是保存这个元素的桶的索引。例如,如果某个对象的散列码为76268,并且有128个桶,对象应该保存在第108号桶中(76268除以128余108)。或许会很幸运,在这个桶中没有其他元素,此时将元素直接插入到桶中就可以了。当然,有时候会遇到桶被占满的情况,这也是不可避免的。这种现象被称为散列冲突(hash collision)。这时,需要用新对象与桶中的所有对象进行比较,査看这个对象是否已经存在。如果散列码是合理且随机分布的,桶的数目也足够大,需要比较的次数就会很少。

如果想更多地控制散列表的运行性能,就要指定一个初始的桶数。桶数是指用于收集具有相同散列值的桶的数目。如果要插入到散列表中的元素太多,就会增加冲突的可能性,降低运行性能。

如果大致知道最终会有多少个元素要插入到散列表中,就可以设置桶数。通常,将桶数设置为预计元素个数的75%~150%。有些研究人员认为:尽管还没有确凿的证据,但最好将桶数设置为一个素数,以防键的集聚。标准类库使用的桶数是2的幂,默认值为16(为表大小提供的任何值都将被自动地转换为2的下一个幂)。

当然,并不是总能够知道需要存储多少个元素的,也有可能最初的估计过低。如果散列表太满,就需要再散列(rehashed)。如果要对散列表再散列,就需要创建一个桶数更多的表,并将所有元素插入到这个新表中,然后丢弃原来的表。装填因子(load factor)决定何时对散列表进行再散列。例如,如果装填因子为0.75(默认值),而表中超过75%的位置已经填入元素,这个表就会用双倍的桶数自动地进行再散列。对于大多数应用程序来说,装填因子为75%是比较合理的。

散列表用于实现几个重要的数据结构。最简单的就是Set类型。

二、HashSet

1、Set简介

set 是没有重复元素的元素集合。

set的 add 方法首先在集中查找要添加的对象, 如果不存在 , 就将这个对象添加进去。

2、HashSet

HashSet是基于散列表的集。可以用 add 方法添加元素。contains方法已经被重新定义,用来快速地查看是否某个元素已经出现在集中。它只在某个桶中査找元素,而不必查看集合中的所有元素。

散列集迭代器将依次访问所有的桶。由于散列将元素分散在表的各个位置上,所以访问它们的顺序几乎是随机的。只有不关心集合中元素的顺序时才应该使用HashSet。

HashSet底层使用HashMap实现的,HashSet会将元素存储在HashMap的key集合中,然后为value赋一个static空对象PRESENT。

HashSet不能存储重复元素,因为HashMap的key集合不可以重复,本质也是通过equals()和hashCode()来判定两个对象是否重复,因此将对象存储在HashSet之前,必须先重写对象的equals()和hashCode()方法。

hashCode原则:

两个对象的hashCode()相等,equals()未必返回true

两个对象equals()返回true,它们的hashCode()一定相等

HashMap中,只有两个对象hashCode()相等,且equals()相同,才判定为重复元素,重写对象的equals()方法一定要同时重写hashCode()以符合原则。

HashSet是非同步的。如果多个线程同时访问一个哈希 set,而其中至少一个线程修改了该 set,那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象,则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作,以防止对该 set 进行意外的不同步访问:

Set s = Collections.synchronizedSet(new HashSet(...));

HashSet通过iterator()返回的迭代器是fail-fast的。

参考:HashSet详解

二、HashMap

1、Map简介

Map是一个映射接口,即key-value键值对。Map中的每一个元素包含“一个key”和“key对应的value”。

不允许键重复(重复了覆盖了),但允许值重复。

AbstractMap是个抽象类,它实现了Map接口中的大部分API。而HashMap,TreeMap,WeakHashMap都是继承于AbstractMap。Hashtable虽然继承于Dictionary,但它实现了Map接口。

2、HashMap

(1)基本映射操作

集是一个集合,它可以快速地査找现有的元素。但是,要査看一个元素,需要有要査找元素的精确副本。这不是一种非常通用的査找方式。通常,我们知道某些键的信息并想要査找与之对应的元素映射表(map)数据结构就是为此设计的。映射表用来存放键/值对。如果提供了键,就能够査找到值。例如,有一张关于员工信息的记录表,键为员工ID,值为Employee对象。

Java类库为映射表提供了两个通用的实现:HashMap和TreeMap。这两个类都实现了Map接口。

散列映射表(HashMap)对键进行散列,树映射表(TreeMap)用键的整体顺序对元素进行排序,并将其组织成搜索树。散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

应该选择散列映射表还是树映射表呢?与集一样,散列稍微快一些,如果不需要按昭排列顺序访问键,就最好选择散列。

下列代码将为存储的员工信息建立一个散列映射表:

Map<String, Employee> staff = new HashMap<String, Employee>();

staff.put("144-25-5464", new Employee("Amy Lee"));

staff.put("567-24-2546", new Employee("Harry Hacker"));

每当往映射表中添加对象时,必须同时提供一个键。在这里,键是一个字符串,对应的值是Employee对象。

 要想检索一个对象,必须提供(因而,必须记住)一个键:

String s = "144-25-5464";

staff.get(s);

如果在Java中没有与给定键对应的信息,get将返回null。

null 返回值可能并不方便 。 有时可以有一个好的默认值 , 用作为映射中不存在的键 。 然后使用 getOrDefault 方法。

Map<String , Integer> scores = . .
int score = scores.getOrDefault( id , 0 ) ; / / Gets 0 if the id is not present

键必须是唯一的。不能对同一个键存放两个值。如果对同一个键两次调用put方法,第二个值就会取代第一个值。实际上,put将返回用这个键参数存储的上一个值

remove方法用于从映射表中删除给定键对应的元素。size方法用于返回映射表中的元素数。

要迭代处理映射的键和值 , 最容易的方法是使用 forEach 方法。 可以提供一个接收键和值的 lambda 表达式。 映射中的每一项会依序调用这个表达式。

scores.forEach ( ( k , v ) - >
System.out.println ( " key = " + k + " , value : " + v ));

(2)更新映射项

        处理映射时的一个难点就是更新映射项。正常情况下,可以得到与一个键关联的原值,完成更新, 再放回更新后的值。不过,必须考虑一个特殊情况, 即键第一次出现。键第一次出现时,调用get方法会返回 null, 因此会出现一个NullPointerException 异常。

        作为一个简单的补救, 可以使用 getOrDefault 方法:

counts.put(word, counts.getOrDefault(word, 0)+ 1);

        另一种方法是首先调用 putlfAbsent 方法。只有当键原先存在时才会放入一个值。(putIfAbsent   如果传入key对应的value已经存在,就返回存在的value,不进行替换。如果不存在,就添加key和value,返回null)

counts.putlfAbsent(word, 0);
counts.put(word, counts.get(word)+ 1); // Now we know that get will succeed

        不过还可以做得更好。merge 方法可以简化这个常见的操作。如果键原先不存在,下面的调用将把 word 与 1 关联 , 否则使用 Integer :: sum 函数组合原值和 1 ( 也就是将原值与 1 求和 ):

counts.merge(word, 1, Integer::sum);

(3)映射视图

集合框架并没有将映射表本身视为一个集合(其他的数据结构框架则将映射表视为对(pair)的集合,或者视为用键作为索引的值的集合。然而,可以获得映射表的视图,这是一组实现了Collection接口对象,或者它的子接口的视图。

有3个视图,它们分别是:键集、值集合(不是集)和键/值对集。键与键/值对形成了一个集,这是因为在映射表中一个键只能有一个副本。下列方法将返回这3个视图(条目集的元素是静态内部类Map.Entry的对象)。

Set<K> keySet()

Collection<K> values()

Set<Map.Entry<K, V>> entrySet()

 注意,keySet既不是HashSet,也不是TreeSet,而是实现了Set接口的某个其他类的对象。Set接口扩展了Collection接口,因此,可以与使用任何集合一样使用keySet。例如,可以枚举映射表中的所有键:

Set<String> keys = map.keySet();

for (String key : keys)

    doSomethingWith(key);

提示:如果想要同时查看键与值,就可以通过枚举各个条目(entries)查看,以避免对值进行查找,可以使用下面这段代码框架:

for (Map.Entry<String, Employee> entry : staff.entrySet()) {

            String key = entry.getKey();

            Employee value = entry.getValue();

            doSomethingWith(key, value);

        }

ps:原先这是访问所有映射条目的最高效的方法。 如今 , 只需要使用forEach 方法 :

counts.forEach((k,v)->{
    do something with k , v
});

如果在键集视图上调用迭代器的remove方法,实际上就从映射表中删除了键以及对应的值。但是,不能将元素添加到键集的视图中。如果只添加键而不添加值是毫无意义的。如果试图调用add方法,将会抛出一个UnsupportedOperationException异常,条目集视图也有同样的限制,不过,从概念上讲,添加新的键/值对是有意义的。

更多:HashMap详细介绍(源码解析,迭代方式等)和使用示例

(4)HashMap在不同jdk版本的变化

上面链接中解析时部分基于JDK1.6的版本。

JDK1.6:

HashMap是基于数组+链表实现的,hash碰撞多的话,会导致获取数据变慢。

new HashMap时,开辟了内存空间,如果不使用,则浪费内存。

hash算法复杂,扩容算法是resize(2 * table.length)。

JDK1.7:

改成了懒汉初始化,意味着new HashMap并没有开辟内存空间

JDK1.8:

(getOrDefault方法和Lambda表达式都是1.8新增的方法)

HashMap是基于数组+链表+红黑树实现的(链表长度超过8时,转为红黑树,ConcurrentHashMap与此类似),解决了碰撞较多时的效率问题。

hash算法改为了XORs算法x ^ (x>>>16),可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

扩容算法改为ewThr = oldThr << 1

(5)计算索引

在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表,这样就大大优化了查询的效率。

对于任意给定的对象,只要它的 hashCode() 返回值相同,那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中是这样做的:调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下:

static int indexFor(int h, int length) {  
    return h & (length-1);  
}  

这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的n 次方这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码:

int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;  

这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方 。

当length总是 2 的n次方时,h& (length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

ArrayQueue也使用了&代替%这个优化)

这看上去很简单,其实比较有玄机的,我们举个例子来说明:

从上面的例子中可以看出:当8、9两个数和(15-1)2=(1110)进行“与运算&”的时候,产生了相同的结果,都为0100,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链 表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hash值会与(15-1)2=(1110)进行“与运算&”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!

当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1(比如(24-1)2=1111),这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

  所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

参考:HashMap详解

 

参考:《Java核心技术 卷I》

https://blog.csdn.net/xunwei0303/article/details/80318485

https://www.jianshu.com/p/b98010c22975

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wyplj2015/article/details/91806827

智能推荐

5G网络身份识别---详解5G-GUTI_5g guami-程序员宅基地

文章浏览阅读3.5k次,点赞4次,收藏19次。5G-GUTI是AMF分配给用户的全球唯一标识的临时身份识别信息,3GPP和non-3gpp共用,AMF可以在任意时刻重分配5G-GUTI给UE。 := GUAMI可以识别一个或多个AMF,当GUAMI唯一识别一个AMF时,5G-TMSI唯一这个AMF下的唯一UE;当GUAMI标识多个AMF时,AMF需要做到分配5G-GUTI时,不能与自己share GUAMI的AMF分配的5G-GUTI重复,保证5G-GUTI的唯一性。5GC现网我了解一般都是前者,GUAMI唯一........._5g guami

深度学习的可解释性!-程序员宅基地

文章浏览阅读1.1w次,点赞23次,收藏139次。一、深度学习的可解释性研究概述随着深度学习模型在人们日常生活中的许多场景下扮演着越来越重要的角色,模型的「可解释性」成为了决定用户是否能够「信任」这些模型的关键因素(尤其是当我们需要机器为..._可解释性

第四章 CSS样式表_css: -webkit-box-reflect给图片设置倒影实例-程序员宅基地

文章浏览阅读1.1k次。样式的分类: 1、行类样式 2、内嵌式样式 3、外部样式选择器的分类 1、标签选择器 2、类选择器 3、ID选择器 4、伪类选择器内嵌式样式 _css: -webkit-box-reflect给图片设置倒影实例

Mysql主从备份数据库服务器搭建_mysql主备搭建-程序员宅基地

文章浏览阅读7.5k次,点赞9次,收藏52次。一,引入mysql主从备份1,为什么要做主从备份防止数据丢失,数据的热备份,架构的扩展。业务量越来越大,I/O访问频率过高,单机无法满足,此时做多库的存储,降低磁盘 I/O访问的频率,提高单个机器的I/O性能2,什么是mysql主从备份MySQL 主从复制是指数据可以从一个MySQL数据库服务器主节点复制到一个或多个从节点。 MySQL 默认采用异步复制方式,这样从节点不用一直访问主服务器来更新自己的数据,数据的更新可 以在远程连接上进行,从节点可以复制主数据库中的所有数据库或者特定的数据库_mysql主备搭建

Linux下用命令行编译运行Java总结_用linux编译java文件感悟-程序员宅基地

文章浏览阅读3w次,点赞26次,收藏106次。最近使用腾讯云的Cloud Studio写Java,只能使用命令行进行编译运行,趁此机会,学习一下Linux的一些常用命令。平时windows下IDE用习惯了,现在用命令行进行编译运行,发现其实问题还是挺多的,所以写下这篇文章。1.javac命令行javac用于编译java源文件,生成.class文件。形式如下javac [option] source常用的option..._用linux编译java文件感悟

获得程序的句柄_如何取得程序句柄-程序员宅基地

文章浏览阅读703次。DWORD aProcesses[1024], dwSize, dwSize2; char szProcessName[MAX_PATH] = "unknown"; char MyProcessName[MAX_PATH] = "Test.exe";//用实际文件名代替 unsigned int i; if _如何取得程序句柄

随便推点

Geany文本编辑器_geany编辑器显示方框-程序员宅基地

文章浏览阅读5.3k次,点赞3次,收藏8次。第一步,下载Geany,在百度里搜Geany点开Geany:Home Page第二步,在Download里点Releases.第三步,点windows下的下载程序下载,下载好后设置安装文件夹,然后一路安装。第四步,安装好之后打开Geany,点“生成”设置生成命令。第五步,在设置生成命令里需要Python的安装位置,这时候找到Python,点文件所在位置,找到后右键点“属性”里面有Python的目标..._geany编辑器显示方框

Github Actions 使用Docker部署SpringBoot_docker/setup-qemu-action@v3-程序员宅基地

文章浏览阅读372次。Github Actions 使用Docker部署SpringBoot_docker/setup-qemu-action@v3

YOLOV5-seg中json转txt及划分数据集_seg_json-程序员宅基地

文章浏览阅读1.5k次,点赞4次,收藏26次。yolov5-seg自制数据集的划分_seg_json

C#/.NET 多线程任务Task的详解——应用实例_.net task-程序员宅基地

文章浏览阅读9.9k次,点赞2次,收藏32次。Task类介绍:Task 类的表示单个操作不返回一个值,通常以异步方式执行。 Task 对象是一个的中心思想 基于任务的异步模式 首次引入.NET Framework 4 中。 因为由执行工作 Task 对象通常以异步方式执行在线程池线程上而不是以同步方式在主应用程序线程,可以使用 Status 属性,以及 IsCanceled, ,IsCompleted, ,和 IsFaulted 属性,以确..._.net task

css响应式网页设计:自适应屏幕宽度、移动页面开发技巧_响应式 自适应大小 css-程序员宅基地

文章浏览阅读1.4w次,点赞7次,收藏56次。html响应式网页设计:自动适应屏幕宽度背景移动设备正超过桌面设备,成为访问互联网的最常见终端。于是,网页设计师不得不面对一个难题:如何才能在不同大小的设备上呈现同样的网页?手机的屏幕比较小,宽度通常在600像素以下;PC的屏幕宽度,一般都在1000像素以上(目前主流宽度是1366×768),有的还达到了2000像素。同样的内容,要在大小迥异的屏幕上,都呈现出满意的效果,并不是一件容易的事。..._响应式 自适应大小 css

Pandas基础操作2——DataFrame的基础操作_data=nr-程序员宅基地

文章浏览阅读257次。紧接着上一篇博客,创建了Series跟DataFrame今天学习DataFrame的行列添加和删除操作,以及append和切片操作下面看代码:import numpy as npimport pandas as pdfrom pandas import Series, DataFrame# Seriess = Series([1, 2, 3, 4], index=['a', 'b', 'c', 'd'])print(s)# >>># a 1# b _data=nr