散列表

• 2020 年 9 月 15 日
• 笔记
• 话说算法

　　如果所有的键都是小整数，我们可以使用一个数组来实现无序的符号表，将键作为数组的索引而数组中键 i 处存储的就是它对应的值。散列表就是用来处理这种情况，它是简易方法的扩展并能够处理更加复杂的类型的键。我们需要用算术操作将键转换为数组的索引来访问数组中的键值对。

　　使用散列表的查找算法分为两步。第一步是用散列函数将被查找的键转换为数组的一个索引理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或多个键都会散列到相同的索引值的情况。因此散列查找的第二步是一个处理碰撞冲突的过程。解决碰撞的方法：拉链法和线性探测法。

　　散列表是算法在时间和空间上作出权衡的经典例子。如果没有内存限制，我们可以直接将键直接作为（可能超大）数组的索引，那么所有查找操作只需访问一次即可。另一方面，如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需很少的内存。而散列表使用了适度的空间和时间并在两个极端之间找到了一种平衡。我们只需要调整散列算法的参数就可以在空间和时间之间作出取舍。

　　使用散列表可以实现在一般应用中（均摊后）常数级别的查找和插入操作的符号表。这使得它在很多情况下成为实现简单符号表的最佳选择。

　　1.散列函数

　　散列算法的第一个问题就是散列函数的计算，这个过程会将键转化为数组的索引。如果我们有一个能够保存 M 个键值对的数组，那么我们就需要一个能够将任意键转化为数组范围内的索引（[0, M-1] 范围内的整数）的散列函数。我们要找的散列函数应该易于计算并且能够均匀分布所有的键，即对于任意键，0 到 M-1 之间的每个整数都有相等的可能性与之对应（与键无关）。要理解散列，就首先要思考如何去实现一个散列函数。

　　散列函数和键的类型有关系。严格地说，对于每种类型的键都需要一个与之对应的散列函数。如果键是一个数，比如社会保险号，我们就可以直接使用这个数；如果键是一个字符串，比如一个人的名字，我们就需要将这个字符串转化为一个数；如果键含有多个部分，比如邮件地址，我们需要用某种方法将这些部分结合起来。

　　假设我们有一个应用程序，其中的键是美国的社会保险号。诸如123-45-6789之类的社会保险号是分为三个字段的9位数字。第一个字段标识 地理区域 发出号码的位置（例如，第一个字段为035的号码来自罗德岛，而第一个字段为214的号码来自马里兰州），其他两个字段标识个人。有十亿个不同的社会保险号，但是假设我们的应用程序只需要处理几百个密钥，那么我们就可以使用大小为M = 1000的哈希表。实现哈希函数的一种可能方法是使用三个密钥中的数字。使用右侧字段中的三位数字可能比使用左侧字段中的三位数字更可取（因为客户在地理区域上可能分布不均），但是更好的方法是使用所有九位数字一个int值，然后考虑整数的哈希函数。

　　正整数

　　将整数散列最常用方法是除留余数法。我们选择大小为素数 M 的数组，对于任意正整数 k ，计算 k 除以 M 的余数。这个函数的计算简单并且能有效地将键散布在 0 到 M-1 的范围内。如果 M 不是素数，我们可能无法利用键中包含的所有信息，可能导致无法均匀地散列散列值。例如，如果键是十进制数而 M 为 10^k ，那么我们只能利用键的后 k 位。 但如果使用素数 97 ，散列值的分布显然会更好（一个离100更远的素数会更好）。

　　浮点数

　　如果键是介于0和1之间的实数，我们可以乘以M并四舍五入为最接近的整数以获得介于0和M-1之间的索引。尽管很直观，但是这种方法是有缺陷的，因为它给按键的最高有效位赋予了更大的权重。最低有效位不起作用。解决这种情况的一种方法是将键表示位二进制数然后再使用除留余数法。

　　字符串

　　除留余数法也可以处理较长的键，如字符串，我们只需将它们当作大整数即可：

int hash = 0;
for(int i = 0;i < s.Length;i++)
{
     hash = (R * hash + s.CharAt(i)) % M;  
}

　　如果 R 比任何字符的值都大，这种计算相当于将字符串当作一个 N 位的 R 进制值，将它除以 M 并取余。一种叫做 Horner 方法的经典算法用 N 次乘法，加法和取余来计算一个字符串的散列值。只要 R 足够小（如 31），不造成溢出，那么结果就能落在 0 至 M-1 之内。

　　组合键

　　如果键类型具有多个整数字段，则通常可以按照刚才针对String值所述的方式将它们混合在一起。

　　将 HashCode() 的返回值转化为一个数组索引

