第11章 集合HashSet类教学课件.pptx

第10章散列表与HashMap类2024/9/101

10.1散列结构的特点2024/9/102生活中有些数据之间可能是密切相关的一对，例如，一副手套，一双鞋子，一对夫妻等，即数据的逻辑结构是成对的，即不是线性也不是树形结构，一对数据与另一对数据之间也无须有必然的关系。如何存储这样的数据对，也是数据结构非常关心的，以下要介绍的散列结构，就是存储“数据对”的最重用的手段之一.

2024/9/10310.1散列结构的特点●散列结构与散列表数据对，也称作键-值对，键和值都是某种类的实例，即对象。叙述时可以把这键-值对记作(key,value)，称key是关键字、value是键值或值。散列结构使用两个集合存储对象，一个集合称作关键字集合，记作Key。另一个是值的集合，记作Value。Key集合中的节点（或称元素）负责存储关键字，所有关键字对应的全部值称作散列结构的值集合，记作Value，即Value中的节点负责存储值。称Value为散列结构中的散列表（hash表，也常常被音译称作哈希表）。简单说，散列结构是根据关键字直接进行访问数据的数据结构，其核心思想是使用散列函数（hash()函数）把关键字映射到散列表中一个位置，即映射到散列表中的某个节点。

2024/9/10410.1散列结构的特点●散列结构与散列表hash()函数本质上就是集合Key到整数集合????

2024/9/10510.1散列结构的特点●散列结构与散列表对于一个关键字，比如key1，如果hash(key1)=98，那么key1关键字对应的节点就是数组hashValue第98个元素，即hashValue[98]。

2024/9/10610.1散列结构的特点●散列结构与散列表一个散列函数，即hash()函数需保证下列两点：①对于不同的关键字，比如，key1，key2是Key中两个节点，即两个关键字，一定有hash(key1)不等于hash(key2)，即hash(key1)和hash(key2)是两个不同的节点。但节点中的对象可能是相同的（数组的两个不同的元素中的值可能是相同的）。②为了保证第①点，让hash()函数映射出的全部节点，分散地分布在一块连续的内存中，这也是人们把Value称作一个散列表的原因。由于散列表中的节点是随机、分散分布的，所以我们不在散列表上定义任何关系（见第1章）。散列表或散列二字不是指数据之间的关系，而是形容存储形式的特点（hash()函数映射存储位置）。如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。

2024/9/10710.1散列结构的特点●散列结构与散列表如果出现hash(key1)和hash(key2)相同，就称关键字有冲突。散列算法就是研究如何避免冲突或减少冲突的可能性，以及在冲突不可避免时能给出解决的问题的算法。可以用链接法解决冲突，散列函数把和关键字key有相同对应的值的那些关键字所对应的存储位置依次设置为一个链表的中不同的节点（链表头节点是key对应的存储位置），这样一来，就会增大查询Value中值的时间复杂度。如果散列函数设计的合理，那么一般不会发生关键字冲突或发生关键字冲突的概率非常小，因此也就不需要使用链式方法解决冲突或使用链式方法解决冲突的概率很小。链接法是最后保证不同关键字对应的不同节点（不同的存储位置）的最后办法。

2024/9/10810.1散列结构的特点●查找、添加、删除的特点由散列结构的特点可以知道，使用关键字查找、删除、添加Value中的节点，时间复杂度通常都是?（如果关键字冲突，使用了链接法）散列结构具有数组的优点，即非常快的查询速度，同时又将查询数据（Value）的索引分离到另一个独立的集合中（Key）。数组最大的缺点就是将索引（下标）和数组元素绑定，因此，一旦创建数组，就无法更改索引，即无法再改变数组的长度。而散列结构可以随时添加一个“键-值”对（一个关键字，一个相应的值），或删除一个“键-值”对。

10.2简单的散列函数2024/9/109通过简单的例子：停车场，进一步理解散列结构，后面我们将使用Java的HashMap类实现的散列结构。

2024/9/101010.2简单的散列函数●顺序扩建停车位当Value中节点的数目越来越多时，比如达到总内存大小的一半时，就要重新调整内存，即分配新的数组，并把原数组hashValue[]的值复制到新的数组中，新的数组成为Value的新的一块连续内存。汽车停车场（模拟散列表）初始状态有10个连续的车位，相当于散列结构中分配给散列表Value的一块连续的内存空间（数组的长度是10）。假设汽车的车牌号是3位数的正整数，相当于散列结构中的