关于算法:看动画学算法之hashtable

java 中和 hash 相干并且罕用的有两个类 hashTable 和 hashMap, 两个类的底层存储都是数组，这个数组不是一般的数组，而是被称为散列表的货色。

散列表是一种将键映射到值的数据结构。它用哈希函数来将键映射到小范畴的指数（个别为 [0.. 哈希表大小 -1]）。同时须要提供抵触和对抵触的解决方案。

明天咱们来学习一下散列表的个性和作用。

文末有代码地址，欢送下载。

散列表中比拟要害的三个概念就是散列表，hash 函数，和抵触解决。

散列是一种算法（通过散列函数），将大型可变长度数据集映射为固定长度的较小整数数据集。

散列表是一种数据结构，它应用哈希函数无效地将键映射到值，以便进行高效的搜寻 / 检索，插入和 / 或删除。

散列表广泛应用于多种计算机软件中，特地是关联数组，数据库索引，缓存和汇合。

散列表必须至多反对以下三种操作，并且尽可能高效：

搜寻（v）– 确定 v 是否存在于散列表中，
插入（v）– 将 v 插入散列表，
删除（v）– 从散列表中删除 v。

因为应用了散列算法，将长数据集映射成了短数据集，所以在插入的时候就可能产生抵触，依据抵触的解决办法的不同又能够分为线性探测，二次探测，双倍散列和拆散链接等抵触解决办法。

思考这样一个问题：找到给定的字符串中第一次反复呈现的的字符。

怎么解决这个问题呢？最简略的方法就是进行 n 次遍历，第一次遍历找出字符串中是否有和第一个字符相等的字符，第二次遍历找出字符串中是否有和第二个字符相等的字符，以此类推。

因为进行了 n * n 的遍历，所以工夫复杂度是 O(n²)。

有没有简略点的方法呢？

考虑一下字符串中的字符汇合其实是无限的，如果都是应用的 ASCII 字符，那么咱们能够构建一个 256 长度的数组一次遍历即可。

具体的做法就是遍历一个字符就将绝对于的数组中的相应 index 中的值 +1，当咱们发现某个 index 的值曾经是 1 的时候，就晓得这个字符反复了。

那么数组的实现有什么问题呢？

数组的问题所在：

键的范畴必须很小。如果咱们有（十分）大范畴的话，内存使用量会（十分的）很大。
键必须密集，即键值中没有太多空白。否则数组中将蕴含太多的空单元。

咱们能够应用散列函数来解决这个问题。

通过应用散列函数，咱们能够：

将一些非整数键映射成整数键，
将大整数映射成较小的整数。

通过应用散列函数，咱们能够无效的缩小存储数组的大小。

无利就有弊，尽管应用散列函数能够将大数据集映射成为小数据集，然而散列函数可能且很可能将不同的键映射到同一个整数槽中，即多对一映射而不是一对一映射。

尤其是在散列表的密度十分高的状况下，这种抵触会常常产生。

这里介绍一个概念：影响哈希表的密度或负载因子 α = N / M，其中 N 是键的数量，M 是哈希表的大小。

其实这个抵触的概率要比咱们设想的更大，举一个生日悖论的问题：

一个班级外面有多少个学生会使至多有两人生日雷同的概率大于 50%？

咱们来计算一下下面的问题。

假如 Q（n）是班级中 n 集体生日不同的概率。

Q（n）= 365/365×364/365×363/365×…×（365-n + 1）/ 365，即第一人的生日能够是 365 天中的任何一天，第二人的生日能够是除第一人的生日之外的任何 365 天，等等。

设 P（n）为班级中 n 集体的雷同生日的概率，则 P（n）= 1-Q（n）。

计算可得，当 n =23 的时候 P(23) = 0.507> 0.5（50%）。

也就是说当班级领有 23 集体的时候，班级至多有两个人的生日雷同的概率曾经超过了 50%。这个悖论通知咱们：集体感觉常见的事件在个体中却是常见的。

好了，回到咱们的 hash 抵触，咱们须要构建一个好的 hash 函数来尽量减少数据的抵触。

什么是一个好的散列函数呢？

