A. 散列表的平均查找长度怎么计算
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1，2，3，…，n)，可以简单以数学上的期望来这么理解。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。
在查找表中查找不到待查元素，但是找到待查元素应该在表中存在的位置的平均查找次数称为查找不成功时的平均查找长度，不成功。
(1)散列存储的地址取多少扩展阅读
散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。
查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：
1、散列函数是否均匀；
2、处理冲突的方法；
3、散列表的装填因子。
散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。
参考资料来源：网络-平均查找长度
参考资料来源：网络-散列表
B. 哈希表详解
哈希表：即散列存储结构。
散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。
这样，不经过比较，一次存取就能得到所查元素的查找方法
优点：查找速度极快（O(1)）,查找效率与元素个数n无关！
哈希方法(杂凑法)
选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。
哈希函数(杂凑函数)
哈希方法中使用的转换函数称为哈希函数(杂凑函数).在记录的关键码与记录的存储地址之间建立的一种对应关系
有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k ， H(k)称为散列函数,画出存储结构图。
根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，
根据存储时用到的散列函数H(k)表达式，迅即可查到结果！
例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；
若查不到，应当设法返回一个特殊值，例如空指针或空记录。
很显然这种搜索方式空间效率过低。
哈希函数可写成：addr(ai)=H(ki)
选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数(杂凑函数).在记录的关键码与记录的存储地址之间建立的一种对应关系。
通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。
有6个元素的关键码分别为：（14，23，39，9，25，11）。
选取关键码与元素位置间的函数为H(k)=k mod 7
根据哈希函数算出来发现同一个地址放了多个关键码，也就是冲突了。
在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。
所以，哈希方法必须解决以下两个问题：
1）构造好的哈希函数
（a）所选函数尽可能简单，以便提高转换速度；
（b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。
2）制定一个好的解决冲突的方案
查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。
从上面两个例子可以得出如下结论：
哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落在表长允许的范围之内即可
冲突：key1≠key2，但H(key1)=H(key2)
同义词：具有相同函数值的两个关键码
哈希函数冲突不可避免，只能尽量减少。所以，哈希方法解决两个问题：
构造好的哈希函数；
制定解决冲突基本要求：
要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
Hash(key) = a·key + b (a、b为常数)
优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.
缺点：要占用连续地址空间，空间效率低。
例.关键码集合为{100，300，500，700，800，900}，
选取哈希函数为Hash(key)=key/100，
则存储结构（哈希表）如下：
Hash(key)=key mod p (p是一个整数)
特点：以关键码除以p的余数作为哈希地址。
关键：如何选取合适的p？p选的不好，容易产生同义词
技巧：若设计的哈希表长为m，则一般取p≤m且为质数
（也可以是合数，但不能包含小于20的质因子）。
Hash(key)= ⎣ B ( A key mod 1 ) ⎦
(A、B均为常数，且0<A<1，B为整数)
特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。
例：欲以学号最后两位作为地址，则哈希函数应为：
H(k)=100 (0.01 k % 1 )
其实也可以用法2实现： H(k)=k % 100
特点：选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。
例：有一组（例如80个）关键码，其样式如下：
讨论：
① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。
② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。
特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。(适于不知道全部关键码情况)
理由：因为中间几位与数据的每一位都相关。
例：2589的平方值为6702921，可以取中间的029为地址。
特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
适用于：关键码位数很多,且每一位上各符号出现概率大致相同的情况。
法1：移位法 ── 将各部分的最后一位对齐相加。
法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。
例：元素42751896,
用法1： 427＋518＋96=1041
用法2： 427 518 96—> 724+518+69 =1311
7、随机数法
Hash(key) = random ( key ) (random为伪随机函数)
适用于：关键字长度不等的情况。造表和查找都很方便。
小结：构造哈希函数的原则：
① 执行速度（即计算哈希函数所需时间）；
② 关键字的长度；
③ 哈希表的大小；
④ 关键字的分布情况；
⑤ 查找频率。
设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。
1）线性探测法
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中：
Hash(key)为哈希函数
m为哈希表长度
di 为增量序列 1，2，…m-1，且di=i
关键码集为 {47，7，29，11，16，92，22，8，3}，
设：哈希表表长为m=11；
哈希函数为Hash(key)=key mod 11；
拟用线性探测法处理冲突。建哈希表如下：
解释：
① 47、7是由哈希函数得到的没有冲突的哈希地址；
② Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入。
③ 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。
其中3 还连续移动了（二次聚集）
线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；
线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，
因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。
解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。
2） 二次探测法
仍举上例，改用二次探测法处理冲突，建表如下：
Hi=(Hash(key)±di) mod m
其中：Hash(key)为哈希函数
m为哈希表长度，m要求是某个4k+3的质数；
di为增量序列 1^2，-1 ^2，2 ^2，-2 ^2，…，q ^2
注：只有3这个关键码的冲突处理与上例不同，
Hash(3)=3，哈希地址上冲突，由
H1=(Hash(3)+1 ^2) mod 11=4，仍然冲突；
H2=(Hash(3)-1 ^2) mod 11=2，找到空的哈希地址，存入。
3） 若di＝伪随机序列，就称为伪随机探测法
基本思想：将具有相同哈希地址的记录(所有关键码为同义词)链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：
Hash(key)=key mod 11，
用拉链法处理冲突，则建表如图所示。
Hi=RHi(key) i=1, 2, …，k
RHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。
优点：不易产生聚集；
缺点：增加了计算时间。
思路：除设立哈希基本表外，另设立一个溢出向量表。
所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。
明确：散列函数没有“万能”通式（杂凑法），要根据元素集合的特性而分别构造。
讨论：哈希查找的速度是否为真正的O（1）？
不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。
一般地，ASL依赖于哈希表的装填因子α,它标志着哈希表的装满程度。
0≤α≤1
α 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。
例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，
设每个记录的查找概率相等
(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m
(2) 用二次探测再散列处理冲突，即Hi=(H(key)+di) MOD m
(3) 用链地址法处理冲突
1） 散列存储的查找效率到底是多少？
答：ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)
2）“冲突”是不是特别讨厌？
答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。
利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。
C. 关于散列表，散列函数的两个问题。
散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。设计合理的散列函数可以集成链表和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：
散列表的主要特点：
将输入映射到数字
2.不同的输入产生不同的输出
3.相同的输入产生相同的输出
4. 当填装因子超过阈值时，能自动扩展。填装因子 = 散列表包含的元素数 / 位置总数，当填装因子 =1，即散列表满的时候，就需要调整散列表的长度，自动扩展的方式是：申请一块旧存储容量 X 扩容系数的新内存地址，然后把原内存地址的值通过其中的 key 再次使用 hash 函数计算存储位置，拷贝到新申请的地址。
5. 值呈均匀分布。这里的均匀指水平方向的，即数组维度的。如果多个值被映射到同一个位置，就产生了冲突，需要用链表来存储多个冲突的键值。极端情况是极限冲突，这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将变为最差的 O(n)，如果水平方向填充因子很小，但某些节点下的链表又很长，那值的均匀性就比较差。
D. 散列储存（hash储存）的理解
设要存储对象的个数为num, 那么我们就用len个内存单元来存储它们(len>=num); 以每个对象ki的关键字为自变量，用一个函数h(ki)来映射出ki的内存地址，也就是ki的下标，将ki对象的元素内容全部存入这个地址中就行了。这个就是Hash的基本思路。
为什么要用一个函数来映射出它们的地址单元呢？
假设现在我要存储 4个元素 13 7 14 11
显然，我们可以用 数组 来存。也就是： a[1] = 13; a[2] = 7; a[3] = 14; a[4] = 11 ;
当然，我们也可以用Hash来存。下面给出一个简单的 Hash存储 ：
先来确定那个函数。我们就用 h(ki) = ki%5 ;
对于第一个元素 h(13) = 13%5 = 3 ; 也就是说 13 的下标为 3 ；即 Hash[3] = 13 ;
对于第二个元素 h(7) = 7 % 5 = 2 ; 也就是说誉橡 7 的下标为 2 ; 即 Hash[2] = 7 ;
同理， Hash[4] = 14; Hash[1] = 11 ;
现在我要你查找 11 这个元素是否存在。你会怎么做呢？当然，对于数组来说，那是相当的简单，一个for循环就可以辩虚御了。
也就是说我们要找4次。
下面我们来用Hash找一下。
首先，我们携岩将要找的元素 11 代入刚才的函数中来映射出它所在的地址单元。也就是 h(11) = 11%5 = 1 了。下面我们来比较一下 Hash[1]?=11 , 这个问题就很简单了。也就是说我们就找了1次。这个就是Hash的妙处了，通过制定一个规则（函数）来映射出它的地址，数据也就能通过这个规则去找到它的内存地址了。
E. 数据结构的存储方式有哪几种
数据结构的存储方式有顺序存储方法、链接存储方法、索引存储方法和散列存储方法这四种。
1、顺序存储方式：顺序存储方式就是在一块连续的存储区域一个接着一个的存放数据，把逻辑上相连的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接挂安息来体现。顺序存储方式也称为顺序存储结构，一般采用数组或者结构数组来描述。
2、链接存储方法：它比较灵活，其不要求逻辑上相邻的结点在物理位置上相邻，结点间的逻辑关系由附加的引用字段表示。一个结点的引用字段往往指导下一个结点的存放位置。链接存储方式也称为链接式存储结构，一般在原数据项中增加应用类型来表示结点之间的位置关系。
3、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。它细分为两类：稠密索引：每个结点在索引表中都有一个索引项，索引项的地址指示结点所在的的存储位置；稀疏索引：一组结点在索引表中只对应一个索引项，索引项的地址指示一组结点的起始存储位置。
4、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
(5)散列存储的地址取多少扩展阅读
顺序存储和链接存储的基本原理
在顺序存储中，每个存储空间含有所存元素本身的信息，元素之间的逻辑关系是通过数组下标位置简单计算出来的线性表的顺序存储，若一个元素存储在对应数组中的下标位置为i，则它的前驱元素在对应数组中的下标位置为i-1，它的后继元素在对应数组中的下标位置为i+1。
在链式存储结构中，存储结点不仅含有所存元素本身的信息，还含有元素之间逻辑关系的信息。数据的链式存储结构可用链接表来表示。其中data表示值域，用来存储节点的数值部分。Pl，p2，…，Pill(1n≥1)均为指针域，每个指针域为其对应的后继元素或前驱元素所在结点的存储位置。
在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到，访问任一元素的时间与该元素结点在链式存储结构中的位置有关。
F. 数据结构 哈希表建立
国防部和发短信