时间:2021-07-01 10:21:17 帮助过:29人阅读
最后我们介绍的重要数据结构就是Hash表。当你需要快速查找的时候非常有用,而且理解Hash表会有助于我们以后理解常用数据库Join方式之一Hash join。这种数据结构常被数据库用作存储内部数据结构:表锁或缓存池(后续章节会介绍)。 Hash表能够通过元素Key快速
最后我们介绍的重要数据结构就是Hash表。当你需要快速查找的时候非常有用,而且理解Hash表会有助于我们以后理解常用数据库Join方式之一Hash join。这种数据结构常被数据库用作存储内部数据结构:表锁或缓存池(后续章节会介绍)。
Hash表能够通过元素Key快速找到元素的,为了构建一张Hash表,你需要定义:
让我们看一个虚拟的例子:
上图中的Hash表实际有10个桶,Hash函数就是取10的余数,也就是每个Key的个位数字:
比较函数就是比较两个整数是否相同的函数。如果我们想要找到78:
如果我们想要找到59:
标准依赖于你要查找的值,不同类型的值花费是不同的。
如果将之前例子中的Hash函数换为取1 000 000的余数(也就是最后6位数),第二个例子耗费的操作数就会降为1,因为在000059号桶中没有元素。实际上,真正的难点就是找到一个能够尽可能降低每个桶中元素数量的Hash函数。(译者注:我们一般称之为降低Hash冲突)
在上述两个例子中,找到一个好的Hash函数很容易。但是当Key是下列类型时,找到一个好Hash函数很困难:
只要拥有一个足够好的Hash函数,搜索的时间复杂度就是O(1)。
什么情况下需要使用数组呢?这是一个好问题!
关于更多的信息,可以参考我写的另外一篇文章Java HashMap。但理解这篇文章并不要求你理解Java。
下一章我们来开始介绍数据库的整体视图。