## 1. 分离链接法

Find和Insert是散列表的关键操作

• Find：通过散列函数计算出散列值，找到相应的链表，剩下的就是链表的遍历操作
• Insert：先使用Find例程，根据查找结果，决定是否需要插入到链表中，将之插入到头节点后的第一个位置

``````int hash(int key, int size){
return key%size;
}

Hash Init(int Size){
Hash H;
H = malloc(sizeof(struct HashTable));
H->Size = Size;
//H->List = malloc(sizeof(Position)*H->Size);
H->List = malloc(sizeof(struct ListNode)*H->Size);
for (int i = 0; i < H->Size; ++i) {
H->List[i] = malloc(sizeof(struct ListNode));
H->List[i]->Next = NULL;
}
return H;
}

Position Find(int key, Hash H){
Position P;
Position L;
L = H->List[hash(key, H->Size)];
P = L->Next;
while(P && P->Elem != key){
P = P->Next;
}
return P;
}

void Insert(int key, Hash H){
Position P,NewCell;
Position L;
L = H->List[hash(key,H->Size)];
P = Find(key,H);
if (P == NULL){
NewCell = malloc(sizeof(struct ListNode));
NewCell->Elem = key;
NewCell->Next = L->Next;
L->Next = NewCell;
}
}
``````

``````H->List = malloc(sizeof(struct ListNode)*H->Size);
for (int i = 0; i < H->Size; ++i) {
H->List[i] = malloc(sizeof(struct ListNode));
H->List[i]->Next = NULL;
}
``````

``````H->List = malloc(sizeof(struct ListNode)*H->Size);
for (int i = 0; i < H->Size; ++i) {
H->List[i]->Next = NULL;
}
``````

``````It means your program has tried to access memory that doesn't belong to it. Basically, you have a pointer that contains an invalid value somewhere in your code - a common source of this error is dereferencing a NULL pointer.
``````

## 2. 开放定址法

1. 线性探测法 F(i) = i
2. 平方探测法 F(i) = i^2
3. 双散列 F(i) = i * hash2(X)(注意和再散列的区别:将散列表大小改变)

``````HashTable Init(int Size){
HashTable H;
H = malloc(sizeof(struct HashTbl));
H->Size = Size;
H->Array = malloc(sizeof(Cell) * H->Size);
for (int i = 0; i < H->Size; ++i) {
H->Array[i].Info = Empty;
}
return H;
}
``````

``````int Find(int key, HashTable H){
int CurrentPos;
int CollisionNum = 0;
CurrentPos = Hash(key, H->Size);
while(H->Array[CurrentPos].Info != Empty && H->Array[CurrentPos].Elem != key){
CollisionNum++;
//      CurrentPos += CollisionNum;              //针对线性探测
CurrentPos += 2*CollisionNum - 1;        //针对平方探测
//      CurrentPos += CollisionNum * hash2(key,H->Size); //针对双散列
if (CurrentPos>=H->Size)
CurrentPos -= H->Size;
}
return CurrentPos;
}
``````

``````void Insert(int key, HashTable H){
int Position;
Position = Find(key,H);
if (H->Array[Position].Info != Legitimate){
H->Array[Position].Elem = key;
H->Array[Position].Info = Legitimate;
}
}
``````

## 3. 利用Hash表实现多项式乘法

2个链表每一项相乘时时间复杂度是 O(MN),消耗 O(1) 插入到Hash表中

``````HashTable insert(ElementType key, HashTable h){
int Pos;
Pos = find(key,h);
if(h->Cells[Pos].info == Legitimate){
h->Cells[Pos].element.Cof += key.Cof;
}else if(h->Cells[Pos].info == Empty){
h->Cells[Pos].element = key;
h->Cells[Pos].info = Legitimate;
h->currentNum ++;
}
}
``````

``````for (Position_list P1 = Poly1->Next; P1 != NULL; P1 = P1->Next) {
for (Position_list P2 = Poly2->Next; P2 != NULL; P2 = P2->Next) {
T.Exp = P1->Element.Exp + P2->Element.Exp;
T.Cof = P1->Element.Cof * P2->Element.Cof;
insert(T, H);
}
}
``````

``````    Another method of implementing these operations is to use a search tree instead of a hash table; a balanced tree is required because elements are inserted in the tree with too much order. A splay tree might be particularly well suited for this type of a problem because it does well with sequential accesses. Comparing the different ways of solving the problem is a good programming assignment.
``````

## 4. Hash表改进字谜程序

``````//顺时针从右旋转
int x[8] = { 0,1,1,1,0,-1,-1,-1 };
int y[8] = { 1,1,0,-1,-1,-1,0,1 };
``````

`````` for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
for (int d = 0; d < 8; d++) {
string s;
int rr = row;
int cc = col;
for (int count = 1; count <= n; count++) {
s += table[rr][cc];
rr += x[d];
cc += y[d];
Position pos = find(s.c_str(), h);
if(isLegitimate(pos,h))
cout<<s.c_str()<<endl;
}
}
}
}
``````

``````    for (int count = 1; count <= n; count++) {//长度
s += table[rr][cc];
rr += x[d];
cc += y[d];
Position pos = find(s.c_str(), s.length(), h);
if (isLegitimate(pos, h) && retrive(pos, h).info == word)
printf("%s\n", s.c_str());
else if (!isLegitimate(pos, h)) {//找不到前缀
break;//找不到，换方向
}
``````