　　由于我们的目标是数组索引，而不是32位整数，因此我们 在实现中将 HashCode() 和除留余数法结合，以产生0到M-1之间的整数：

private int Hash(Key x)
{
     return (x.HashCode() & 0x7fffffff) % M;  
}

　　这段代码会将符号位屏蔽（将一个 32 位整数变为一个 31 位非负整数），然后用除留余数法。在使用这样的代码时我们一般会将数组的大小 M 取为素数以充分利用原散列值的所有位。

　　自定义的 HashCode 

　　自定义的 HashCode() 需要将键平均地散布为所有可能的 32 位整数。也就是说，对于任意对象 x ，调用 x.HashCode() 有均等的机会得到 2^32 个不同整数中的任意一个 32 位整数值。更简单的方法：对实例变量使用hashCode（）方法将每个实例变量转换为32位int值，然后进行算术运算。

public class Transaction
    {
        private string who;
        private string when;
        private double amount;

        public int HashCode()
        {
            int hash = 17;
            hash = 31 * hash + who.GetHashCode();
            hash = 31 * hash + when.GetHashCode();
            hash = 31 * hash + amount.GetHashCode();
            return hash;
        }
    }

　　系数的具体值（这里是 31）并不是很重要。

　　软缓存

　　如果散列值的计算很耗时，那么我们可以将每个键的散列值缓存起来。第一次调用 HashCode() 时，我们需要计算对象的散列值，但之后可以直接返回缓存。

　　总的来说，要为一个数据类型实现一个优秀的散列方法需要满足三个条件：

　　一致性：等价的键必然产生相等的散列值；

　　高效性：计算简便；

　　均匀性：均匀地散列所有的键。

　　在有性能要求时应该谨慎使用散列，因为糟糕的散列函数经常是性能问题的罪魁祸首。保证均匀性的最好办法也许就是保证键的每一位都在散列值的计算中起到了相同的作用。实现散列函数最常见的错误也许就是忽略了键的高位。无论散列函数的实现是什么，当性能很重要时应该测试所使用的散列函数：

　　计算散列函数和比较两个键，哪个耗时更多？

　　你的散列函数能够将一组键均匀地散布在 0到 M-1之间吗？

　 用简单的实现测试这些问题能够预防未来的悲剧。

　　这些讨论的背后是我们在使用散列时作出一个重要的假设（均匀散列假设），我们使用的散列函数能够均匀并独立地将所有键散布于 0 到 M-1 之间。这个假设是一个我们实际上无法达到的理想模型，但它是我们实现散列函数时的指导思想。原因有两点：一是设计散列函数时尽量避免随意指定参数以防止大量的碰撞，这是我们的重要目标；二是它提示我们使用数学分析来预测散列算法的性能并在实验中进行验证。

　　2.基于拉链法的散列表

　　一个散列函数能够将键转化为数组索引。散列算法的第二步是碰撞处理，也就是处理两个或多个键的散列值相同的情况。一种直接的方法是将大小为 M 的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对，这种方法称为拉链法。

　　这个方法的基本思想就是选择足够大的 M ，使得所有链表都尽可能短以保证高效的查找。查找分两步：首先根据散列值找到对应的链表，然后沿着链表顺序查找对应的键。

　　拉链法的一种简单实现方法是，为 M 个元素分别构建符号表来保存散列到这里的键，可以使用之前查找树的代码。

　　因为我们要用 M 条链表保存 N 个键，无论键在各个链表中额分布如何，链表的平均长度肯定是 N/M。

public class SeparateChainingHashST<Key,Value>
    {
        private int N;//键值总对数
        private int M;//散列表的大小
        private SequentialSearchST<Key, Value>[] ST;//存放链表对象的数组

        public SeparateChainingHashST(int M)
        {
            this.M = M;
            ST = new SequentialSearchST<Key, Value>()[M];
            for (var i = 0; i < M; i++)
            {
                ST[i] = new SequentialSearchST<Key, Value>();
            }
        }

        private int Hash(Key key)
        {
            return (key.GetHashCode() & 0x7fffffff) % M;
        }

        public Value Get(Key key)
        {
            return ST[Hash(key)].Get(key);
        }

        public void Put(Key key, Value value)
        {
            ST[Hash(key)].Put(key,value);
        }
    }

　　当你能预知所需要的符号表的大小时，这段短小的方案能够得到不错的性能。一种更可靠的方案是动态调整数组的大小。

　　在一张含有 M 条链表和 N 个键的散列表中，未命中查找和插入操作所需的比较次数为 ～N/M。

　　散列表的大小