可能疾速计算，即其工夫复杂度是 O（1）。
尽可能应用最小容量的散列表，
尽可能平均地将键扩散到不同的基地址∈[0..M-1]，
尽可能减少碰撞。

在探讨散列函数的实现之前，让咱们探讨现实的状况：完满的散列函数。

完满的散列函数是键和散列值之间的一对一映射，即基本不存在抵触。当然这种状况是十分少见的，如果咱们当时晓得了散列函数中要存储的 key，还是能够办到的。

好了，接下来咱们讨论一下 hash 中解决抵触的几种常见的办法。

先给出线性探测的公式：i 形容为 i =（base + step * 1）%M，其中 base 是键 v 的散列值，即 h（v），step 是从 1 开始的线性探测步骤。

线性探测的探测序列能够正式形容如下：

h（v）// 基地址
（h（v）+ 1 * 1）%M // 第一个探测步骤，如果产生碰撞
（h（v）+ 2 * 1）%M // 第二次探测步骤，如果仍有碰撞
（h（v）+ 3 * 1）%M // 第三次探测步骤，如果仍有抵触
…
（h（v）+ k * 1）%M // 第 k 个探测步骤等 …

先看个例子，下面的数组中，咱们的基数是 9，数组中曾经有 1，3，5 这三个元素。

当初咱们须要插入 10 和 12，依据计算 10 和 12 的 hash 值是 1 和 3，然而 1 和 3 当初曾经有数据了，那么须要线性向前探测一位，最终插入在 1 和 3 的前面。

下面是删除 10 的例子，同样的先计算 10 的 hash 值 =1，而后判断 1 的地位元素是不是 10，不是 10 的话，向前线性探测。

看下线性探测的要害代码：

    // 插入节点
    void insertNode(int key, int value)
    {HashNode temp = new HashNode(key, value);

        // 获取 key 的 hashcode
        int hashIndex = hashCode(key);

        //find next free space
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex++;
            hashIndex %= capacity;
        }
        // 插入新节点，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {size++;}
        // 将新节点插入数组
        hashNodes[hashIndex] = temp;
    }

如果咱们把具备雷同 h(v) 地址的间断存储空间叫做 clusters 的话，线性探测有很大的可能会创立大型主 clusters，这会减少搜寻（v）/ 插入（v）/ 删除（v）操作的运行工夫。

为了解决这个问题，咱们引入了二次探测。

先给出二次探测的公式：i 形容为 i =（base + step * step）%M，其中 base 是键 v 的散列值，即 h（v），step 是从 1 开始的线性探测步骤。

h（v）// 基地址
（h（v）+ 1 * 1）%M // 第一个探测步骤，如果产生碰撞
（h（v）+ 2 * 2）%M // 第 2 次探测步骤，如果仍有抵触
（h（v）+ 3 * 3）%M // 第三次探测步骤，如果仍有抵触
…
（h（v）+ k * k）%M // 第 k 个探测步骤等 …

就是这样，探针依照二次方跳转，依据须要盘绕哈希表。

看一个二次探测的例子，下面的例子中咱们曾经有 38，3 和 18 这三个元素了。当初要向外面插入 10 和 12。大家能够自行钻研下探测的门路。

再看一个二次摸索删除节点的例子。

看下二次探测的要害代码：

    // 插入节点
    void insertNode(int key, int value)
    {HashNode temp = new HashNode(key, value);

        // 获取 key 的 hashcode
        int hashIndex = hashCode(key);

        //find next free space
        int i=1;
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {
            hashIndex=hashIndex+i*i;
            hashIndex %= capacity;
            i++;
        }

        // 插入新节点，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {size++;}
        // 将新节点插入数组
        hashNodes[hashIndex] = temp;
    }

在二次探测中，群集（clusters）沿着探测门路造成，而不是像线性探测那样围绕基地址造成。这些群集称为次级群集（Secondary Clusters）。
因为在所有密钥的探测中应用雷同的模式，所以造成次级群集。

二次探测中的次级群集不如线性探测中的主群集那样蹩脚，因为实践上散列函数实践上应该首先将键扩散到不同的基地址∈[0..M-1] 中。

