先来了解一下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冲突的处理,这里就不再讲了。有一句俗话说得好:“师傅领进门,修行靠个人”
,到这里文章也就结束了。