哈希表详解

哈希表：即散列存储结构。

散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。

这样，不经过比较，一次存取就能得到所查元素的查找方法

优点：查找速度极快（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）“冲突”是不是特别讨厌？

答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。

利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。

md5值为什么不可逆？

大学里“资讯保安”学些什么内容？

资讯保安专业课程设定：

在校期间，不仅强调学生对基础知识的掌握，更强调对其专业素质和能力的培养。学生除学习理工专业公共基础课外，学习的专业基础和专业课主要有：高等数学、线性代数、计算方法、概率论与数理统计、计算机与演算法初步、C++语言程式设计、资料结构与演算法、计算机原理与组合语言、资料库原理、作业系统、大学物理、集合与图论、代数与逻辑、密码学原理、编码理论、资讯理论基础、资讯保安体系结构、软体工程、数字逻辑、计算机网路等。

除上述专业课外还开设了大量专业选修课，主要有：资料通讯原理、资讯保安概论、计算机网路安全管理、数字鉴别及认证系统、网路安全检测与防范技术、防火墙技术、病毒机制与防护技术、网路安全协议与标准等。学生除要完成资讯保安体系不同层次上的各种实验和课程设计外，还将在毕业设计中接受严格训练。

通过学习，将具备了以下几方面的能力：

1．防火墙，建立企业网路的第一道安全屏障；

2．入侵检测系统，有效抵御外来入侵事件，并监控网路内部非法行为；

3．安全评估分析工具，对使用者环境进行基于安全策略的审计分析，及时发现安全隐患；

4．防毒系统，清除病毒危害并预防病毒事件，实现防毒的完全智慧化；

5．伺服器防护系统，保护企业重要伺服器的资料安全性；

6．部署及维护企业资讯化管理（OA、Exchange）系统、UNIX系统等；

7．专业的资料备份、还原系统，保护企业使用者最关键的资料和资源；

8．能够能利用各级别的企业核心路由器、交换机及各种作业系统（Linux、Windows）、资料库产品（SQL SERVER、Oracle）等、安全的域环境设计，根据不同业务需求的不同性，制定严格的安全策略及人员安全要求。

大学里的资讯保安系是学什么的？

学网路资讯保安的，开了较多的数学和计算机课程，将来工作也与计算机离不开

资讯保安专业主要学些什么?

是大学新生吧?我也是被大学资讯保安专业录取了.我以前对它也不了解,网上就知道了,是一门很棒的专业,非常喜欢!

资讯保安专业是计算机、通讯、物理、数学等领域的交叉学科，培养德、智、体、美全面发展的资讯保安专门技术人才。本专业毕业生具有系统的资讯保安和电脑科学与技术基础理论和实践应用能力、很强的英语语言能力和良好的人文素质和创新精神。本专业修业年限为四年，学生在修完教学计划所规定的全部课程并考试合格后，将被授予工学学士学位。

主要课程：外语、高等数学、线性代数、离散数学、资讯保安数学基础、电子技术基础、计算机组成原理与体系结构、C++程式设计、资料结构、作业系统、组合语言程式设计、资讯保安、网路安全、作业系统安全、资讯理论与编码、计算机网路、介面与通讯技术、PKI原理与技术、计算机病毒及其防治技术、入侵检测技术、WEB技术与应用、安全协议导论、网路攻击与防御技术、电子商务概论等。

本专业重视实践能力的培养，按照企业和领域需求确定培养方向，按照产业需求不断调整专业方向，形成灵活的课程体系，动态的教学计划。大量课程采用英文原版教材和双语教学，开设日语、韩语等第二外语。

毕业生适应范围：毕业生将主要服务于资讯产业或其它国民经济管理部门的企事业单位、 *** 、学校和军事部门，从事各类资讯安全系统、计算机安全系统的科研、设计、开发、教学、产业、管理和工程技术应用等方面工作。

目前武汉大学等一些一流大学的资讯保安专业非常好!

网路安全学些什么内容啊？

1.防火墙（正确的配置和日常应用）

2.系统安全（针对伺服器的安全加固和WEB程式码的安全加固以及各种应用伺服器的组建，例如WEB MAIL FTP等等）

3.安全稽核（入侵检测。日志追踪）

4.CCNA课程（网路基础知识。区域网常见故障排除和组建）

5.经验积累。

化学资讯学都考些什么内容？

