今天是开通博客后第一次做算法导论习题呢。。。
首先是算法导论散列表11.1的答案。
11.1-1 假设一动态集合S用一个长度为m的直接寻址表T来表示，请给出一个查找S中最大元素的过程，你所给的过程在最坏情况下的运行时间是多少？
第一题，很简单按照我的理解这题就是没有卫星数据，意味着key值就是数值大小也是下标，那我们就从下往上遍历整个表，直到找到一个非空的slot为止，这很好理解，下标越大值就越大，但是最糟糕情况下就需要O(n)的渐近时间，发生在空表或数据在表头处这种情况。
11.1-2 使用bit vector来做一个没有satellite data的直接寻址表，要求O(1)的字典操作时间。
看到这题想到剑指offer还是编程之美里面的一道题，大意就是需要在一段非常大的不重复整数中寻找一个数有没有，解决方案就是bit vector。
开始分析，首先，先决条件：不重复整数，应该还要正整数，这样的整数在所属集合中独一无二，而每个位在二进制中也是独一无二的，因为位置是不会重合的，所以每一个为对应一个整数，而整个集合使用一个大数组做为存储，假设我们一共拥有1024个整数，并且我们一个字节8各位，那么我们使用char[1024/8] 的数组，然后使用位运算判断每个位的0或1从而确认数据的存在，大致思路就是这样。
可以轻易的得到key/8就是数组的下标，而key%8就是在每个字节中的顺序，由于8为2的幂，我们可以使用位运算key>>3,key&(7)来得到所需要的值
代码如下
#include <iostream>
#include <cmath>
#include <vector>
#include <assert.h>
class BitVector
{
public:
BitVector(int upperLimit=1024)
: Bit(8),
Vector(roundUp(upperLimit)/8),
offset(3)
{
//std::cout<<Vector.capacity()<<std::endl
}
bool find(size_t key)
{
assert(key < 1024);
return Vector[key >> offset] & (1 << (key & (Bit - 1)));
}
void insert(size_t key)
{
assert(key < 1024);
Vector[key >> offset] |= (1 << (key & (Bit - 1)));
}
void remove(size_t key)
{
assert(key < 1024);
Vector[key >> offset] &= ~(1 << (key & (Bit - 1)));
}
private:
// 每个字节位的大小
const size_t Bit;
// 偏移量，也就是lgBit
const size_t offset;
//我们的容器
std::vector<char> Vector;
// 作用是将数字num上调为bytes，这里也就是8的倍数，
// 来源于stl源码解析中对空间适配器的解析一章
static size_t roundUp(size_t num, size_t bytes= 8)
{
return ((num) + bytes - 1)&~(bytes- 1);
}
};
int main()
{
BitVector mBitVector;
for (int i = 1; i <= 30;++i)
{
int num = rand() % 1024;
mBitVector.insert(num);
std::cout << num << std::endl;
}
for (int i = 0; i < 1024;++i)
{
if (mBitVector.find(i))
std::cout << "find " << i << std::endl;
}
return 0;
}在这段代码里我们使用了位向量建立了一个简单的直接寻址表，数据大小为0到1023这1024个数（不是1到1024），
11.1-3如何实现一个字典操作为常量而且拥有重复关键字的直接寻址表。
老实说，这一道题没什么好讲的，摆明了就是让我们预习一下后一节的内容，方法很简单的，就是在每一个寻址表寻的是一个链表而不是一个单纯的数据了，恩，应该还要是双向链表，恩，对，就是11.2的链接法hash，当然如果是11.4的opening address也可以。
11.1-4 星号题，题目不写了，想通了就很简单，既然大数组不能初始化，也就不能直接当寻址表，那么我们就把附加数组当寻址表就好了，题目又告诉你附加数组的大小就是大数组中关键字的多少，那么我们就把真正的地址放在附加数组里，然后大数组中存放附加数组的位置信息。
假设大数组为T，附加数组为S，保存地址信息，并且我们加一个变量为N=关键字数目，现在将S，N初始化为0，一旦我要insert一个数据，比如7好了，那么S[]=sth,然后T[7]=N，然后N++；然后我插入9，S[N]=sth,T[9]=N,N++,一样的流程，然后我们要find，就去查找S[T[key]]是否有效，然后是delete，把S[T[key]]设置为nil就好了，都是常量操作，所以，我们并不是直接使用T作为寻址表，T是一个间接寻址表，T和S，以及数据之间是一个单射关系，如同我们的函数一样，函数名为T，参数为key，操作为S，返回值为data。
———————–以上为11.1章节的答案，接下去是乘法散列法的一些总结
#include<iostream>
#include<string.h>;
#include <assert.h>
#include <time.h>
int a[11];
int hash(int key)
{
// 乘法hash function对于数据较大的情况有非常好的效果
// 但是如果数据较小，在100以内，那么冲突就会非常多
// 甚至出现空槽现象
float A = 0.6180339887f;
int m = 1 << 10;
float temp = static_cast<float>(static_cast<int>(A*key));
int hashKey = floor((A*key - temp)*m);
return hashKey;
}
void distKey(int hashkey)
{
int n = hashkey * 11 / (1024);
assert(n >= 0 && n <= 10);
switch (n)
{
case 0:a[0]++; break;
case 1:a[1]++; break;
case 2:a[2]++; break;
case 3:a[3]++; break;
case 4:a[4]++; break;
case 5:a[5]++; break;
case 6:a[6]++; break;
case 7:a[7]++; break;
case 8:a[8]++; break;
case 9:a[9]++; break;
case 10:a[10]++; break;
default:
break;
}
}
void show()
{
for (int i = 0; i <= 10; ++i)
{
printf("hashKey = %d -- %d : %d\n", 1024 * i / 11, 1024 * (i + 1) / 11, a[i]);
}
}
int main()
{
srand((unsigned int)time(NULL));
memset(a, 0, sizeof(a));
int hashKey;
int key;
int mod = 0;
for (int i = 0; i < 1000000; ++i)
{
while (mod == 0) mod = rand() % 100000;//mod may be zero
key = rand() % 100000000;
key %= mod;
hashKey = hash(key);
distKey(hashKey);
}
show();
return 0;
}
虽说很多地方不如除法散列法，不过还是蛮有优点的，mit公开课上，教授举了一个很好的例子，车轮法，这个乘法散列就好像是一个幸运大转盘一样，你转一次转过了A*360度，比如我的key是500，那么我就把这个轮盘转500次，他会落在哪里？随机性很大，所以这是个不错的hash函数，感觉比除法要好，不过有一个致命的缺点，那就是数据不能太小，而且数据不能太一致（感觉是废话？），数据平均值越小越容易导致每个slot分布不均衡，我的代码在mod小于30，也就是均值低于30的时候基本是每次都有空槽出现，我也不知道怎么回事，应该是和rand函数与时间seed的关系有关，不过均值大于100的话基本是均衡分布，至于A的选择呢，，，虽然不知道为什么老K选他，不过我也觉的黄金比例是个不错的数字。