首页 > 代码库 > 哈希(hash) 之插入和查找(链地址法)

哈希(hash) 之插入和查找(链地址法)

一:学些心得

1 getHash函数的设计最牛的是Unix中处理字符串的ELFHash();当然也可以自己写一个比较简单的getHash函数关键在于去mod M的M值,使器均匀的分布(一般是不大于hash_size的某一个素数,接近于2的某次幂);但是有一点需要注意就是返回的hash值必须是正值。

2 处理冲突的方法:链地址法是比较好的方法了(静态动态都可以的);二次哈希(一般是加key值)再探测;或者加1再探测

3 插入和查找以及删除的第一步都是一样的,getHash(),时候存在……

4 对于链表发,插入法包括头插入法(插入操作比较简单,当然其不判断数据的重复插入),和链表尾插入法(稍微复杂一些,边遍历边判断数据的重复与否,和查找类似)

5 虽然比不上c++的STL中的hash_map类,没有他的各种构造函数,以及 = 赋值构造函数;更没有其强大的iterator迭代器,但是本函数基本上实现了hash的主要功能,而且把int 改为T也可以实现类似泛型的功能。

6 请看 哈希(hash) 之 ELFHash 和 静态hash(模拟链接法)  ELHash的实现

    哈希(hash) 之 开放地址法(poj)开放地址法 hash

c++STL Hash_Map 简介

7  下面通过类似于带头结点的list实现的hashmap的链地址法,以牺牲空间来使得代码的操作简介性,哈哈!也许并不可取,请看6中的最后一个连接。

二: 代码实现(注释比较详细,这里就不多说了)

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1003;
typedef struct Hash
{
    int x,y;
    Hash *next;
}Hash;
Hash hashtable[maxn];
// 意义不同,NULL表示指针为空的宏,0是没有任何特殊含义的值。也就是说,
//理论上来讲NULL可以是任意数值,虽然目前所有编译器都将其设为0。
int p[1001][2];
int gethash(const int &x,const int &y)
{
    return (x*x + y*y)%maxn;
}
// 头插入法,并且不判断重复,任何数据都插入,根节点不插入数据即hash[pos].x 如插入数据
void insert(const int &x,const int &y)
{
    int pos = gethash(x,y);
    Hash *tmp = new Hash;
    tmp->x = x;
    tmp->y = y;
    tmp->next = hashtable[pos].next;
    hashtable[pos].next = tmp;
}


bool search(const int &x,const int &y)
{
    int pos = gethash(x,y);
    Hash *tmp = hashtable[pos].next;
    while(tmp!=NULL)
    {
        if(tmp->x==x && tmp->y==y)
            return true;
        tmp = tmp->next;
    }
    return false;// 缺少这句话是不报错的哦,注意非void类型的返回函数的返回形式(一定要有最后的return   )
}
void destroy()
{
    int i;
    Hash *tmp = NULL;// 初试值设置为NULL,根据情况,一般删除的时候,也设置为NULL
    for(i=0;i<maxn;i++)
    {
        while(hashtable[i].next != NULL)
        {
            tmp = hashtable[i].next;
            hashtable[i].next = tmp->next;
            delete tmp;
        }
    }
}


int main()
{
    int n,i,j;
    int x1,y1,x2,y2;
    int ans;
    while(cin >> n && n!=0)
    {
        for(i=0;i<n;i++)
        {
            cin >> p[i][0] >> p[i][1];
            insert(p[i][0], p[i][1]);
        }
        ans = 0;
        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
            {
                x1 = p[i][0] + p[i][1]-p[j][1];
                y1 = p[i][1] + p[j][0]-p[i][0];
                x2 = p[j][0] + p[i][1]-p[j][1];
                y2 = p[j][1] + p[j][0]-p[i][0];
                if(search(x1,y1) && search(x2,y2)) ans ++;


                x1 = p[i][0] + p[j][1]-p[i][1];
                y1 = p[i][1] + p[i][0]-p[j][0];
                x2 = p[j][0] + p[j][1]-p[i][1];
                y2 = p[j][1] + p[i][0]-p[j][0];
                if(search(x1,y1) && search(x2,y2)) ans ++;
            }
        cout << ans/4 << endl;
        destroy();
    }
    return 0;
}

// wei插入法,并且判断重复,重复数据不再插入,根节点不插入数据即hash[pos].x 如插入数据,即带头结点的链表
void insert(const int &x,const int &y)
{
    Hash *p = NULL;
    Hash *tmp = hashtable[gethash(x,y)].next;
    while(tmp!=NULL)
    {
        if(tmp->x==x && tmp->y==y)
            return;
        p = tmp;
        tmp = tmp->next;
    }
    tmp = new Hash;
    tmp->x = x;
    tmp->y = y;
    tmp->next = NULL;
    if(p!=NULL)
        p->next = tmp;
    else// 是第一个节点咯
    hashtable[gethash(x,y)].next = tmp;
}
// 从头到尾搜,当然第一步都是先gethash
bool search(const int &x,const int &y)
{
    Hash *tmp = hashtable[gethash(x,y)].next;
    while(tmp!=NULL)
    {
        if(tmp->x==x && tmp->y==y)
            return true;
        tmp = tmp->next;
    }
    return false;// 缺少这句话是不报错的哦
}


哈希(hash) 之插入和查找(链地址法)