标签: Data-Structures


散列在选取了散列函数后,要解决的问题及时如何解决散列冲突。有2种简单方式,分离链接法和开放定址法

1. 分离链接法

核心思想在于:将散列到同一个散列值的元素放在一个链表中

分离链接散列表:

hash

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;
        }
    }
    

在编写Init时,即申请指针数组和给每个链表的头节点申请空间时的写法

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;
}

单步调试发现错误提示 SIGSEGV (Segmentation fault).

在StackOerFlow上找到如下回答:

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. 开放定址法

不同于分离链接法使用链表,开放定址法在冲突发生时,借助函数 F(i)来选择另外的空单元

  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;
}

这里有一点:平方探测的快速实现,F(i) = F(i-1) +2 * i - 1 , 下一个要探测的单元通过乘2减1确定 在原书上有一句警告提示,切勿改变while(H->Array[CurrentPos].Info != Empty && H->Array[CurrentPos].Elem != key)的测试顺序,个人猜测是从优化角度考虑的

插入

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表改进字谜程序

第一章第一页的字谜问题,将W个单词的 单词表读入散列表中,O(W) 对每一个四元组(行,列,方向,字符数)测试是否有单词出现。散列表的查询 O(1),而方向只有8个,单词的字符数最大数也是个常数,O(R.C)

//顺时针从右旋转
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;
            }
        }
    }
}

改进程序: 通过将每一个单词的W以及W的所有前缀放入Hash表中,可以在查找时,如果确定前缀不在Hash表中,可以提前结束查找

    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;//找不到,换方向  
                }  

总结: 散列表的原理简单,但是用处很大,比如编译器前端中符号表记录变量等,拼写检查程序中的词典散列