:wenku.baidu./view/b0cbadaed1f34693daef3e2c. 这是百度文库里的希望对你有帮助

请问《资讯检索》这门大学课程都学些什么内容的啊

哈哈~问到点子上了，俺们刚考完啊~

我们学的是《档案资讯检索》教标引、分类、索引等的编制以及主题词表、分类表等等。

我们还有一门《计算机检索》，是教怎样充分利用网路搜寻引擎、期刊网等工具，准确查询所需资讯，提高查询效率的~

智慧资讯处理主要学些什么内容？

讯号与系统电路分析自动控制原理微机原理及介面数电模电是基础课，

从大的方面来说，主要分为经典人工智慧、计算智慧和其他智慧理论。比较重要的是计算智慧中的人工神经网路、模糊逻辑技术和进化计算，经典人工智慧中的搜寻技术以及资料探勘中的Apriori演算法、粗糙集理论、聚类分析方法，很有前景的噢！

资讯保安主要涉及哪些内容

资讯保安主要包括以下五方面的内容，即需保证资讯的保密性、真实性、完整性、未授权拷贝和所寄生系统的安全性。

资讯保安包括哪些内容

资讯保安主要涉及到资讯传输的安全、资讯储存的安全以及对网路传输资讯内容的审计三方面。

鉴别

鉴别是对网路中的主体进行验证的过程，通常有三种方法验证主体身份。一是只有该主体了解的秘密，如口令、金钥；二是主体携带的物品，如智慧卡和令牌卡；三是只有该主体具有的独一无二的特征或能力，如指纹、声音、视网膜或签字等。

口令机制：口令是相互约定的程式码，假设只有使用者和系统知道。口令有时由使用者选择，有时由系统分配。通常情况下，使用者先输入某种标志资讯，比如使用者名称和ID号，然后系统询问使用者口令，若口令与使用者档案中的相匹配，使用者即可进入访问。口令有多种，如一次性口令，系统生成一次性口令的清单，第一次时必须使用X，第二次时必须使用Y，第三次时用Z，这样一直下去；还有基于时间的口令，即访问使用的正确口令随时间变化，变化基于时间和一个秘密的使用者钥匙。这样口令每分钟都在改变，使其更加难以猜测。

智慧卡：访问不但需要口令，也需要使用物理智慧卡。在允许其进入系统之前检查是否允许其接触系统。智慧卡大小形如信用卡，一般由微处理器、储存器及输入、输出设施构成。微处理器可计算该卡的一个唯一数（ID）和其它资料的加密形式。ID保证卡的真实性，持卡人就可访问系统。为防止智慧卡遗失或被窃，许多系统需要卡和身份识别码（PIN）同时使用。若仅有卡而不知PIN码，则不能进入系统。智慧卡比传统的口令方法进行鉴别更好，但其携带不方便，且开户费用较高。

主体特征鉴别：利用个人特征进行鉴别的方式具有很高的安全性。目前已有的装置包括：视网膜扫描器、声音验证装置、手型识别器。

资料传输安全系统

资料传输加密技术目的是对传输中的资料流加密，以防止通讯线路上的窃听、泄漏、篡改和破坏。如果以加密实现的通讯层次来区分，加密可以在通讯的三个不同层次来实现，即链路加密（位于OSI网路层以下的加密），节点加密，端到端加密（传输前对档案加密，位于OSI网路层以上的加密）。

一般常用的是链路加密和端到端加密这两种方式。链路加密侧重与在通讯链路上而不考虑信源和信宿，是对保密资讯通过各链路采用不同的加密金钥提供安全保护。链路加密是面向节点的，对于网路高层主体是透明的，它对高层的协议资讯（地址、检错、帧头帧尾）都加密，因此资料在传输中是密文的，但在中央节点必须解密得到路由资讯。端到端加密则指资讯由传送端自动加密，并进入TCP/IP资料包回封，然后作为不可阅读和不可识别的资料穿过网际网路，当这些资讯一旦到达目的地，将自动重组、解密，成为可读资料。端到端加密是面向网路高层主体的，它不对下层协议进行资讯加密，协议资讯以明文形式传输，使用者资料在中央节点不需解密。

资料完整性鉴别技术目前，对于动态传输的资讯，许多协议确保资讯完整性的方法大多是收错重传、丢弃后续包的办法，但黑客的攻击可以改变资讯包内部的内容，所以应采取有效的措施来进行完整性控制。

