什么是哈希表?特点是什么

 我来答
百度网友f21d398
2014-12-25 · TA获得超过3153个赞
知道大有可为答主
回答量:2538
采纳率:14%
帮助的人:1688万
展开全部
简单说就是按照哈希函数关系建立的表
具体内容请参考数据结构相关知识~
下面引用一些别的地方
1 基本原理

我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。

但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

2 函数构造

构造函数的常用方法(下面为了叙述简洁,设 h(k) 表示关键字为 k 的元素所对应的函数值):

a) 除余法:

选择一个适当的正整数 p ,令 h(k ) = k mod p
这里, p 如果选取的是比较大的素数,效果比较好。而且此法非常容易实现,因此是最常用的方法。

b) 数字选择法:

如果关键字的位数比较多,超过长整型范围而无法直接运算,可以选择其中数字分布比较均匀的若干位,所组成的新的值作为关键字或者直接作为函数值。

3 冲突处理

线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ,则当 h(k) 已经存储了元素的时候,依次探查 (h(k)+i) mod S , i=1,2,3…… ,直到找到空的存储单元为止(或者从头到尾扫描一圈仍未发现空单元,这就是哈希表已经满了,发生了错误。当然这是可以通过扩大数组范围避免的)。

4 支持运算

哈希表支持的运算主要有:初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ,A 为存储的数组。
初始化比较容易,例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procedure makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;

哈希函数值的运算根据函数的不同而变化,例如除余法的一个例子:
function h(x:longint):Integer;
begin
h:= x mod p;
end;

我们注意到,插入和查找首先都需要对这个元素定位,即如果这个元素若存在,它应该存储在什么位置,因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时,要么找到一个空的存储单元,要么找到这个元
//素存储的单元,要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procedure insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误,当然这是可以避免的
end;

查找元素是否已经在表中
procedure member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;

这些就是建立在哈希表上的常用基本运算。
Sievers分析仪
2024-10-13 广告
总有机碳(TOC),由专门的仪器——总有机碳分析仪(以下简称TOC分析仪)来测定。TOC分析仪,是将水中的总有机碳氧化为二氧化碳,并且测定其含量。利用二氧化碳与总有机碳之间碳含量的对应关系,从而对水溶液中总有机碳进行定量测定。TOC分析仪由... 点击进入详情页
本回答由Sievers分析仪提供
Uruz7z
2014-12-25 · TA获得超过639个赞
知道小有建树答主
回答量:586
采纳率:0%
帮助的人:379万
展开全部
哈希散列值表,一般是用来快速计算哈希值的,就是SHA-1
追问
能来个列子吗
追答

比如这个是win10的官方下载点,后面的SHA-1就是哈希值,你下载下来再用工具计算他的SHA-1值,如果和他给的一样就说明东西是正确的

本回答被提问者采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式