随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

除法散列发解决碰撞的散列表

今天学习了除法散列法解决散列表的碰撞。他的基本思路为:
1. 用一个阀值作为除数,对要求散列值的key除以他,得到的结果就是该key要存放的位置。
2. 注意的是,这个除数一定要选择好,不能太大,太大浪费了空间。也不能太小,太小碰撞太严重。一般选择里2的p次幂最远的质数。因为这样的话散列的效果可能更好。具体论证我也不清楚。
3. 空间的选择,只要除数定下来之后,一般空间就是除数这么大了。
4. 碰撞处理,万一遇到碰撞怎么办,我目前采用的是链表法处理碰撞,就是如果两个key算出的值一样。就把他们用链表的形式连接起来,然后再链接到他们的域中。这个最容易理解的方法了。
基本就这么多了,奉上源代码:
#include <stdio.h>
#include 
<stdlib.h>

//定义保存数据的链表
struct stList
{
    
int nData;    //数据的key,也作为数据
    stList* pNext;
}
;

//散列表的域,保存时数据链表的指针
stList* g_data[702= {0};

//计算关键字的散列值。
int HashFunc(int nKey)
{
    
//用除法散列法求散列值,他的一个思路是
    
//求余,但是除数一定要选好,书上说的最好于2的整数幂不太接近
    
//的质数。具体为什么书上有说明。
    return nKey % 701;
}


//插入数据到散列表中
int InsertData(int nKey)
{
    
//就是选算出算列值,然后就是链表的插入了。
    int nPos = HashFunc(nKey);
    stList
* pTemp = new stList();
    pTemp
->nData = nKey;
    pTemp
->pNext = g_data[nPos];
    g_data[nPos] 
= pTemp;
    
return nPos;
}


int g_MaxFind = -1;    //这个计算最大查找次数的,因为数据很特殊,所以没有看到效果。

bool FindData(int nKey)
{
    
//也是先算出散列值,再对应值处做链表查找。
    int nPos = HashFunc(nKey);
    
int i = 0;
    stList
* pTemp = g_data[nPos];
    
while(pTemp)
    
{
        
++i;
        
if (pTemp->nData == nKey)
        
{
            
if (g_MaxFind < i)
            
{
                g_MaxFind 
= i;
            }

            
return true;
        }

        pTemp 
= pTemp->pNext;
    }


    
//增加了一个算出最大查找次数的比较。多余的。
    if (g_MaxFind < i)
    
{
        g_MaxFind 
= i;
    }


    
return false;
}


int DeleteData(int nKey)
{
    
//先算出散列值,再对对应的区域做链表删除
    int nPos = HashFunc(nKey);
    stList
* pTemp = g_data[nPos];
    stList
* pPre = g_data[nPos];
    
while(pTemp)
    
{
        
if (pTemp->nData == nKey)
        
{
            
            
if (pTemp == g_data[nPos])
            
{
                g_data[nPos] 
= pTemp->pNext;
            }

            
else
            
{
                pPre
->pNext = pTemp->pNext;
            }


            delete pTemp;
            
return nPos;
        }

        pPre 
= pTemp;
        pTemp 
= pTemp->pNext;

    }

    
return -1;
}



int main()
{
    
//插入2000个数,因为太特殊了,所以效果很好。呵呵。
    for (int i = 0; i < 2000++i)
    
{
        InsertData(i);
    }


    
//找这些数据。
    for (int i = 0; i < 2++i)
    
{
        
if (FindData(i))
        
{
            
//printf("%d ", i);
        }

        
else
        
{
            printf(
"Wrong!\n");
        }

    }


    
//输出最大查找次数,是3次,数据太特殊。所以不能说明什么
    
//这个结果是最好的,完全散列在散列表中。碰撞次数最少。
    printf("%d ", g_MaxFind);

    
//删除数据
    for (int i = 0; i < 2000++i)
    
{
        DeleteData(i);
    }


    
//再次查找,跟定时找不到的啦。
    for (int i = 0; i < 2000++i)
    
{
        
if (FindData(i))
        
{
                printf(
"%d Wrong!\n", i);
        }

    }


    system(
"pause");
    
return 0;
}

posted on 2009-05-06 20:19 shongbee2 阅读(1291) 评论(2)  编辑 收藏 引用 所属分类: 数据结构和算法

评论

# re: 除法散列发解决碰撞的散列表 2011-05-20 21:59 shongbee2

不就是hash的一种算法嘛,我还以为。。呵呵。。  回复  更多评论   

# re: 除法散列发解决碰撞的散列表[未登录] 2011-10-12 23:41 方君君

if (pTemp == g_data[nPos])
{
g_data[nPos] = pTemp->pNext;
}
else
这个可以去掉啊.....  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理