在这里没有新的原创性的东西。该部分内容主要取材于《软件设计师教程》部分的内容。
我想强调一种数据结构，散列表。它是基于快速存取的角度设计的，也是一种典型的“空间换时间”的做法。顾名思义，该数据结构可以理解为一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙。也就是说，比如我们存储70个元素，但我们可能为这70个元素申请了100个元素的空间。70/100=0.7，这个数字称为负载因子。我们之所以这样做，也是为了“快速存取”的目的。我们基于一种结果尽可能随机平均分布的固定函数H为每个元素安排存储位置，这样就可以避免遍历性质的线性搜索，以达到快速存取。但是由于此随机性，也必然导致一个问题就是冲突。所谓冲突，即两个元素通过散列函数H得到的地址相同，那么这两个元素称为“同义词”。这类似于70个人去一个有100个椅子的饭店吃饭。散列函数的计算结果是一个存储单位地址，每个存储单位称为“桶”。设一个散列表有m个桶，则散列函数的值域应为[0,m-1]。
解决冲突是一个复杂问题。冲突主要取决于：（1）散列函数，一个好的散列函数的值应尽可能平均分布。（2）处理冲突方法。（3）负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。
解决冲突的办法：
（1）线性探查法：冲突后，线性向前试探，找到最近的一个空位置。缺点是会出现堆积现象。存取时，可能不是同义词的词也位于探查序列，影响效率。
（2）双散列函数法：在位置d冲突后，再次使用另一个散列函数产生一个与散列表桶容量m互质的数c，依次试探(d+n*c)%m，使探查序列跳跃式分布。
下面例子，为c语言一共32个关键字建立散列表，为简单每个桶的容量为1，取负载因子=0.7，因此散列表大小32/0.7=47。双散列函数解决冲突，补偿函数H2的基数取和47互质的数为43。
主要散列函数H1，取每三个字母为一段，每个字母占据一个字节，折叠累加，取余算法。H2取每两个字母为一段叠加。
Code
#define P1 47
#define P2 43
/* Compute Hash */
int GetHashCode(char *key,int iSection,int iBase, int offset)
{
long k=0,d;
int c;
while(*key)
{
for(d=0,c=0; *key != '\0' && c < iSection; c++)
{
d=(d<<8)+(*key++);
}
k+=d;
}
return (k % iBase + offset);
}
/* Double Hash Function */
int H1(char *key)
{
return GetHashCode(key, 3, P1, 0);
}
int H2(char *key)
{
return GetHashCode(key, 2, P2, 1);
}
32个关键字，注意，volatile可能是使用不多的一个关键字，指示变量是易变的，禁止编译器对取值进行优化。
Code
char tbl[N][LEN];
char *kWord[]=
{
"auto", "break", "case", "char", "const",
"continue", "default", "do", "double", "else",
"enum", "extern", "float", "for", "goto",
"if", "int", "long", "register", "return",
"short", "signed", "sizeof", "static", "struct",
"switch", "typedef", "union", "unsigned", "void",
"volatile", "while"
};
对散列表进行存储的操作代码。查找代码是类似的。用count数组记录每个位置的冲突次数。
Code
for(i=0;i< sizeof(kWord)/sizeof(kWord[0]); i++)
{
pos= H1(kWord[i]);
c = H2(kWord[i]);
while(tbl[pos][0]!='\0' && strcmp(tbl[pos],kWord[i]))
{
count[pos]++;
pos=(pos+c)%N;
printf(",%d",pos);
}
strcpy(tbl[pos],kWord[i]);
}
------------------------------------------------------------
存储时，每个元素的探查序列如下（数字为数组元素索引值）：
auto : 12
break : 11
case : 40
char : 41
const : 33
continue : 45
default : 37
do : 2
double : 15
else : 25
enum : 30
extern : 34
float : 23
for : 4
goto : 41,37,33,29
if : 4,26
int : 39
long : 23,13
register : 28
return : 16
short : 13,25,37,2,14
signed : 25,0
sizeof : 0,43
static : 18
struct : 38
switch : 15,18,21
typedef : 26,7
union : 6
unsigned : 11,38,18,45,25,5
void : 7,31
volatile : 33,17
while : 32
可见，最长的探查序列为6次。
-----------------------------------------------------
各元素在散列表中的分布如下：
0: signed 2: do 4: for 5: unsigned 6: union
7: typedef 11: break 12: auto 13: long 14: short
15: double 16: return 17: volatile 18: static 21: switch
23: float 25: else 26: if 28: register 29: goto
30: enum 31: void 32: while 33: const 34: extern
37: default 38: struct 39: int 40: case 41: char
43: sizeof 45: continue
存在冲突的位置的冲突计数如下：
count[ 0]=1 count[ 2]=1 count[ 4]=1 count[ 7]=1 count[11]=1
count[13]=1 count[15]=1 count[18]=2 count[23]=1 count[25]=3
count[26]=1 count[33]=2 count[37]=2 count[38]=1 count[41]=1
count[45]=1