我们一直在讲哈希，哈希，但是真正用这个数据结构的时候往往采用的是它的简化形式
那么如何构造一个真正的哈希表呢？
首先我们明确一下哈希表是干啥用的，没错就是用来判重和查找的
但是这个判重，我们要规定一下限制范围， 虽然哈希表功能强大但是还是有局限性
哈希表适合那种数据特别多，但是对于每一个数据，它的值不是很大的情况
在使用哈希表之前，我们先来进行一个科普，C++的int转string与string转int
在这里最好不用调用什么函数，你不懂它
string转int istringstream is("12"); //构造输入字符串流，流的内容初始化为“12”的字符串 int i; is >> i; //从is流中读入一个int整数存入i中 int转string ostringstream os; //构造一个输出字符串流，流内容为空 int i = 12; os << i; //向输出字符串流中输出int整数i的内容 cout << os.str() << endl; //利用字符串流的str函数获取流中的内容
首先我们给出哈希表的一些定义
const int max_hash_size=1000005; const int maxn=1005; int head[max_hash_size]; //存数据的数组 int Next[maxn]; //记录同地址元素的下一个元素的值 int st[maxn]; //数据集
为啥这个max_hash_size很大，因为这个范围是每一个元素最大是多少而不是一共有多少个元素，哈希表就是用来解决元素非常多的那种情况的
如果单纯使用bool数组的话受制于内存的限制，查找能力实在有限，哈希表在本质上就是拓宽了这个bool数组的范围
这里的head和Next就是链表，然后我们给出哈希函数
int Hash(int& s) { return(s*2654435769)>>28; } int HashingDouble(double d) { if (d==0) return 0; else { int exponent; double mantissa = frexp(d, &exponent); return (unsigned int)((2*mantissa-1) * (~0U)); } } int HashingString(char *str, int iLen) { int hsval = 2654435769; int i; int iShift = 0; for(i=0; i<iLen; i++) { hsval ^= (str[i]<<iShift); iShift+=3; if(iShift>24) iShift=0; } return hsval; }
你可以把哈希函数理解为根据元素的值来计算这个元素下标的函数，然后我们回头去看那个max_hash_size,然后理解一下：
如果我们不用哈希函数，那么数据有多少，max_hash_size就是多少，如果我们用了哈希函数，就把原数据范围进行了一个放缩，放缩到了空间所允许的一个范围内
这个时候我们再取理解maxn是啥，既然max_hash_size是经过放缩之后的数据有多少个，那么maxn就是每一个数据的数据范围了
由于哈希碰撞的原因，同哈希值元素可能有多个，我们在链表查找到地址的时候，要顺着链表一个一个找看是不是
下面给出尝试插入哈希表的函数，如果不重复就可以插进去，否则就插不进去返回0
int try_to_insert(int s) { int h=Hash(st[s]); //得到s元素的数组下标 int u=head[h]; //得到这个下标下的元素值 while(u) //顺着链表一个一个找 { if(st[u]==st[s]) //如果在链表中找到了s，说明这个s已经访问过了 return 0; u=Next[u]; //此时u是下一个在此位置的元素值 } Next[s]=head[h]; //头插法 head[h]=s; return 1; }
因为实现的过程中有一个
int u=head[h];
while(u)
这么一个操作，这应该是这种方法实现哈希表的一个缺陷，所以在插入的时候，千万保证非0
下面给出哈希表完整的实现代码，如果有更好的实现方法，会在本篇文章的基础上迭代
1 //适用于数据特别多但是每个数的范围不是很大的情况下查找 2 /* 3 string转int 4 istringstream is("12"); //构造输入字符串流，流的内容初始化为“12”的字符串 5 int i; 6 is >> i; //从is流中读入一个int整数存入i中 7 int转string 8 ostringstream os; //构造一个输出字符串流，流内容为空 9 int i = 12; 10 os << i; //向输出字符串流中输出int整数i的内容 11 cout << os.str() << endl; //利用字符串流的str函数获取流中的内容 12 */ 13 #include<iostream> 14 #include<cstring> 15 #include<cmath> 16 using namespace std; 17 const int max_hash_size=1000005; 18 const int maxn=1005; 19 int head[max_hash_size]; //存数据的数组 20 int Next[maxn]; //记录同地址元素的下一个元素的值 21 int st[maxn]; //数据集 22 void init_lookup_table() 23 { 24 memset(head,0,sizeof(head)); 25 } 26 int Hash(int& s) 27 { 28 return(s*2654435769)>>28; 29 } 30 int HashingDouble(double d) 31 { 32 if (d==0) 33 return 0; 34 else 35 { 36 int exponent; 37 double mantissa = frexp(d, &exponent); 38 return (unsigned int)((2*mantissa-1) * (~0U)); 39 } 40 } 41 int HashingString(char *str, int iLen) 42 { 43 int hsval = 2654435769; 44 int i; 45 int iShift = 0; 46 for(i=0; i<iLen; i++) 47 { 48 hsval ^= (str[i]<<iShift); 49 iShift+=3; 50 if(iShift>24) 51 iShift=0; 52 } 53 return hsval; 54 } 55 int try_to_insert(int s) 56 { 57 int h=Hash(st[s]); //得到s元素的数组下标 58 int u=head[h]; //得到这个下标下的元素值 59 while(u) //顺着链表一个一个找 60 { 61 if(st[u]==st[s]) //如果在链表中找到了s，说明这个s已经访问过了 62 return 0; 63 u=Next[u]; //此时u是下一个在此位置的元素值 64 } 65 Next[s]=head[h]; //头插法 66 head[h]=s; 67 return 1; 68 } 69 int main() 70 { 71 //必须保证数据集中，查找的位置有值 72 for(int i=1;i<=10;i++) 73 st[i]=i-1; 74 init_lookup_table(); 75 for(int i=1;i<=5;i++) 76 { 77 if(try_to_insert(i)) 78 cout<<"Yes"<<endl; 79 else 80 cout<<"No"<<endl; 81 } 82 cout<<endl; 83 for(int i=3;i<=7;i++) 84 { 85 if(try_to_insert(i)) 86 cout<<"Yes"<<endl; 87 else 88 cout<<"No"<<endl; 89 } 90 return 0; 91 }