下载文档原格式
数据结构实验报告班级：姓名：学号：时间：一、题目散列表的设计二、要求1、问题描述针对某个集体中人名设计一个散列表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
2、基本要求假设人名为中国人姓名的汉语拼音形式，待填入散列表的人名共有30个，取平均查找长度上限为2。
散列函数用除留余数法构造，用伪随机探测再散列法处理冲突3、测试数据取读者周围较熟悉的30人的姓名。
4、实现提示如果随机函数自行构造，则应首先调整好随机函数，使其发布均匀。
人名的长度不超过20个字符。
可先对过长的人名作折叠处理。
三、设计思想1、散列函数的构造方法：散列列函数的构造方法有四种：平方取中法、除余法、相乘取整法、随机数法。
这里用了除余法，该方法是最为简单常用的一种方法。
它是以表长m来除关键字，取其余数作为散列地址，即 h(key)=key％m该方法的关键是选取m。
选取的m应使得散列函数值尽可能与关键字的各位相关。
m最好为素数。
【例】若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。
于是高位不同而低位相同的关键字均互为同义词。
【例】若关键字是十进制整数，其基为10，则当m=100时，159，259，359，…，等均互为同义词。
2、冲突的处理：（1）冲突两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。
该现象称为冲突(Collision)或碰撞。
发生冲突的两个关键字称为该散列函数的同义词(Synonym)。
（2）安全避免冲突的条件最理想的解决冲突的方法是安全避免冲突。
要做到这一点必须满足两个条件：①其一是|U|≤m②其二是选择合适的散列函数。
这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。
（3）冲突不可能完全避免通常情况下，h是一个压缩映像。
虽然|K|≤m，但|U|> m，故无论怎样设计h，也不可能完全避免冲突。
因此，只能在设计h时尽可能使冲突最少。
哈希散列值哈希散列值是计算机科学中常用的一种数据结构，它能将任意长度的数据映射为固定长度的散列值。
通过哈希散列值，我们可以快速地查找和比较数据，以提高程序的效率和安全性。
本文将重点探讨哈希散列值的原理、具体操作方法和实践导向结论。
一、哈希散列值的原理哈希散列值的原理基于哈希函数的构造和散列算法的设计。
哈希函数是一种将输入映射到固定大小输出的函数。
它应具备以下两个特点：1. 确定性：对于相同的输入，哈希函数应始终返回相同的输出。
2. 均匀性：哈希函数应能将不同的输入均匀地映射到输出空间。
散列算法是通过哈希函数将数据映射为散列值的过程。
常用的散列算法有MD5、SHA-1、SHA-256等。
这些算法通过复杂的数学运算和位操作，将输入的数据转化为固定长度的散列值。
二、具体操作方法1. 选择合适的哈希函数：在实际应用中，我们需要根据数据的特点选择合适的哈希函数。
例如，对于字符串数据，常用的哈希函数有BKDRHash、APHash等。
2. 设计合理的散列算法：在选择哈希函数的基础上，我们还需要设计合理的散列算法。
常见的散列算法包括链地址法、开放地址法等。
3. 处理冲突：由于散列值的长度是有限的，不同的输入可能会产生相同的散列值，即冲突。
解决冲突的方法包括拉链法、线性探测法等。
三、实践导向结论通过哈希散列值，我们可以实现以下应用：1. 数据索引：哈希散列值可以作为数据的索引，通过散列值快速查找数据，提高查找效率。
例如，在数据库中，可以通过哈希散列值加速对数据的检索。
2. 数据完整性验证：通过对数据进行哈希散列，可以生成一个唯一的散列值，用于验证数据的完整性。
例如，在文件传输过程中，可以通过比较文件的散列值判断文件是否被篡改。
3. 密码存储：在用户登录认证等场景中，通常不会将密码明文存储在数据库中，而是将密码的哈希散列值存储，提高密码的安全性。
4. 分布式存储：在分布式系统中，通过哈希散列值可以将数据分布到不同的节点上，实现负载均衡和数据冗余。
散列表（哈希表）散列表（哈希表）散列表是根据键(KEY)来直接访问内存存储位置的⼀种数据结构，它通过散列函数计算键值对中键(KEY)的散列地址，然后将值存在此地址上，这样就可以直接根据键来取得所对应的值。
散列函数的冲突对于不同的键(KEY)，散列函数得到同⼀个散列地址，这种现象称为冲突。
如何处理散列冲突开放定址法线性探测法：就是⼀旦冲突了就放到下⼀个位置就好了，只要存储空间够⼤总会有位置放的（但是这样会产⽣堆积，因为他可能会把其他的原来属于别⼈的位置只是暂时空着的给占了）⼆次探测法：冲突了就放在1或者2或者3等等的平⽅后的位置，⽽不是像前⾯那样就是单纯的不停地加1，这样就可以不让关键字对集中在⼀块地⽅伪随机探测法：⽤⼀个种⼦产⽣⼀个随机数来作为位移量来避免冲突，然后最后查找这个数在不在的时候也⽤这个种⼦⽣成随机数来找当散列表存在"堆积"(在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块)的情况时，使⽤开放定址法的效率⼤⼤降低，此时不能再使⽤开放定址法单链表法：将散列地址值⼀样的键值对保存在⼀个链表中。
再散列：在上次散列计算发⽣冲突时，利⽤该次冲突的散列函数地址产⽣新的散列函数地址，直到冲突不再发⽣。
这种⽅法不易产⽣"堆积"，但增加了计算时间。
公共溢出区：将所有冲突的键值对放在⼀个数组中。
查找时如果在散列表中没有找到就在数组中顺序查找。
散列表的查找效率在理想情况下，散列表建⽴过程中没有出现冲突，那么在散列表中查找的效率则为O(1)。
但是这仅是理想情况，散列冲突会影响查找效率，那么影响查找效率的因素就是影响产⽣冲突的因素：散列函数是否均匀（均匀散列函数是指对于键值对中任意⼀个键(KEY)经过散列函数得到任意⼀个地址的概率是相等的）处理散列冲突的⽅法散列表的载荷因⼦其中散列表的载荷因⼦计算公式为α = 表中元素个数/表长度α越⼤，产⽣冲突的可能性就越⼤。
数据结构中的散列算法详解散列算法（Hashing Algorithm）是数据结构中一种常用的技术，可以提高数据的查找效率。
它将数据映射到一个固定大小的数组中，通过散列函数得到数组的索引位置，从而快速定位数据。
一、什么是散列算法散列算法是一种通过将输入数据映射到固定大小的数组中，从而实现快速访问的技术。
它利用散列函数将输入数据转换为一个整数值，并将该值与数组的大小取模，得到数组的索引位置。
将数据存储在对应索引的数组位置上，称为散列存储。
散列算法有很多种，常见的包括直接定址法、平方取中法、除留余数法等。
每一种散列算法都有自己的特点和适用场景。
二、散列函数的选择散列函数的选择非常重要，它直接关系到散列算法的效率和数据的分布。
一个好的散列函数应该具备以下特点：1. 易于计算：散列函数应该具备高效的计算性能，能够在短时间内完成散列计算。
2. 分布均匀：散列函数应能够将输入数据均匀地映射到散列表的各个位置上，避免出现数据聚集的情况。
3. 最小冲突：散列函数应该尽可能减少冲突，即不同的输入值映射到相同的索引位置的情况。
三、散列算法的实现散列算法的实现主要分为两个步骤：散列函数的设计和冲突处理。
散列函数的设计是散列算法的核心。
常见的散列函数设计方法有：直接定址法、除留余数法、平方取中法、伪随机数法等。
根据不同的数据特点和应用场景，选择合适的散列函数。
冲突处理是指当多个数据映射到相同的索引位置时，如何解决冲突的问题。
常见的冲突处理方法有：开放定址法、链地址法、再散列法等。
不同的冲突处理方法有不同的优势和适用场景，可以根据具体情况选择合适的方法。
四、散列算法的应用散列算法在实际应用中被广泛使用，主要用于提高数据的查找、插入和删除效率。
以下是散列算法的几个典型应用场景：1. 数据库索引：散列算法可用于构建数据库中的索引，加快数据的检索速度。
2. 缓存管理：散列算法可用于缓存的管理，快速找到对应的缓存数据。
3. 字典查找：散列算法可用于字典的查找，通过散列存储可以高效地实现快速查找。
Python数据结构——散列表散列表的实现常常叫做散列(hashing)。
散列仅⽀持INSERT,SEARCH和DELETE操作，都是在常数平均时间执⾏的。
需要元素间任何排序信息的操作将不会得到有效的⽀持。
散列表是普通数组概念的推⼴。
如果空间允许，可以提供⼀个数组，为每个可能的关键字保留⼀个位置，就可以运⽤直接寻址技术。
当实际存储的关键字⽐可能的关键字总数较⼩时，采⽤散列表就⽐较直接寻址更为有效。
在散列表中，不是直接把关键字⽤作数组下标，⽽是根据关键字计算出下标，这种关键字与下标之间的映射就叫做散列函数。
1.散列函数⼀个好的散列函数应满⾜简单移植散列的假设：每个关键字都等可能的散列到m个槽位的任何⼀个中去，并与其它的关键字已被散列到哪个槽位⽆关。
1.1 通常散列表的关键字都是⾃然数。
1.11 除法散列法通过关键字k除以槽位m的余数来映射到某个槽位中。
hash(k)=k mod m应⽤除法散列时，应注意m的选择，m不应该是2的幂，通常选择与2的幂不太接近的质数。
1.12 乘法散列法乘法⽅法包含两个步骤，第⼀步⽤关键字k乘上常数A(0<A<1),并取出⼩数部分，然后⽤m乘以这个值，再取结果的底(floor)。
hash(k)=floor(m(kA mod 1))乘法的⼀个优点是对m的选择没有什么特别的要求，⼀般选择它为2的某个幂。
⼀般取A=(√5-1)/2=0.618⽐较理想。
1.13 全域散列随机的选择散列函数，使之独⽴于要存储的关键字。
在执⾏开始时，就从⼀族仔细设计的函数中，随机的选择⼀个作为散列函数，随机化保证了没有哪⼀种输⼊会始终导致最坏情况发⽣。
1.2 如果关键字是字符串，散列函数需要仔细的选择1.2.1 将字符串中字符的ASCII码值相加def _hash(key,m):hashVal=0for _ in key:hashVal+=ord(_)return hashVal%m由于ascii码最⼤127，当表很⼤时，函数不会很好的分配关键字。
