1. 散列表：

1.1 直接寻址表：

1.1 文章

直接寻址表 ： 直接选址表是一个数组T，假设对于一个域{0,1,2,...,m-1} 共有m个值。而数组的存储空间可以覆盖这个域，那么对于值域中的任一个元素k，直接在数组第k个位置来存储，有T[k] = k。寻址的复杂度是1。

1.2 题目：

1.位向量是一个仅包含0和1的数组。长度为m的位向量所占空间要比包含m个指针的数组少得多。如何用一个位向量来表示一个包含不同元素（无卫星数据）的动态集合。字典操作的运行时间是O(1)。

直接寻址有着明显的缺点，（1）为了覆盖全域U，需要很大的存储空间，往往是不现实的。（2）如果关键字域 K 相比于U很小，又会造成大量的空间浪费。

对于直接寻址，具有关键字k的元素存放在槽k内，对于散列表，该元素存放在槽h(k)中，其中h就是散列函数。可以说，一个具有关键字k的元素被散列到了槽h(k)上。h(k)是关键字k的散列值。
由于关键字域相比于全域来讲要小得多，所以必然会有两个不同的key，hash到同一个槽上的情况，这种叫做冲突。解决冲突的方法有：链接法和开放寻址法。