数据结构与算法（Java语言版）课件 第10章 散列表与HashMap类

第10章散列表与HashMap类2024/11/9110.1散列结构的特点2024/11/92生活中有些数据之间可能是密切相关的一对，例如，一副手套，一双鞋子，一对夫妻等，即数据的逻辑结构是成对的，即不是线性也不是树形结构，一对数据与另一对数据之间也无须有必然的关系。如何存储这样的数据对，也是数据结构非常关心的，以下要介绍的散列结构，就是存储“数据对”的最重用的手段之一.2024/11/9310.1散列结构的特点●散列结构与散列表数据对，也称作"键-值"对，键和值都是某种类的实例，即对象。叙述时可以把这"键-值"对记作(key,value)，称key是关键字、value是键值或值。散列结构使用两个集合存储对象，一个集合称作关键字集合，记作Key。另一个是值的集合，记作Value。Key集合中的节点（或称元素）负责存储关键字，所有关键字对应的全部值称作散列结构的值集合，记作Value，即Value中的节点负责存储值。称Value为散列结构中的散列表（hash表，也常常被音译称作哈希表）。简单说，散列结构是根据关键字直接进行访问数据的数据结构，其核心思想是使用散列函数（hash()函数）把关键字映射到散列表中一个位置，即映射到散列表中的某个节点。2024/11/9410.1散列结构的特点●散列结构与散列表hash()函数本质上就是集合Key到整数集合

2024/11/9510.1散列结构的特点●散列结构与散列表对于一个关键字，比如key1，如果hash(key1)=98，那么key1关键字对应的节点就是数组hashValue第98个元素，即hashValue[98]。2024/11/9610.1散列结构的特点●散列结构与散列表一个散列函数，即hash()函数需保证下列两点：①

对于不同的关键字，比如，key1，key2是Key中两个节点，即两个关键字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是两个不同的节点。但节点中的对象可能是相同的（数组的两个不同的元素中的值可能是相同的）。②为了保证第①点，让hash()函数映射出的全部节点，分散地分布在一块连续的内存中，这也是人们把Value称作一个散列表的原因。由于散列表中的节点是随机、分散分布的，所以我们不在散列表上定义任何关系（见第1章）。散列表或散列二字不是指数据之间的关系，而是形容存储形式的特点（hash()函数映射存储位置）。如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。2024/11/9710.1散列结构的特点●散列结构与散列表如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。可以用链接法解决冲突，散列函数把和关键字key有相同对应的值的那些关键字所对应的存储位置依次设置为一个链表的中不同的节点（链表头节点是key对应的存储位置），这样一来，就会增大查询Value中值的时间复杂度。如果散列函数设计的合理，那么一般不会发生关键字冲突或发生关键字冲突的概率非常小，因此也就不需要使用链式方法解决冲突或使用链式方法解决冲突的概率很小。链接法是最后保证不同关键字对应的不同节点（不同的存储位置）的最后办法。2024/11/9810.1散列结构的特点●查找、添加、删除的特点由散列结构的特点可以知道，使用关键字查找、删除、添加Value中的节点，时间复杂度通常都是

（如果关键字冲突，使用了链接法）散列结构具有数组的优点，即非常快的查询速度，同时又将查询数据（Value）的索引分离到另一个独立的集合中（Key）。数组最大的缺点就是将索引（下标）和数组元素绑定，因此，一旦创建数组，就无法更改索引，即无法再改变数组的长度。而散列结构可以随时添加一个“键-值”对（一个关键字，一个相应的值），或删除一个“键-值”对。10.2简单的散列函数2024/11/99通过简单的例子：停车场，进一步理解散列结构，后面我们将使用Java的HashMap类实现的散列结构。2024/11/91010.2简单的散列函数●顺序扩建停车位当Value中节点的数目越来越多时，比如达到总内存大小的一半时，就要重新调整内存，即分配新的数组，并把原数组hashValue[]的值复制到新的数组中，新的数组成为Value的新的一块连续内存。汽车停车场（模拟散列表）初始状态有10个连续的车位，相当于散列结构中分配给散列表Value的一块连续的内存空间（数组的长度是10）。假设汽车的车牌号是3位数的正整数，相当于散列结构中的Key集合中节点里的关键字。停车场可以根据需要，随时顺序地扩大停车场，即连续地扩建停车位。

