随感而发

杂七杂八

统计

留言簿(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 阅读(1317) 评论(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   知识库   博问   管理