《算法导论》第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）

图1 图1中表示的是全域就包含0~10的所有数字，浅色区域代表实际关键字（K）构成的集合，槽中均有指向这些元素的指针；深色区域代表NIL。

（2）几个操作都比较简单——

DIRECT-ADDRESS-SEARCH(T, k)
	return T[k]
1
2

DIRECT-ADDRESS-INSERT(T, x)
	T[x.key]=x
1
2

DIRECT-ADDRESS-DELETE(T,x)
	T[x.key] = NIL
1
2

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的散列值。

图2 在图2 中就反映了这种映射关系，我们可以发现 k2 和 k5被映射到了同一个位置上，称为==冲突==，因为很明显，散列函数缩小了数组，因此这个不可避免。 3、如何减少冲突？ 答：那就让h尽可能随机一点（虽然依旧是一个k对应一个h(k)），后面我们介绍链接法（chaining）和开放寻址法（open addressing）两种方法。

1、通过链接法解决冲突

图1 在链接法中，散列到同一槽的所有元素放在一个链表中，槽j的内部有一个指针，它指向存储所有散列到j的元素的链表的表头；如果不存在这样的元素，则槽j中为NIL。

图1中，像第一个浅色槽，说明h(k1) = h(k4)。这些链表中可以是单链表，也可以是双向链表，图中的链表是双链，因为删除操作比较快。
这样操作以后，散列表上的算法就很容易实现。

CHAINED-HASH-INSERT(T,x)
	insert x at the head of list T[h(x.key)]
1
2

CHAINED-HASH-SEARCH(T,k)
	search for an element with key k in list T[h(k)]
1
2

CHAINED-HASH-DELETE(T,x)
	delete x from the list T[h(x.key)]
1
2