【数据管理】谈谈哈希原理和散列表

一、说明

        提起哈希，有人要说：不就是一个稀疏表格么，谈的上什么原理？我说：非也，哈希是是那种看似无物，其实解决大问题的东西。如何提高数据管理效率？这是个问题，随着这个问题的深度接触，您就会发现，哈希是一个不错选择，而且配合哈希还有不少的操作，似乎不为人知。

二、从数据表的维护说起

2.1 数据库的插入删除

        我们知道，数据库最重要的维护不外乎key。数据库水平高低，就看你对key维护有何独到的设计。这里我们把key抽象成电话号码，且看如何维护？

        假设我们要设计一个以电话号码（作为键）存储员工记录的系统。我们希望高效地执行以下查询：

• 插入电话号码和相应的信息。
• 搜索电话号码并获取信息。
• 删除电话号码和相关信息。

         我们可以想到使用如下数据结构来维护不同电话号码的信息。

• 电话号码和记录的数组。
• 电话号码和记录的链接列表。
• 以电话号码为键的平衡二叉搜索树。
• 直接访问表。 

        对于数组和链表，我们需要以线性方式搜索，这在实践中可能代价高昂。如果我们使用数组并保持数据排序，那么使用二进制搜索可以在 O(Logn) 时间内搜索电话号码，但是插入和删除操作变得昂贵，因为我们必须维护排序顺序。

        使用平衡二叉搜索树，我们得到适度的搜索、插入和删除时间。

        以上的数据维护是过去的老式想法，因为存储是昂贵的。所以，索引数据（电话号）需要密集排列，中间没有间隙。因此插入、删除、排序成了必须的维护手段。

2.2 全预留表格

        所谓哈希表的稀疏性，还不如叫做全预留表格。也就是不管你的电话号出不出现，我总是预留一个超大表格，该表格足以覆盖电话号码的全部。比如，对于电话号码，我们首先做一个00000000-99999999的大数组，该数组足以满足任意电话号码的存取，而且常驻内存。以上电话号码的哈希表如图。

电话号码的哈希表 

        这种设计看似蠢笨，然而，在现实中的内存数据库全是这种模式：用大内存换取时间。因而使得dds协议，rtps协议得以实现，比如redis数据库就是这种模式。

        如果电话号码不存在，则数组中的条目为 NIL，否则数组条目存储指向records corresponding to phone number. 时间复杂度方面这个解决方案是最好的，我们可以在 O(1) 时间内完成所有操作。例如插入一个电话号码，我们创建一个包含给定电话号码详细信息的记录，使用 phone number 作为索引，并将指向创建的记录的指针存储在表中。
        这个解决方案有很多实际限制。这个解决方案的第一个问题是需要额外的空间是巨大的。例如，如果电话号码是 n 位数字，我们需要 O(m * 10n) 表空间，其中 m 是要记录的指针的大小。问题是编程语言中的整数可能不会存储 n 位数字。

        由于上述限制，不能总是使用直接访问表。哈希是几乎可以在所有此类情况下使用的解决方案，并且在实践中与上述数据结构（如数组、链表、平衡 BST）相比表现非常出色。（1）搜索时间平均（在合理的假设下）和最坏情况下的 O(n)。现在让我们了解什么是散列。

三、为什么要使用哈希？

3.1 最简单的散列方法

        散列：散列是一种流行的技术，用于尽可能快地存储和检索数据。下面用最简单例子说明为什么要散列，如何散列？

        比如有0-200的随机数作为key键，那么，如果用全预留表格存储，索引字至少用201个存储单元（有些单元可能永远不用）。

        那么我用长度12个长度单元存索引，如下：

        Random ∈【0-200】，索引字为Index∈【0，11】，索引字数组长度L=12，模数M=11.

        Random % M = Index

给出几个具体数字：55，70，196，185，0，200

   

        我们索引一个关键字（比如196）的次数为：N = Index（最多10）+ 链表（最多18次）≤ 28次，是不是比全索引表200次要少很多呢？

3.2 更高明的哈希--平恒二叉树

        如果你仔细观察，在平衡的二叉搜索树中，如果我们尝试搜索、插入或删除任何元素，那么相同的时间复杂度是 O(logn)。以更快的方式操作，即以更优化的方式和这里的散列开始发挥作用。在散列中，所有上述操作都可以在 O(1) 中执行，即常数时间。重要的是要理解散列的最坏情况时间复杂度仍然是 O(n)，但平均情况时间复杂度是 O( 1).
现在让我们了解一些散列的基本操作。

基本操作：

• HashTable：此操作用于创建新的哈希表。
• 删除：此操作用于从哈希表中删除特定的键值对。
• 获取：此操作用于在哈希表中搜索键并返回与该键关联的值。
• Put：此操作用于在哈希表中插入新的键值对。
• DeleteHashTable：此操作用于删除哈希表

3.3 哈希组件

        1）哈希表：存储指向与给定电话号码对应的记录的指针的数组。如果没有现有电话号码的哈希函数值等于条目的索引，则哈希表中的条目为 NIL。简单来说，我们可以说哈希表是数组的推广。哈希表提供了一种功能，其中存储数据集合，以便以后在需要时很容易找到这些项目。

        2）哈希函数：将给定的大电话号码转换为实用的小整数值的函数。将给定的键转换为特定的槽索引。其主要工作是将每个可能的键映射到唯一的槽索引。如果每个键被映射到一个唯一的槽索引，那么哈希函数被称为完美哈希函数。创建一个完美的哈希函数非常困难，但我们作为程序员的工作是创建这样一个哈希函数，借助它的数量碰撞尽可能少。碰撞在前面讨论。

一个好的哈希函数应该具备以下特性：

• 可高效计算。
• 应该统一分配键（每个表位置每个位置的可能性相同）。
• 应该尽量减少碰撞。
• 应该有一个低负载因子（表中的项目数除以表的大小）。

        例如，对于电话号码，一个糟糕的哈希函数是取前三位数字。更好的函数是考虑最后三位数字。请注意，这可能不是最好的哈希函数。

        3）冲突处理：由于哈希函数为我们提供了一个大键的小数字，因此有可能两个键产生相同的值。新插入的键映射到哈希表中已被占用的槽的情况称为碰撞和以下是处理冲突的方法：

        Chaining：思想是让hash表的每个cell指向一个hash函数值相同的记录链表，Chaining简单，但需要表外额外的内存。
        开放式寻址：在开放式寻址中，所有元素都存储在哈希表本身中。每个表条目包含一条记录或 NIL。在搜索元素时，我们逐个检查表槽，直到找到所需的元素或者它是清楚该元素不在表中。

四、结论

        知道哈希原理，你就知道快速检索数据库大概是个什么东西，也大概知道，近几年大数据处理的数据库如Redis数据库如何构造。负载平恒概念，dds协议，rtps协议等，理解起来也不复杂了。