　　在实现基于拉链法的散列表时，我们的目标是选择适当的数组大小 M，既不会因为空链表而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。而拉链法的一个好处就是这并不是关键性的选择。如果存入的键多于预期，查找所需的时间只会比选择更大的数组稍长；如果少于预期，虽然空间浪费但查找会非常快。当内存不是很紧张时，可以选择一个足够大的  M，使得查找需要的时间变为常数；当内存紧张时，选择尽量大的 M 仍然能够将性能提高 M倍。另一种方法是动态调整数组的大小以保持短小的链表。

　　删除操作 

　　要删除一个键值对，先用散列值找到含有该键的 SequentialSearchST 对象，然后调用该对象的 Delete 方法。

　　有序性相关的操作 

　　散列最主要的目的在于均匀地将键散布开来，因此在计算散列后键的顺序信息就丢失了。基于拉链法的散列表实现简单，在键的顺序不重要的应用中，他可能是最快的，也是使用最广泛的符号表实现。

　　3.基于线性探测法的散列表　　

　　实现散列表的另一种方式就是用大小为 M 的数组保存 N 个键值对，其中 M > N 。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为开放地址散列表。

　　开放地址散列表中最简单的方法叫做线性探测法：当发生碰撞时（当一个键的散列值已经被另一个不同的键占用），我们直接检查散列表的下一个位置（将索引值加一）。这样的线性探测可能会产生三种结果：

　　　　命中：该位置的键和查找的键相同；

　　　　未命中：键为空（该位置没有键）；

　　　　继续查找：该位置的键和被查找的键不同。

　　我们用散列函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。如果不用则继续查找（将索引增大，到达数组结尾时折回数组的开头），直到找到该键或者遇到一个空元素。我们将检查一个数组位置是否含有被查找的键的操作称为探测。

　　开放地址类的散列表的核心思想是与其将内存用作链表，不如将它们作为在散列表的空元素，这些空元素可以作为查找结束的标志。我们在实现中使用了并行数组，一条保存键，一条保存值。

    public class LinerProbingHashST<Key,Value>
    {
        private int N;//符号表中键值对的总数
        private int M = 16;//线性探测表的大小
        private Key[] keys;//键
        private Value[] values;//值

        public LinerProbingHashST()
        {
            keys = new Key[M];
            values = new Value[M];
        }

        private int Hash(Key key)
        {
            return (key.GetHashCode() & 0x7ffffff) % M;
        }

        public void Put(Key key, Value value)
        {
            if (N >= M / 2)
                Resize(2*M);
            int i;
            for (i = Hash(key); keys[i] != null; i = (i + 1) % M)
            {
                if (keys[i].Equals(key))
                {
                    values[i] = value;
                    return;
                }
            }

            keys[i] = key;
            values[i] = value;
            N++;

        }

        public Value Get(Key key)
        {
            for(int i = Hash(key);keys[i] != null;i = (i+1)%M)
            {
                if (keys[i].Equals(key))
                    return values[i];
            }

            return default(Value);
        }

        /// <summary>
        /// 调整数组大小
        /// </summary>
        /// <param name="v"></param>
        private void Resize(int v)
        {
            throw new NotImplementedException();
        }
    }

　　和拉链法一样，开放地址类的散列表的性能也依赖于  α = N/M 的比值，但意义有所不同。我们将 α 称为散列表的使用率。对于基于拉链法的散列表， α 是每条链表的长度，因此一般大于 1 ；对于基于线性探测的散列表， α 是表中已被占有的空间的比例，它是不可能大于 1 的。事实上，在 LinerProbingHashST 中我们不允许 α 达到1（散列表被占满），因为此时未命中的查找会导致无限循环。为了保证性能，会动态调整数组的大小来保证使用率 在 1/8 到 1/2 之间。

　　删除操作

　　如何从基于线性探测的散列表中删除一个键？如果直接将该键所在的位置设为 null 会使得在此位置之后的元素无法被查找。因此我们需要将簇中被删除的右侧的所有键重新插入列表。

public void Delete(Key key)
        {
            if (!keys.Contains(key))
                return;

            int i = Hash(key);
            while (!key.Equals(keys[i]))
                i = (i + 1) % M;
            keys[i] = default(Key);
            values[i] = default(Value);

            i = (i + 1) % M;
            while (keys[i] != null)
            {
                Key keyToRedo = keys[i];
                Value valueToRedo = values[i];
                keys[i] = default(Key);
                values[i] = default(Value);
                N--;//重新插入
                Put(keyToRedo,valueToRedo);
                i = (i + 1) % M;
            }

            N--;
            if (N > 0 && N >= M / 8)
                Resize(M/2);
        }

