数据结构-散列笔记

散列表查找技术

散列表查找技术的思想主要是，将关键值映射到一个适当的存储位置，使得关键码与存储位置有着一一对应的关系，这样就不需要进行查找，只需要知道关键码，就能得到对应的位置。

散列表、散列函数、散列地址

采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。
将关键码映射为散列表中适当存储位置的函数称为散列函数（hash function），所得的存储位置称为散列地址（hash address）。

散列过程

1. 存储记录时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
2. 查找记录时，通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。

可以看到，散列既是一种存储方法，也是一种查找方法。

散列方法不适用于有多个相同关键码的情况！
散列方法也不适用于范围查找！

散列存储时的问题

如果记录按散列函数计算出的地址加入散列表时产生的冲突，就必须另外再找一个地方在存放它。
散列技术需要考虑的两个主要问题：

1. 散列函数的设计。如何设置一个简单，均匀，存储利用率高的散列函数。
2. 冲突的处理。如何采取合适的处理冲突方法来解决冲突。

散列函数的设计

散列设计一般用于处理关键码来自很大范围的记录，并将这些记录存储在一个有限的散列表中。一般来说，我们希望散列函数能够把记录以相同的概率“散列”到散列表的所有地址空间中。
设计散列函数的原则：

1. 计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。
2. 函数值即散列地址分布均匀。函数值要尽量均匀散步在地址空间，这样才能保证存储空间的有效利用，并减少冲突。

   以上两点往往是矛盾的。如果散列地址均匀性比较好，散列函数的计算就必然要复杂。反之如果散列函数的计算很简单，则均匀性就可能比较差。实际使用中要根据具体情况，选择一个比较合理的方案。

常见的散列函数

1. 直接定址法
   直接定址法的散列函数是关键码的线性函数，即：

   `H(key)` = `a` * `key` + `b` (a、b为常数)
   

2. 除留余数法
   除留余数法的基本思想是：选择某个适当的正整数p，以关键码除于p的余数作为散列地址，即：
   H(key) = key & p
3. 数字分析法
   数字分析法根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。
   数字分析法适用于事先知道关键码的分布且关键码中有若干位分布较均匀的情况。
4. 平分取中法
   平分取中法是对关键码平方后,按散列表大小，去中间的若干位作为散列地址（平方后截取）。之所以这样，是因为一个数平方后，中间的几位分布较均匀，也就是不同的关键码较少有相同的平方后截取，从而冲突发生的概率较少。
5. 折叠法
   折叠法是将关键码从左到右分割成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按散列列表长，取最后几位作为散列地址。通常分为两种叠加方法：
   1. 移位叠加：将各部分的最后一位对齐相加。
   2. 间界叠加：从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。
   • 如key=25346358705
     1. 253+463+587+05
     2. 253+364+587+50(奇数段正序，偶数段反序)