报文鉴别：与资料链路层的CRC控制类似，将报文名栏位（或域）使用一定的操作组成一个约束值，称为该报文的完整性检测向量ICV（Integrated Check Vector）。然后将它与资料封装在一起进行加密，传输过程中由于侵入者不能对报文解密，所以也就不能同时修改资料并计算新的ICV，这样，接收方收到资料后解密并计算ICV，若与明文中的ICV不同，则认为此报文无效。

校验和：一个最简单易行的完整性控制方法是使用校验和，计算出该档案的校验和值并与上次计算出的值比较。若相等，说明档案没有改变；若不等，则说明档案可能被未察觉的行为改变了。校验和方式可以查错，但不能保护资料。

加密校验和：将档案分成小快，对每一块计算CRC校验值，然后再将这些CRC值加起来作为校验和。只要运用恰当的演算法，这种完整性控制机制几乎无法攻破。但这种机制运算量大，并且昂贵，只适用于那些完整性要求保护极高的情况。

讯息完整性编码MIC（Message Integrity Code）：使用简单单向杂凑函式计算讯息的摘要，连同资讯传送给接收方，接收方重新计算摘要，并进行比较验证资讯在传输过程中的完整性。这种杂凑函式的特点是任何两个不同的输入不可能产生两个相同的输出。因此，一个被修改的档案不可能有同样的杂凑值。单向杂凑函式能够在不同的系统中高效实现。

防抵赖技术它包括对源和目的地双方的证明，常用方法是数字签名，数字签名采用一定的资料交换协议，使得通讯双方能够满足两个条件：接收方能够鉴别传送方所宣称的身份，传送方以后不能否认他传送过资料这一事实。比如，通讯的双方采用公钥体制，发方使用收方的公钥和自己的私钥加密的资讯，只有收方凭借自己的私钥和发方的公钥解密之后才能读懂，而对于收方的回执也是同样道理。另外实现防抵赖的途径还有：采用可信第三方的权标、使用时戳、采用一个线上的第三方、数字签名与时戳相结合等。

鉴于为保障资料传输的安全，需采用资料传输加密技术、资料完整性鉴别技术及防抵赖技术。因此为节省投资、简化系统配置、便于管理、使用方便，有必要选取整合的安全保密技术措施及装置。这种装置应能够为大型网路系统的主机或重点伺服器提供加密服务，为应用系统提供安全性强的数字签名和自动金钥分发功能，支援多种单向杂凑函式和校验码演算法，以实现对资料完整性的鉴别。

资料储存安全系统

在计算机资讯系统中储存的资讯主要包括纯粹的资料资讯和各种功能档案资讯两大类。对纯粹资料资讯的安全保护，以资料库资讯的保护最为典型。而对各种功能档案的保护，终端安全很重要。

资料库安全：对资料库系统所管理的资料和资源提供安全保护，一般包括以下几点。一，物理完整性，即资料能够免于物理方面破坏的问题，如掉电、火灾等；二，逻辑完整性，能够保持资料库的结构，如对一个栏位的修改不至于影响其它栏位；三，元素完整性，包括在每个元素中的资料是准确的；四，资料的加密；五，使用者鉴别，确保每个使用者被正确识别，避免非法使用者入侵；六，可获得性，指使用者一般可访问资料库和所有授权访问的资料；七，可审计性，能够追踪到谁访问过资料库。

要实现对资料库的安全保护，一种选择是安全资料库系统，即从系统的设计、实现、使用和管理等各个阶段都要遵循一套完整的系统安全策略；二是以现有资料库系统所提供的功能为基础构作安全模组，旨在增强现有资料库系统的安全性。

终端安全：主要解决微机资讯的安全保护问题，一般的安全功能如下。基于口令或（和）密码演算法的身份验证，防止非法使用机器；自主和强制存取控制，防止非法访问档案；多级许可权管理，防止越权操作；储存装置安全管理，防止非法软盘拷贝和硬碟启动；资料和程式程式码加密储存，防止资讯被窃；预防病毒，防止病毒侵袭；严格的审计跟踪，便于追查责任事故。

资讯内容审计系统

实时对进出内部网路的资讯进行内容审计，以防止或追查可能的泄密行为。因此，为了满足国家保密法的要求，在某些重要或涉密网路，应该安装使用此系统。

----以上转载自《中国资讯保安网infosec.gov.》