　　键簇

　　线性探测的平均成本取决于元素再插入数组后聚集成的一组连续的条目，也叫键簇。显然，短小的键簇才能保证较高的效率。随着插入的键越来越多，这个要求很难满足，较长的键簇会越来越多。另外，基于均匀性假设，数组的每个位置都有相同的可能性被插入一个新键，长键簇更长的可能性比短键簇更大，因为新键的散列值无论落在簇中的任何位置都会使簇的长度加一。

　　线性探测法的性能分析

　　尽管最后的结果的形式相对简单，准确分析线性探测法的性能是非常有难度的。

　　在一张大小为 M 并含有 N = α M 个键的基于线性探测的散列表中，，基于均匀性假设，命中和未命中的查找所需的探测次数分别为： ~ 1/2 (1 + (1 / (1 – α )) ) 和  ~ 1/2 (1 + (1 / (1 – α ) ^ 2) )  。特别是当 α 约为 1/2 时，查找命中所需的探测次数约为 3/2 ，未命中所需的约为 5/2 。当 α 趋近于 1 时，这些估计值的精确度会下降，我们会保证散列表的使用率小于 1/2 。下面我们看看动态调整数组大小。

　　调整数组大小

private void Resize(int cap)
{
    LinearProbingHashST<Key,Value> t = new LinearProbingHashST<Key,Value>(cap);
    for(int i = 0;i<M;i++)
    {
         if(keys[i] != null)
         {
             t.Put(keys[i],values[i]);
         }  
    }  

     keys = t.keys;
     values = t.values;
     M = t.M;
}

 　　动态数组可以为我们保证  α 不大于 1/2 。

　　拉链法

　　我们可以使用相同的方法在拉链表中保持较短的链表（平均长度在 2 到 8 之间）：当 N >= 8*M 时，Resize(2*M)；当 N > 0 && N <= 2*M 时 ，Resize( M/2 )。

　　对于拉链法，如果能准确地估计用例所需的散列表的大小，调整数组的工作并不是必需的，只需根据查找耗时和 （1 + N/M）成正比来选取一个适当的 M 即可。而对于线性探测法，调整数组的大小是必需的，因为当用例插入的键值对数量超过预期时它的查找时间不仅会变长，还会在散列表被填满时进入无限循环。

　　均摊分析

　　理论上，当我们动态调整数组大小时，需要找出均摊成本的上限，因为使散列表长度加倍的插入操作需要大量的探测。

　　假设一张散列表能够自己调整数组大小，初始为空。基于均匀性假设，执行任意顺序的 t 次查找，插入和删除操作所需的时间和 t 成正比，所使用的内存量总是在表中键的总数的常数因子范围内。

　　4.内存的使用

　　我们希望将散列表的性能调整到最优，理解它的内存使用情况是非常重要的。我们可以通过估计引用使用数量来粗略计算所需的内存量：除了存储键和值所需的空间之外，我们实现的 SeparateChainingHashST 保存了 M 个 SequentialSearchST 对象和它们的引用。每个 SequentialSearchST 对象需要 16 字节，它的每个引用需要 8 字节。另外还有 N 个 node 对象，每个需要 24 字节以及三个引用（key , value 和 next），比二叉查找树的每个结点还多需要一个引用。在使用动态调整数组大小来保证表的使用率在 1/8 到 1/2 之间的情况下，线性探测使用 4N 到 16N 个引用。对于原始数据类型，这些计算又有所不同。可以看出，根据内存使用来选择散列表的实现并不容易。

　　还有很多关于实现散列表的算法，大多数改进都能降低 时间 – 空间的曲线：在查找耗时相同的情况下使用更少的空间，或使在使用相同空间的情况下进行更快的查找。其他方法包括提供更好的性能保证，如最坏情况下的查找成本；改进散列函数的设计等。

　　拉链法和线性探测的详细比较取决于实现的细节和用例对空间和时间的要求。即使基于性能考虑，选择拉链法而非线性探测法也不一定是合理的。在实践中，两种方法的性能差别主要是因为拉链法为每个键值对都分配了一小块内存而线性探测则为整张表使用了两个很大的数组。对于非常大的散列表，这些做法对内存管理系统的要求也很不同。

　　基于均匀性假设，期望散列表能支持和数组大小无关的常数级别的查找和插入操作是可能的。对于任意的符号表实现，这个期望都是理论上的最优性能。但散列表并非包治百病，因为：

　　　　每种类型的键都需要一个优秀的散列函数；

　　　　性能保证来自于散列函数的质量；

　　　　散列函数的计算可能复杂而且昂贵；

　　　　难以支持有序性相关的符号表操作。