2024/11/91110.2简单的散列函数●顺序扩建停车位

2024/11/91210.2简单的散列函数●顺序扩建停车位每当一辆车来到停车场，如果用散列函数计算了若干次，得到的车位号对应的车位上都是已经停放了车辆，这个时候，就扩建停车场、让其容量增加2倍，然后再用散列函数计算车位号……，如此这般，只要内存足够大，总能找到停车位，如图所示意。由于用散列函数的算法是随机的，所以，某个时刻以后，扩建停车场的概率就很小了。2024/11/91310.2简单的散列函数●链式扩展停车位当用散列函数计算出同样的车位数时，比如都是9，就把二者的停车位分别指定为同一个链表中的不同的两个节点，链表的头节点是数组的第9个元素。2024/11/91410.2简单的散列函数例子1Key.javaExample10_1.java例子1中的ParkingOne类使用顺序办法增加停车场的车位，ParkingTwo类使用链式办法增加停车场的车位。Car.javaParkingOne.javaParkingTwo.java例子1中的主类Example10_1模拟了两个停车场的停车情况。10.3HashMap类2024/11/915HashMap<K,V>泛型类继承Map泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了Map泛型接口中的抽象方法。HashMap<K,V>泛型类的对象为散列表,散列表的Key集合是实现Set接口的一个实例，Key集合中不允许有两个结点中的对象相同，即大小一样的两个结点，Key中不同的key对应的Value中的节点是不同的，但Value中的节点中的对象，即数据可以是相同的，就像数组的不同元素（节点）里可以存放相同的数据。HashMap<K,V>泛型类提供的添加、删除、查找等操作的时间复杂度都是O(1).2024/11/91610.3HasMap类HashMap<K,V>泛型类直接实现了Map接口，注意，没有实现SortedMap接口。2024/11/91710.3HasMap类例子2Example10_2.java声明一个HashMap<K,V>泛型类的对象，即散列表，必须要指定Key和Value的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定Key中节点里的对象的类型和Value中节点里的对象的类型。例如，指定K是String类型、V是Car类型，例如：HashMap<String,Car>hashMap=newHashMap<>();或HashMap<String,Car>hashMap=newHashMap<String,Car>();Car.java例子2中的主类Example10_2中首先创建一个空散列表hashMapOne，然后向散列表hashMapOne添加4个”键-值”对，随后再用hashMapOne创建另一个散列表hashMapTwo。10.4散列表的基本操作2024/11/918publicVput(Kkey,Vvalue)向散列表添加”键-值”对，即将key存储在Key中，把value放置在Value中，如果添加成功返回null。需要注意的是，如果散列表Key中已经有了键key，那么当前添加的”键-值”对将替换已存在的”键-值”对，并返回旧”键-值”对中的value值，即返回被替换的”键-值”对的值。publicVputIfAbsent(Kkey,Vvalue)如果散列表Key中没有key，则添加该键值对(key,value)到散列表，并返回null，如果散列表Key中已经有键key，则返回旧key对应的value(不做添加操作)。10.4散列表的基本操作2024/11/919publicVget(Objectkey)返回”键-值”对(key,value)中的value，如果key不在集合Key中，方法返回null。publicbooleancontainsKey(Objectkey)判断Key中是否有关键字key，有返回true，否则返回false。publicbooleancontainsValue(Objectvalue)判断Value中是否有value，有返回true，否则返回false。publicbooleanisEmpty()如果散列表中没有任何"键-值"对，则返回true，否则返回false。10.4散列表的基本操作2024/11/920publicVremove(Objectkey)删除关键字key组合的”键-值”对(key,value)，并返回value。publicVreplace(Kkey,Vvalue)如果散列表Key已有key，就用(key,value)替换已有的key组合的”键-值”对，并返回替换后的value，如果Key中没有关键字key，不进行替换操作，并返回null。publicvoidclear()删除散列表的全部”键-值”对。2024/11/92110.4散列表的基本操作例子3Example10_3.java例子3的主类Example10_3使用了HashMap<K,V>泛型类的一些常用方法。10.5遍历散列表2024/11/922publicvoidforEach(BiConsumer<?superK,?superV>action)对散列表中的所有(key,value)执行给定的action操作，直到所有(key,value)对都被处理或操作引发异常。BiConsumer是一个函数接口，该接口里的抽象方法是voidaccept(Kk,Vv)。使用forEach()方法时将一个Lambda表达式传递给action，例如：（k,v）->{System.out.println(v);}。forEach()方法将Lambda表达式中的k,v，依次取散列表中的(key,value)。2024/11/92310.5遍历散列表例子4Example10_4.java例子4的主类Example10_4将正整数和正整数的平方根（最多保留3位小数）作为(key,value)存放在一个散列表中，然后遍历散列表。10.6散列表与字符、单词频率2024/11/924●每次读取文件的一个字符，如果是字母，并且散列表中还没有(key,value)：(字母,次数)，散列表就添加(key,value)：(字母，次数)，如果散列表中已经有(key,value)：(字母，次数)，就更新该(key,value)：(字母，次数)，将其次数增加1。●每次读取文件的一个单词，如果散列表中还没有(key,value)：(单词，次数)，散列表就添加(key,value)：(单词，次数)，如果散列表中已经有(key,value)：(单词，次数)，就更新该(key,value)：(单词，次数)，将其次数增加1。2024/11/92510.6散列表与字符、单词频率例子5LettersFrequency.java例子5中的LettersFrequency类负责统计文本文件中字符出现的次数和频率，WordsFrequency负责统计文本文件中单词出现的次数和频率。WordsFrequency.javaExample10_5.java例子5中Example10_5.java中的主类Example10_5使用LettersFrequency类统计了Example10_5.java里字母出现的次数和频率，另外一个主类MainClass使用WordsFrequency统计了Example10_5.java里单词出现的次数和频率。10.7散列表与单件模式2024/11/926●单件模式

