定义一个杂凑表类，要求用数组存放杂凑表元素，以字符串作关键字存放和查找表元素，并提供用于插入、查询和删除杂凑表元素的public函数成员。

//这是类的定义

include

class HASH
{
class NODE
{
int value;
NODE *next;
public:
int getvalue(){return value;}
NODE *getnext{return next;}
NODE *setnext(NODE *n){next=n;return this;}
NODE(int v,NODE *n){value=v;next=n}
~NODE(){if(next)delete next;}
}
struct BARREL{char *s;NODE n;}h;
int c;
const int t;
public:
HASH(int m);
NODE *lookup(const char *s,int v);
int insert(const char *s,int v);
int remove(const char *s,int v);
~HASH();
};
//我要把成员函数写完整，能作出一个main来运行这个类啊.
//帮我把成员函数定义一下！谢谢了！

Hash表有很多种实现方法，主要是解决hashcode冲突的时候的方法不一样造成的差别。
我以前写过一个链接法的哈希表，给你做参考吧。

include

/* Model Name : 哈希表

Author : Tang Qiao @ Beijing Normal University
Time & Date: 2006.10.18 10:47 AM
Description: 哈希表。
使用时需要改写hash函数。
v[]数组的内容需要改成需要的结构体
只需要改 type 为T的地方
M 为整个 hash 值的范围 ,可大可小，
size为哈希表一共可以存下的数据，必须保证足够大 */

struct hashtable
{
#define M 9997
#define T int
// M 要用大质数，1811, 5087, 10657, 50503, 100109, 500119
int n;
int f[M], *next;
T *v;
// v数组存放key对应的value,根据具体情况可以换成结构体类型数组
// f数组指出hash值为i的数据的第一个数据，存放在 v数组的下标为f[i]的数据中，如果为0表示不存在
// next数组指出在v数组中, v[i]的下一个元素的下标为next[i] , 如果为0表示不存在
hashtable(int size)
{
n = 0;
v = new int[size+1]; // 下标从1开始使用
next = new int[size+1];
memset(f, 0, sizeof(f));
}
int hash(T a)
{
return a%M;
}
int ELFhash(char key) //字符串用的ELF哈希 { unsigned long h=0, g; while (key)
{
h = (h<<4)+(*key++); g = h & 0xf0000000L; if (g) h ^= g>>24;
h &= ~g;
}
return h%M;
}
int find(T x)
{
int p=f[ hash(x) ];
while (p)
if (v

== x) return p;
else p = next

;
return 0; // 0代表没有找到
}
void insert(T x)
{
int p = hash(x);
v[++n] = x; // 将数据加入v数组
next[n] = f

; // 新节点的next指向原头结点
f

= n; // 头结点指向新的头
}
};

int main()
{

return 0;

}

总结一下字符串哈希：

// RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;

     while (*str)
     {
             hash = hash * a + (*str++);
             a *= b;
     }

     return (hash & 0x7FFFFFFF);

}

// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;

     while (*str)
     {
             hash ^= ((hash << 5) + (*str++) + (hash >> 2));
     }

     return (hash & 0x7FFFFFFF);

}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) *
8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3)
/ 4);
unsigned int OneEighth = (unsigned int)(BitsInUnignedInt / 8);

     unsigned int HighBits          = (unsigned int)(0xFFFFFFFF) << (BitsInU

nignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;

     while (*str)
     {
             hash = (hash << OneEighth) + (*str++);
             if ((test = hash & HighBits) != 0)
             {
                     hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits)

);
}
}

     return (hash & 0x7FFFFFFF);

}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;

     while (*str)
     {
             hash = (hash << 4) + (*str++);
             if ((x = hash & 0xF0000000L) != 0)
             {
                     hash ^= (x >> 24);
                     hash &= ~x;
             }
     }

     return (hash & 0x7FFFFFFF);

}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;

     while (*str)
     {
             hash = hash * seed + (*str++);
     }

     return (hash & 0x7FFFFFFF);

}

// SDBM Hash Function
unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;

     while (*str)
     {
             hash = (*str++) + (hash << 6) + (hash << 16) - hash;
     }

     return (hash & 0x7FFFFFFF);

}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;

     while (*str)
     {
             hash += (hash << 5) + (*str++);
     }

     return (hash & 0x7FFFFFFF);

}
// AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash = 0;
int i;
for (i=0; *str; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ (str++) ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ (str++) ^ (hash >> 5)));
}
}
return (hash & 0x7FFFFFFF);

}

一般说来哈希算法就是一个不可逆的函数.
假设D是定义域(输入),R是值域(输出),通常D中的元素有无限个,R一般是自然数集合的一个子集.
一个好的哈希算法,总希望使得在值域中比较均匀,总希望能够体现输入的特征,在输入一个上的振动下输入就会变化很大.
而显然的是值域的较小,因此不可避免的有冲突,也就是说不同的输入a,b有hash(a)=hash(b).
所以有很多解决冲突的办法.
比如把同一个哈希值的元素放在一起构成一个表.
还有的就是开放寻址,去试探下一个位置.
还有的就是在冲突的时候再次使用另一个哈希函数.
有的是使用哈希函数集
…
最最简单的一个哈希函数就是取一个质数,然后在这个质数的的剩余系上作一次乘法和加法运算…在产生冲突的时候换一个乘子和加数…

加密狗算法-哈希表(杂凑表)c++实现

include

include

include

include

}

发表评论取消回复