当前位置 : 主页 > 编程语言 > 其它开发 >

让你真正的理解Hash

来源:互联网 收集:自由互联 发布时间:2022-05-25
先来了解一下Hash的基本思路: 设要存储对象的个数为num, 那么我们就用len个内存单元来存储它们(len=num); 以每个对象ki的关键字为自变量,用一个函数h(ki)来映射出ki的内存地址,也就是

先来了解一下Hash的基本思路:

设要存储对象的个数为num, 那么我们就用len个内存单元来存储它们(len>=num);

以每个对象ki的关键字为自变量,用一个函数h(ki)来映射出ki的内存地址,也就是ki

的下标,将ki对象的元素内容全部存入这个地址中就行了。这个就是Hash的基本思路。

 

Hash为什么这么想呢?换言之,为什么要用一个函数来映射出它们的地址单元呢?

This is a good question.明白了这个问题,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;

好了,存现在是存好了。但是,这并没有体现出Hash的妙处,也没有回答刚才的问题。

下面就让我来揭开它神秘的面纱吧。

 

现在我要你查找11这个元素是否存在。你会怎么做呢?

当然,对于数组来说,那是相当的简单,一个for循环就可以了。

也就是说我们要找4次。

下面我们来用Hash找一下。

首先,我们将要找的元素11代入刚才的函数中来映射出它所在的地址单元。也就是

h(11) = 11%5 = 1 了。下面我们来比较一下Hash[1]?=11, 这个问题就很简单了。

也就是说我们就找了1次。我咧个去, 这个就是Hash的妙处了。至此,刚才的问题也

就得到了解答。至此,你也就彻底的明白了Hash了。

 

至于Hash冲突的处理,这里就不再讲了。有一句俗话说得好:“师傅领进门,修行靠个人”

,到这里文章也就结束了。

上一篇:LINQ之路17:LINQ to XML之X
下一篇:没有了
网友评论