《算法导论》第11章-散列表 11.1-直接寻址表 11.2 散列表
11.1 直接寻址表
1、当关键字全域U比较小的时候，直接寻址比较有效。
2、一个例子：假设一个动态集合，全域U={0,1，，，，m-1}，m不是一个很大的数字，与此同时没有两个元素具有相同的关键字。
（1）我们用一个数组，称为直接寻址表，记为T，其中每个位置称为槽，槽对应U中的每一个关键字（槽k指向的是集合中U中关键字为k的元素，即T[k] = NIL）
（2）几个操作都比较简单——
DIRECT-ADDRESS-SEARCH(T, k)
return T[k]
DIRECT-ADDRESS-INSERT(T, x)
T[x.key]=x
DIRECT-ADDRESS-DELETE(T,x)
T[x.key] = NIL
3、在某些应用中，直接寻址表本身可以存放动态集合里的元素，意思就是不需要指针操作，直接将含有关键字的对象存放在槽里。
11.2 散列表
引入：
1、直接寻址表有很大的缺点：（1）在全域U很大的时候，存储一张这么大的表不是很合适。（2）当实际存储的关键字K在全域U中的比例太小，那么直接寻址表T的大部分空间会浪费掉。
2、在直接寻址的方式下，具有关键字k的元素被放在了槽k中；在散列方式的情况下，利用散列函数h，由关键字k算出槽的位置，比如将U映射到散列表（hash table） T[0…m-1]的槽位上：h ->{0,1…m-1}。这里有两个表述，第一个是具有关键字k的元素被散列槽h(k)上，也可以说h(k)是关键字k的散列值。
1、通过链接法解决冲突
图1中，像第一个浅色槽，说明h(k1) = h(k4)。这些链表中可以是单链表，也可以是双向链表，图中的链表是双链，因为删除操作比较快。
这样操作以后，散列表上的算法就很容易实现。
CHAINED-HASH-INSERT(T,x)
insert x at the head of list T[h(x.key)]
CHAINED-HASH-SEARCH(T,k)
search for an element with key k in list T[h(k)]
CHAINED-HASH-DELETE(T,x)
delete x from the list T[h(x.key)]