数据结构 二叉树遍历 关系型工作原理(3)

这个hash table有10组bucket。我只在图中画了5组bucket，另外5组 请自行脑补。Hash function我定义为除10求模(除以10求余数)，换句话讲，我可以通过数值的最后一位数字确定bucket。

如果数字的最后一位是0，将数值存储到bucket 0中

如果数字最后一位是1，将数值存储到bucket 1中

如果数字最后一位是2，将数值存储到bucket 2中

…..

比较函数我采用判断两个整型数值是否相等的方法比较。

我们看一下如何找到hash table中找到元素78：

通过哈希函数计算得到哈希值8

在bucket 8中查找元素，第一个元素就是78

返回元素78

查询只需要执行两个步骤：第一步是计算哈希值，确定bucket位置；第二步在bucket中查看元素。

我们再看一下如何查找元素59：

计算哈希值，得到9

在bucket中查找元素59。第一个元素是99，99!=59，99不是要查找的元素。

采用同样的方式，查找第二个元素(9)，第三个元素(79)，… 最后一个元素(29)。

不存在59这个元素

本次查询执行了7步操作

如你所见，查询不同的值，时间复杂度是不同的。

如果你将哈希函数改为除以1000000取模(取数字的最后6位数，作为bucket标识)。上面的第二次查询只需要一步(在bucket 59中没有任何数据)。找一个好的哈希函数，保证每个bucket中存储尽可能少的数据，是非常困难的。

在上面的例子中找一个好的hash function非常容易。但这仅仅是一个简单的样例，如果关键字是如下数据类型，将非常困难：

1. 一个字符串(例如表示人的名)

2. 两个字符串(例如同时表示人的姓和名)

3. 两个字符串 + 一个日期(例如表示人的姓、名及生日)

设计一个好的hash function，哈希表的查询时间为O(1)。

为什么不使用数组? 问得好。

Hash table支持将部分内容加载到内存，另一部分保存在磁盘上。不必把整颗树加载到内存，节省内存空间。

数组必须使用连续的内存空间。如果要加载一张大表数据到内存，很难找到一大片连续的内存空间。内存分配失败的风险很大。

Hash table支持选择你想要的任意字段作为关键字(例如：人的所属国家，加上人的姓名。任意组合)。

想了解更多的信息，你可以读一下介绍Java如何实现hash map的文章，它是hash map高效实现的一个样例。理解本文中概念，你不需要懂JAVA。

已翻译的《How does a relational database work》其它章节链接：

1. 关系型工作原理-时间复杂度：

2. 关系型工作原理-归并排序：

3. 关系型工作原理-数据结构：

4. 关系型工作原理-高速缓存：

5. 关系型工作原理-事务管理(一)：

6. 关系型工作原理-事务管理(二)：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-74529-3.html