散列

散列

 

1，基本概念

   散列可以使得插入、删除、查找以常数平均时间进行。

   要高效的应用散列技术，需要注意两个方面：

      一，选择好的散列函数。 散列函数的选择要使得插入的值尽量均匀分布在散列表中。

      二，选择好的解决冲突的方案。 解决冲突的方案有很多种，根据实际情况选择最优的方案。

 

2，散列函数

   通常关键字是字符串，此时要注意选择散列函数。

   typedef int Index;

 

2.1 方法1

   一种散列的方法是把关键字字符串的各个值都加起来，散列函数如下：

   Indext hash(const char *key, int tablesize)

   {

      int hashvalue = 0;

 

      while (*key != '\0')

         hashvalue += *key++;

      return hashvalue % tablesize;

   }

   分析：该方法有自身的缺陷。由于是把字符串相加，我们假设这些关键字最多10个字符。若hash表足够大，比如10007(素数)。

   那么我们可以计算出按照这种方法计算出来的hash表的位置值是在：0到10*127(1270)之间，那么，次表中有1270以后的位置都是空的，显然对于表很长的hash表来说，这不是一个很好的散列函数。

 

长为10007的hash表：

|———————————————————————————————————|

|    被关键词(最大10个字符)占满 |        永远空闲的位置           |

|———————————————————————————————————|

                           1270                              10007 

 

2.2 方法2

   一种稍好的散列函数，该散列函数只使用到了关键字的前3个字符，若关键字的前3个字符都是随机的，那么给散列函数，将会得到一个均匀分布的散列值。

   Index hash(const char *key, int tablesize)

   {

      return(key[0] + 27*key[1]+729*key[3]);

   }

   分析：27是英文字母加上空格，而729是27^2，由于英文字母不是随机的，所以当散列表长度足够大时该函数还是不太合适。

 

2.3 方法3

   一个比较好的散列函数：

   Index hash(const char *key, int table_size)

   {

      unsigned int hash_value = 0;

 

      while (*key!= '\0')

         hash_value = (hash_value << 5) + *key++;

 

      return hash_value%table_size;

   }

   分析：该散列函数把上次计算出来的hash值*32，再和每个关键字相加，能得到较好的均匀分布的效果，但是，当关键字很长时，计算起来可能比较慢。一种改进的方法是只把关键字的奇数位上的字符加起来。

 

小结：散列函数的选择要根据实际情况来选择，主要要使得关键字均匀分布在散列表中，减少冲突的机会。

 

3，如何解决冲突

3.1 分离链表法

3.2 开放地址法

3.3 再散列

3.4 可扩展散列

 

 

4，散列应用

 

5，相关练习

 

 

 

参考资料： 《数据结构与算法分析-C语言描述》

          《 算法导论》