为了缩小次要和主要 clusters，咱们引入了双倍散列。

先给出双倍散列的公式：i 形容为 i =（base + step * h2(v)）%M，其中 base 是键 v 的散列值，即 h（v），step 是从 1 开始的线性探测步骤。

h（v）// 基地址
（h（v）+ 1 * h2（v））%M // 第一个探测步骤，如果有碰撞
（h（v）+ 2 * h2（v））%M // 第 2 次探测步骤，如果仍有抵触
（h（v）+ 3 * h2（v））%M // 第三次探测步骤，如果仍有抵触
…
（h（v）+ k * h2（v））%M // 第 k 个探测步骤等 …

就是这样，探测器依据第二个散列函数 h2（v）的值跳转，依据须要盘绕散列表。

看下双倍散列的要害代码：

    // 插入节点
    void insertNode(int key, int value)
    {HashNode temp = new HashNode(key, value);

        // 获取 key 的 hashcode
        int hashIndex = hash1(key);

        //find next free space
        int i=1;
        while(hashNodes[hashIndex] != null && hashNodes[hashIndex].key != key
            && hashNodes[hashIndex].key != -1)
        {hashIndex=hashIndex+i*hash2(key);
            hashIndex %= capacity;
            i++;
        }

        // 插入新节点，size+1
        if(hashNodes[hashIndex] == null || hashNodes[hashIndex].key == -1) {size++;}
        // 将新节点插入数组
        hashNodes[hashIndex] = temp;
    }

如果 h2（v）= 1，则双散列（Double Hashing）的工作形式与线性探测（Linear Probing）完全相同。所以咱们通常心愿 h2（v）> 1 来防止主聚类。

如果 h2（v）= 0，那么 Double Hashing 将会不起作用。

通常对于整数键，h2（v）= M’ – v%M’ 其中 M ’ 是一个小于 M 的质数。这使得 h2（v）∈[1..M’]。

二次散列函数的应用使得实践上难以产生次要或主要群集问题。

拆散链接法（SC）抵触解决技术很简略。如果两个键 a 和 b 都具备雷同的散列值 i，那么这两个键会以链表的模式附加在要插入的地位。

因为键（keys）将被插入的中央齐全依赖于散列函数自身，因而咱们也称拆散链接法为关闭寻址抵触解决技术。

下面是拆散链接插入的例子，向现有的 hashMap 中插入 12 和 3 这两个元素。

下面是拆散链接删除的例子，从链接中删除 10 这个元素。

看下拆散链接的要害代码：

 // 增加元素
    public void add(int key,int value)
    {int index=hashCode(key);
        HashNode head=hashNodes[index];
        HashNode toAdd=new HashNode(key,value);
        if(head==null)
        {hashNodes[index]= toAdd;
            size++;
        }
        else
        {while(head!=null)
            {if(head.key == key)
                {
                    head.value=value;
                    size++;
                    break;
                }
                head=head.next;
            }
            if(head==null)
            {head=hashNodes[index];
                toAdd.next=head;
                hashNodes[index]= toAdd;
                size++;
            }
        }
        // 动静扩容
        if((1.0*size)/capacity>0.7)
        {HashNode[] tmp=hashNodes;
            hashNodes=new HashNode[capacity*2];
            capacity=2*capacity;
            for(HashNode headNode:tmp)
            {while(headNode!=null)
                {add(headNode.key, headNode.value);
                    headNode=headNode.next;
                }
            }
        }

当负载因子 α 变高时，哈希表的性能会升高。对于（规范）二次探测抵触解决办法，当哈希表的 α > 0.5 时，插入可能失败。
如果产生这种状况，咱们能够从新散列（rehash）。咱们用一个新的散列函数构建另一个大概两倍的散列表。咱们遍历原始哈希表中的所有键，从新计算新的哈希值，而后将键值从新插入新的更大的哈希表中，最初删除较早的较小哈希表。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/14-algorithm-hashtable/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！

关于算法:看动画学算法之hashtable

简介

散列表的要害概念

数组和散列表

数组的问题

hash 的问题

线性探测

二次探测

双倍散列

拆散链接

rehash