hash的基本原理

hash定义了一个存储hash值的数组，该数组的大小由外面调用hash的对象指定

当然，我们也明白，hash数组越大越好，但是占用大量的内存，这就是空间和时间的等

价替换。所以hash数组不可能很大，那么就存在一个问题了，hash的值肯定是一个无底洞，

究竟应该建立一种什么样子的映射表

1

。。。

。。。

100

。。。

200

。。。

300

如果是有300个hash值，我们是否应该建立一个300的数组？如果是300万呢？？

所以只能够采用一种映射的方式：

1 1

。。。 。。。

100 100

。。。

200 100

。。。

300 100

我们把100到200的数据同样子映射到1到100上，200到300上，

这种情况下，我们可以通过求模的方式进行，在程序中确实是这么做的。

hash的基本结构

hash模块没有指定存储hash内容长度的数组，必须由外面实现Hash结构体，

在这里我们可以把Hash结构体看作是一个对象，

struct Hash {

unsigned int htsize; /* Number of buckets in the hash table */

unsigned int count; /* Number of entries in this table */

HashElem *first; /* The first element of the array */

struct _ht { /* the hash table */

intcount; /* Number of entries withthis hash */

HashElem*chain; /* Pointer to first entry withthis hash */

}*ht;

};

hash 的链式结构

hash的查找与数据块存储的关系

根据hash出来的结果，在hash表中找到对应的结构体，但是该结构体只有两个成员是存储了相关的信息的。

struct HashElem {

HashElem *next,*prev; /* Next and previous elements in thetable */

void*data; /* Dataassociated with this element */

constchar *pKey; /* Key associatedwith this element */

};

我的开始设想是保存有一个数据块的编号ID,根据数据块的ID，查找存储数据块的具体信息。一下子没有了思路。

我不明白的地方是data保存了什么，按道理，应该是保存指向数据的指针才对，或者是记录所在的页面才对啊，并且记录的元素相关的数据是什么？？

在这里，作者巧妙的记录了hash之前的数据，而不是保存hash的值，毕竟还是存在冲突的，两个pKey的值很可能得到同一个hash的值，在搜索hash的过程中，只需要将pKey和搜索的关键字进行匹配即可避免了冲突的发生！！

hash 的规模分类

数据量少

比如现在我们只有20个元素，但是我们却不得不分配一个100元素的存储，去存储，不仅仅浪费空间，可能并没有比线性访问的速度快。所以作者在这里有了一个分水岭，当htsize和ht等于零的情况下，表示当前将所有的hash保存在一个链表当中，遍历hash的时候，只需要遍历first链表，

数据量庞大

作者有在其中rehash一遍hash表，当hash表的元素个数大于10 ，并且比hash数组的长度的2倍

还要大，这种情况下，进行了扩展。

hash数据的扩容

hash扩容都是当前数据的两倍，目前情况下，是否会100万数据的不同

hash的磁盘读写

从磁盘读

hash表的存储和读取问题：

在这里存在一个疑问，通过hash表能够快速的定位到某一个元素，但是对于刚刚启动的

程序，Hash表是怎么形成的。

当然了，如果是在空表的情况下，进行大量数据的插入，当前数据库肯定是

保存了Hash表在内存当中，随着数据的插入，Hash表也越来越大。

问题是仅仅是开机读取数据库的内容，这个时候，就需要使用到hash表，问题是

我们怎么知道hash表的来源，难不成，我们还要遍历一遍数据库的内容，然后重新生成一遍

hash表，我看作者肯定不会这么傻，嘿嘿！！

往磁盘写

hash的插入

hash的删除

我们在删除数据的时候，是否需要删除hash表中的数据，答案是肯定的，

在这里就会有一个次序的问题！！

hash链表的数组长度分析

众所周知，如果hash表定义的数组长度比较短，比如100，如果我插入100万的数据，然后寻找hash的值在什么地方，还是需要hash一遍，找到数组头指针，然后平均遍历1万遍链表中的元素去查找。

在这里引出了一个问题：是否有内存泄露，因为是通过链式地址法来保存

数据的索引的。

struct HashElem {

HashElem *next,*prev; /* Next and previous elements in thetable */

void*data; /* Dataassociated with this element */

constchar *pKey; /* Key associatedwith this element */

};

参考网址

摘自：http://blog.csdn.net/missyou03/article/details/5674308

http://www.cnblogs.com/chencheng/archive/2012/06/18/2554001.html

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!