保证一个类仅有一个实例，并提供一个访问它的全局访问点。散列表可以用来存储已知的数据，在后续的操作中，通过散列表查找是否已经存在，从而实现唯一性验证的功能。因此在实现的具体代码中可以借助散列表来实现单件模式。2024/11/92710.7散列表与单件模式例子6SingletonSun.javaExample10_6.java例子6中的SingletonSun类实现了单件模式，SingletonSun类只能创建一个“太阳”。在例子6中，SingletonSun类中的getInstance()方法检查散列表中是否已经存在当前类的实例对象，如果不存在则创建一个新的，然后将其存储到散列表中，并返回该实例。这样就保证了SingletonSun类在整个程序中只能创建它的一个对象。10.8散列表与数据缓存2024/11/928

2024/11/92910.8散列表与数据缓存例子7Hash.javaExample10_7.java例子7中的Hash类将频繁使用的阶乘放在散列表中(用到第3章例子3中的SumMulti类)10.9TreeMap类2024/11/93010.9TreeMap类2024/11/931在类的层次上，TreeMap<K,V>泛型类HashMap<K,V>泛型类不同，HashMap<K,V>泛型类直接实现Map接口，TreeMap<K,V>泛型类不是直接实现Map接口，而是实现NavigableMap接口，该接口又是SortedMap的子接口，SortedMap接口又是Map的子接口，如图前图。称TreeMap<K,V>泛型类的实例或创建的对象是一个映射树。10.9TreeMap类2024/11/932在存储数据上，TreeMap<K,V>泛型类和HashMap<K,V>泛型类似，映射树也是存储"键-值"对，但映射树不是散列结构。映射树也是使用两个集合存储对象，一个集合称作关键字集合，记作Key。另一个是值的集合，记作Value。TreeMap<K,V>的Key集合也是实现Set接口的一个实例，映射树中按着Key集合中的关键字的大小关系，将关键字key对应的value，存放在一个红黑树（平衡二叉搜索树，见第9章）上，即映射树的Value是一棵红黑树，这也是TreeMap<K,V>类名的来历。10.9TreeMap类2024/11/933

2024/11/93410.9TreeMap类TreeMap中的Value是红黑树，是按着Key中的关键字的大小关系排序的，这就意味着Value红黑树上可以有相同的对象，即可以有两个结点中的对象是相同的，甚至，所有结点中的对象都可以是相同的。

2024/11/93510.9TreeMap类例子8Example10_8.java例子8中，主类Example10_8使用了TreeMap的一些常用方法。2024/11/93610.9TreeMap类例子9Example10_9.java例子9的主类Example10_9获取的映射树的视图，查询了视图中的”键-值”对，并对视图进行更新操作。2024/11/93710.9TreeMap类