最后我们介绍的重要数据结构就是hash表。当你需要快速查找的时候非常有用，而且理解hash表会有助于我们以后理解常用数据库join方式之一hash join。这种数据结构常被数据库用作存储内部数据结构：表锁或缓存池（后续章节会介绍）。 hash表能够通过元素key快速
最后我们介绍的重要数据结构就是hash表。当你需要快速查找的时候非常有用，而且理解hash表会有助于我们以后理解常用数据库join方式之一hash join。这种数据结构常被数据库用作存储内部数据结构：表锁或缓存池（后续章节会介绍）。
hash表能够通过元素key快速找到元素的，为了构建一张hash表，你需要定义：
一个元素的key；一个关于key的hash函数，key的hash值就代表元素所在的位置（我们通常称为hash桶）；一个关于key的比较函数，一旦你找到了正确的桶，你就可以通过比较函数找到正确的元素。一个简单的例子让我们看一个虚拟的例子：
上图中的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。
下一章我们来开始介绍数据库的整体视图。