散列表

来自计算思维百科
跳转至: 导航搜索
散列表.png

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(,在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,存放首字母的表对应的就是散列表。

散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

基本概念

哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上,并以关键字在地址区间中的象作为记录在表中的存储位置,这种表称为哈希表或散列,所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比,哈希表无疑是查找速度比较快的一种。

哈希(Hash)算法,即散列函数。它是一种单向密码体制,即它是一个从明文到密文的不可逆的映射,只有加密过程,没有解密过程。同时,哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。

散列函数即在查找某个元素时,在元素的关键字与元素的存储位置之间建立起一种对应关系,只需要利用这种确定的关系,由给定的关键字就可以直接找到该元素。

应用范围

Hash算法在信息安全方面有很多应用。比如文件校验,数字签名,鉴权协议等等。

应用案例

应用1- 花名册

案例:一个班级有30名学生,将这些学生用各自的姓氏的拼音排序,其中姓氏首字母相同的学生放在一起。根据学生姓名的拼音首字母建立的散列表。

1

A

安紫衣

2

B

白小翼

3

C

陈立本、陈冲

4

D

邓华

例如,要查找邓华,就可以从序列号为4的一行中找到该学生。这种方法比在一堆杂乱无章的姓名中查找要方便的多。

可以体现的计算思维

散列表通过一个函数计算数据存放的位置,可以高效地找到需要的数据,体现了计算思维的抽象特点。