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

目录

一、说明

二、从数据表的维护说起

2.1 什么是哈希(hashable)？

2.2 数据库的插入删除

2.3 全预留表格

三、为什么要使用哈希？

3.1 最简单的散列方法

3.2 哈希散列有什么好处？

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

3.4 哈希组件

四、结论

---

一、说明

        哈希的目的是提高检索速度，并且内存额外开销不大。数据越大，如何提高数据管理效率成了麻烦：不是内存太大，就是检索过慢。这是个问题，随着这个问题的深度接触，您就会发现，哈希是一个不错选择，而且配合哈希还有不少的操作，似乎不为人知。

二、从数据表的维护说起

2.1 什么是哈希(hashable)？

        解释python中可哈希对象的工作原理，必须首先了解术语“哈希”。

        散列（哈希）是计算机科学中的一个概念，用于创建高性能的伪随机访问数据结构，在该结构中要快速存储和访问大量数据。

        例如，如果您有10,000个电话号码，并且想要将它们存储在一个数组中（这是一个顺序数据结构，可将数据存储在连续的内存位置中，并提供随机访问），但是您可能没有所需的连续数量内存位置。

        您可以改为使用大小为100的数组，并使用哈希函数将一组值映射到相同的索引，并且这些值可以存储在链接列表中。这提供了类似于阵列的性能。

        注意：哈希算法的最根本要点是，从某个变量的值，能够立刻推算出他的地址（尽管有冲撞也是数量不多），如果没有这一条，哈希的快速检索不成立。

2.2 数据库的插入删除

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

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

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

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

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

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

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

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

2.3 全预留表格

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

        这种设计看似蠢笨，然而，这样思考是符合现实情况的，因为现实数据追加本来是无续散列的，将它们强行紧密排列必然出现插入和删除的不便。因此，如果内存够大，这种表也是可以的。

        如果电话号码不存在，则数组中的条目为 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 哈希散列有什么好处？

        哈希散列后，有以下好处：

•          将不确定长度的表格，用固定长度的表格映射，实现可控的目的。
•          大大提升了索引速度。（将一维数组折叠成二维数组，索引速度提高）
•          添加数据后，若碰撞发生，再追加元素到链表后，这节约了大量空间。 

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

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

基本操作：

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

3.4 哈希组件

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

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

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

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

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

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

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

四、结论

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