Made Easy In Java

第14章 哈希

2018-04-25  本文已影响90人  爱做梦的胖子

14.1 什么是哈希？

哈希是一种以尽可能快的方式存储和检索数据的技巧。它可以用于实现最优搜索和实现符号表。

14.2 为什么使用哈希？

在Tree那一章中，我们学习到平衡二叉搜索树支持以O(log n)的时间复杂度，insert、删除和搜索数据操作。在实际应用中，哈希提供了O(1)时间复杂度操作数据的可能（如果我们需要的话）。记住，哈希在最坏情况下操作数据的时间复杂度仍是O(log n)，但是它可以提供平均O(1)的时间复杂度。

14.3 哈希表抽象数据类型

哈希表的通用操作如下：

14.4 理解哈希表

简单来说，我们可以将数组看作一个哈希表。下面让我们看一个例子（这可以帮助我们理解哈希表的使用）：如果一个字符数组中含有重复字符，请给出一个算法，打印出第一个重复的字符。我们可以先思考一下可能的解决方案，然后再继续阅读。其中一种简单粗暴的方式是：给定一个字符串，对其中的每一个字符检查是否存在重复字符。这种方法的时间复杂度是O(n^2)，空间复杂度是O(1)。

现在，我们来寻找这个问题一种更好的解决方法。我们的目标是找到第一个重复的字符，如果我们可以在数组中记录之前的字符出现的次数是不是一个好方法呢？

以ASCII码字符为例，我们知道其可能的字符数为255。我们可以创建一个大小为255的数组，并且将其值均初始化为0。每个字符的ASCII值对应该数组的index，每输入一个字符，对应index的数组值加1。因为我们使用的是数组，所以我们可以在常量时间访问其中的任何index对应的数值。当我们在扫描输入字符的时候，如果发现该字符对应的计数值已经是1，这时，我们就可以判定这个字符就是我们要寻找的第一个出现重复的字符。

public class Demo_001_FirstRepeatedCharDemo {
    public static void main(String[] args) {
        char[] str = {'a', 'b', 'a', 'd', 'd', 'a'};
        getFirstRepeatedChar(str);
    }

    private static char getFirstRepeatedChar(char[] str) {
        int[] charCount = new int[256];
        for (char c : str) {
            if (1 == charCount[c]) {
                System.out.println("'" + c + "' is the first repeated char...");

                return c;
            }
            charCount[c] = charCount[c] + 1;
        }

        System.out.println("there is no repeated char...");

        return 0;
    }
}

为什么不使用数组？

在解决前面的问题时，我们提前定义了一个256大小的数组，这是因为我们知道ASCII码字符的大小为256。现在我们对上述问题稍微修改一下，假如我们给定一个整型数组而不是字符数组，问题同上：查找第一个重复的数字就，那么我们如何解决这个问题呢？

在这个例子中，数组中可能的值是不确定的（或者说可能很大）。创建一个很大的数组并且存储对应的计数值是不可能的，因为这意味着无限的key值需要映射到内存中有限的空间中。因此，使用简单数组是不可能的，因为可能的key值是很大的。把key值映射到某一位置的过程称为哈希。

注意： 我们不必关注key值如何映射到某一位置，这取决于使用的准换函数。一个简单的函数是key % 表大小。

14.5 哈希组件

哈希有4个关键组件

  1. 哈希表
  2. 哈希函数
  3. 哈希碰撞
  4. 哈希碰撞解决方法

14.6 哈希表

哈希表是一个泛化数组。在数组中，我们把key为k的数据存储在数组中第k个位置。这意味着，给定一个key为k，我们可以在数组中第k个位置找到该元素。这被称为直接寻址。

当我们可以提供一个key一个地址空间时，直接寻址是适用的。但是，如果我们不能提供足够的空间给每一个key分配一个位置，我们需要一个一种机制来解决这个问题。这个问题场景换一种说法是：如果我们有更少的地址空间和更多的可能key值，简单的数组并不能满足需求。

针对以上场景，一个可能的方式是使用哈希表。哈希表（哈希映射）是一种数据结构，它存储key值以及它们相关联的值，哈希表使用哈希函数将key值映射到某个空间地址。通常适用于实际存储的key数量相对于可能的key值数量要少的情况。

14.7 哈希函数

哈希函数用于将key值转换为index值。理想情况下，哈希函数应该将每一个key值映射为唯一的索引地址，但实际上这很难实现。

