在使用数组的时候，下标作为关键字为我们提供了操作的便捷性，此时关键字是连续的。在需要统计一串数字中每个数字各出现多少次时，若数字取值范围较小，可以这样处理:

int a[11];  //数字取值范围1~10
while(cin>>x)
  a[x]++;

但如果取值范围是1~100000或者更大呢？在数字总数不大的情况下不必建立一个可以储存1000000个整数的数组，而是将有限的关键字（数字）进行散列的储存：

map<int,int>m;
while(cin>>x)
  m[x]++;

map把关键字和实际需要储存的数据进行映射，这样需要的储存空间就小得多。

散列方式

在直接寻址方式下，具有关键字k的元素被存放在槽k中。在散列方式下，该元素在槽h(k)中。h是散列函数，它决定关键字k的槽的位置。但不同的关键字可以由散列函数分配到同一个槽中，造成冲突。解决办法有：
链接法(chaining)把散列在同一个槽中的元素都放在一个链表中，散列表中保存这些链表的头指针。
在进行数据查找、增加、删除等操作时时间复杂度只取决于链表长度，因此若所有关键字都被分配至同一个槽中（最坏情况），时间复杂度为O(n)。但一般情况下操作只需O(1)。
开放寻址法(open addressing)将所有元素直接储存在散列表中。由于元素没有和地址的映射关系，在操作者需要查找某元素时需要检查整个散列表。检查的顺序依赖于探查序列，它是散列函数的扩充。
完全散列(perfect hashing)的查询操作在对坏情况也能达到O(1)，十分适合静态储存。它采用两级散列，在最初的散列表中存放数个二次散列表，并且选用合适二次散列表空间防止冲突，选用合适的第一级散列函数使整体储存空间不会过大。

散列函数

散列函数应该使关键字的散列尽可能均匀，使散列值尽可能独立于数据的模式。多数散列函数先将关键字都转化为数字，再进行散列。
除法散列法 取关键字的余数作为结果，需要都除数进行合理设计。
乘法散列法使关键字乘一个常数，取他们乘积的小数部分乘另一个常数，再向下取整。
全域散列法先设定一组散列函数，然后在处理关键字时随机选用函数。无论关键字是怎样的都能保证散列较平均。