当前位置:Gxlcms > mysql > 【连载】关系型数据库是如何工作的?(6)

【连载】关系型数据库是如何工作的?(6)

时间:2021-07-01 10:21:17 帮助过:29人阅读

最后我们介绍的重要数据结构就是Hash表。当你需要快速查找的时候非常有用,而且理解Hash表会有助于我们以后理解常用数据库Join方式之一Hash join。这种数据结构常被数据库用作存储内部数据结构:表锁或缓存池(后续章节会介绍)。 Hash表能够通过元素Key快速

最后我们介绍的重要数据结构就是Hash表。当你需要快速查找的时候非常有用,而且理解Hash表会有助于我们以后理解常用数据库Join方式之一Hash join。这种数据结构常被数据库用作存储内部数据结构:表锁或缓存池(后续章节会介绍)。

Hash表能够通过元素Key快速找到元素的,为了构建一张Hash表,你需要定义:

  • 一个元素的Key;
  • 一个关于Key的Hash函数,Key的hash值就代表元素所在的位置(我们通常称为Hash桶);
  • 一个关于Key的比较函数,一旦你找到了正确的桶,你就可以通过比较函数找到正确的元素。

一个简单的例子

让我们看一个虚拟的例子:
Hash表

上图中的Hash表实际有10个桶,Hash函数就是取10的余数,也就是每个Key的个位数字:

  • 如果个位数是0,则元素在0号桶;
  • 如果个位数是1,则元素在1号桶;
  • 如果个位数是2,则元素在2号桶;

比较函数就是比较两个整数是否相同的函数。如果我们想要找到78:

  • Hash表计算的78的哈希值是8;
  • 找到8号桶,第一个元素就是78;
  • 返回78;
  • 整个搜索花费2个操作:1-计算Hash值;2-找到桶中的元素;

如果我们想要找到59:

  • Hash表计算的59的哈希值是9;
  • 找到9号桶,第一个元素是99,99!=59,因此这不是我要找的元素;
  • 用相同的逻辑找到9,79,…,最后一个29;
  • 元素59并不存在;
  • 真个搜索花费7个操作。

好Hash函数的标准

标准依赖于你要查找的值,不同类型的值花费是不同的。
如果将之前例子中的Hash函数换为取1 000 000的余数(也就是最后6位数),第二个例子耗费的操作数就会降为1,因为在000059号桶中没有元素。实际上,真正的难点就是找到一个能够尽可能降低每个桶中元素数量的Hash函数。(译者注:我们一般称之为降低Hash冲突

在上述两个例子中,找到一个好的Hash函数很容易。但是当Key是下列类型时,找到一个好Hash函数很困难:

  • 1个字符串,比如一个人的名字;
  • 2个字符串,比如一个人的姓+名字;
  • 2个字符串和一个日期,比如一个人的姓+名字+出生日期。

只要拥有一个足够好的Hash函数,搜索的时间复杂度就是O(1)。

数组和Hash表的比较

什么情况下需要使用数组呢?这是一个好问题!

  • 基于Hash的数据库表,可以在内存中只加载一般的桶,其他桶可以留在磁盘上;
  • 数组必须占用一个连续的内存空间,如果一个基于二维数组的数据库表很大,那么要在内存中找到足够的连续空间很困难;
  • 基于Hash的数据库表,你可以选择任意的Key,比如可以选择Key为国家+名字。

关于更多的信息,可以参考我写的另外一篇文章Java HashMap。但理解这篇文章并不要求你理解Java。

下一章我们来开始介绍数据库的整体视图。

人气教程排行