给定义一组数据元素，一个哈希函数如果可以将每一个元素映射到唯一的slot地址，这个函数则被称为完美哈希函数。如果我们知道数据元素和集合不会改变，那么是有可能构造出完备哈希函数的。不幸的是，给定任意的元素集合，我们并没有系统的方式来构造一个完备哈希函数。幸运的是，我们不需要一个完美哈希函数来获取高效的性能。

一个可以保持一直是完美哈希哈数的方法就是增大哈希表的大小，这样就可以保证可能的数据值都可以被容纳。而且，每个值都拥有唯一的slot地址。如果数据元素的数量比较少，这样做是实际可行的，但是，如果可能的数据元素数量很大，这就不可行了。举个例子，如果数据元素是9位的社保号码，采用上述方法则需要一亿个slot空间。但是，如果我们只想存储一个班25个学生的数据，则会浪费大量的内存空间。

我们的目标是创建一个容易计算，而且可以将数据元素均匀的分布在哈下表中的哈希函数，而且这可以最小化哈希碰撞。有很多种通用的方法来扩展简单的取余方法，我们会介绍一下其中的几种方法。

折叠法使用将数据元素均分为相等的两部分（后面一部分可大小能不相等）的方式来构造哈希函数。将每一部分的值累加起来最为哈希结果值。举个例子，我们的数据元素是电话号码436-555-4601，我们把数据元素按照2个一组分组为（43，65，55，46，01）。将分组相加，43+65+55+46+01=210。假如我们的哈希表有11个slot空间，那么我们就可以对11取余，然后保留余数。在这个例子中，210%11=1，所以，电话号码436-555-4601对应的哈希index是1。其他的折叠法会将第一步分组数据每隔一组作反转操作，然后再相加。上面的例子就成了43+56+55+64+01=219，219%11=10，所以其对应的哈希index是10。

如何选择哈希函数？

与创建哈希表相关的基本问题是：

合适的哈希函数的特征

一个好的哈希函数应该具有以下特征：

14.8 负载系数

非空哈希表的负载系数定义为哈希表中的数据项个数除以哈希表的大小。负载系数是我们决定是否再次作哈希运算或者扩大哈希表大小的决策参数。这也帮助我们确定哈希函数的效率，这意味着负载系数可以告诉我们该哈希函数是否将key均匀分布在哈希表上。

Load factor = Number of elements in hash table / Hash Table Size

14.9 哈希碰撞

哈希函数是用于将每一个key映射到不同的地址空间，实际上这不可能构造这样的哈希函数，这里会出现哈希碰撞的问题。哈希碰撞指的是不同的key会映射到同一个地址空间。

14.10 哈希碰撞解决方法

寻找一个替代碰撞地址空间的过程方法被称为碰撞解决。虽然哈希表有碰撞问题，但是相比于其他数据结构（比如搜索树），在很多场景下，哈希表仍是更高效的方式。有很多碰撞解决方案，其中最著名的是直接地址链和开发寻址。

14.11 分离链接法

采用链接方式的碰撞解决方案将链表表示和哈希表结合起来，当两个或多个记录映射到同一个位置，这些记录组成一个单链表（称为链）。

14.12 开放地址法

开放寻址方式中所有的key存储在哈希表中，这个种方式称为闭合哈希，它基于探测方式，采用探测解决碰撞。

线性探测

线性探测的探测间隔固定为1。我们从哈希表的起始位置顺序的在哈希表中查找key，如果当前位置被占用了，则继续检查下一个位置。如果有需要，我们也可以从最后一个到第一个环绕查找。再次哈希函数如下：

rehash(key) = (n + 1)%tablesize

线性探测的一个问题是表中的数据项倾向于聚集在一起（扎堆），换句话说，哈希表中包含一组连续占用的地址空间，这被称为聚类。

聚类可以相互靠近，也可以融合成一个大的聚类。因此，可能表中的一部分数据很集中，而另一部分只有相对很少的数据项。聚类可能引起长时间的探测查找，从而减弱整体性能。

步进大小决定下一个探测的位置，有可能采用不同的步长（超过1）探测。如果我们选择哈希表大小为素数，那么步长大小相对于哈希表大小是互素的，比如，它们的最大公约数是1。聚类不可以通过使用更大的步长来避免。

上一篇下一篇

猜你喜欢

热点阅读