技术

散列

参考《数据结构与算法分析（C语言描述）》 第二版 第五章 散列

什么是散列表？

散列表是一种数据结构，它支持对一组元素进行各种操作，不过它只支持二叉查找树所允许的一部分操作。
散列表的实现叫做散列，散列是一种可以用常数时间执行插入、删除和查找的技术，但是它对排序操作是不支持的。

理想的散列表

理想的散列表就是一个包含关键字的，具有固定大小的数组。每个关键字被映射到从 0 到 tableSize-1 这个范围中的某个数，
这个映射叫做散列函数，理想的情况下，任何两个不同的的关键字，映射到不同的单元。我们需要找一个散列函数，使能够在单元
间均匀的分配关键字。

散列函数

如果关键字是整数，那么直接返回 key % tableSize

1
2
3
4
int hash(int key, int tableSize)
{
    return key % tableSize;
}

然而当关键字的取值具有一些不理想的性质时，上面这个散列函数就是一个不好的选择，例如，当tableSize = 10时，关键字都是
个位数为 0 的整数，那么上面这个散列函数返回的值永远是0，也就是说，所有的关键字都被映射到单元0了，这是不好的。为了使
分配的更均匀，tableSize最好为素数。
一般，关键字的的值都是字符串，那么有以下几种方法来实现散列函数

  • 第一种，把字符的ASCII码值加起来，然后再模tableSize。这样的缺点就是当tableSize很大时，分配就不会均匀。
  • 第二种，假设关键字是由三个英文字母组成，那么三个字符有17576种组合（26的三次方），如果表大小是10007，
    这就是一个合理的均匀分配，但是，英文并不是随机组合，三个字幕组成有效的单词大概只有2851个，即使没有冲突，
    也只有表的28%被散列到，所以也是不合适的。
  • 第三种涉及到字符串中所有字符，所以当关键字特别长时，计算会花费过多时间，解决方法就是不计算所有字符，而挑选其中的字符，
    比如只计算奇数位上的字符。

冲突

当两个关键字计算后得出的散列值相同时，就会产生冲突，解决冲突有两种方法：分离链接法 & 开放定址法

分离链接法

该方法将所有散列值相同的元素保留到一个表中，这种方法的缺点就是使用了指针，由于给新单元分配指针需要时间，因此导致算法速度
较慢，另外，它还依赖另一种数据结构（链表）。

开放定址法

开放定址法中如果遇到了冲突，则尝试选择另外的单元，直到找到空的单元为止。

再散列

使用前面两种方法解决冲突时，当表的元素过多时，操作的运行时间将过长，而且insert操作可能失败。解决方案就是扩展表，使表增大
一倍，并使用一个新的散列函数，扫描原表中的元素，重新计算散列值并插入到新表中，这个操作就叫再散列。

可扩散列

fuck，看不懂！

散列表的应用

  • 编译器中使用散列表跟踪源代码声明的变量，这种数据结构叫做符号表。
  • 使用散列表解决图论问题。
  • 游戏编程中
  • 在线拼写检测程序

总结

散列表以常数时间实现insert和find操作，但是当表中元素过多时，表的性能将下降。另外，当关键字的类型以及性质比较特殊时，选择
合适的散列散列函数也会很大程度上影响表的性能。