hash_str.h

数据结构与算法设计学习得素材

//---------------------------------------------------------------------------
#ifndef  _HASHCLASS_H_
#define  _HASHCLASS_H_
/*
    hashVector是闭散列方法的一个哈希类 － 哈希类的向量版本。
    文件名:  hash_str.h
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
using namespace std;

//---------------------------------------------------------------------------
class hashVector
{
   private:
	  // 哈希表向量
      vector<string> ht;
      // 溢出桶
      vector<string> overflowBucket;
      // 参数
      size_t  m;		// 哈希表表长，必须为质数
      size_t  n;		// 人数（姓名字符串数目）
   public:
      // 构造器
      hashVector(vector<string> namelist, int m0);
      // 返回表长
      size_t size() const { return m; }
      // 返回表大小
      size_t  table_size()  const { return n; }
      // 返回装填因子
      float load_factor() const { return float(table_size())/size(); }
      // 哈希表插入操作
      void insert(vector<string>& ht,
                  vector<string>& overflowBucket, string name);
      // 哈希表查找操作
      void search(string name);
      // 输出表
      void print_table();
   private:
      // 除留余数法计算模块
      size_t mid(size_t s);
      // 字符串哈希函数
      size_t hstr1(const string& name);
};
//---------------------------------------------------------------------------
hashVector::hashVector(vector<string> namelist,int m0): m(m0)
{
    n = namelist.size();
    ht.resize(m);
    for (size_t i=0; i<n; i++) {
       // 插入姓名到哈希向量
       insert(ht, overflowBucket, namelist[i]);
    }
}
size_t hashVector::hstr1(const string& name)
{
    // 累加name的ASCII码
    size_t sum = 0, j = 0;
    while(j<name.size()) {
       sum += name[j];  j++;
    }
    return sum;
}
void hashVector::insert(vector<string>& ht,
                        vector<string>& overflowBucket, string name)
{
    size_t  k, s, l;
    // 用除留余数法构造哈希函数
    s = hstr1(name);        // 见7.4.2字符串哈希函数
    l = mid(s) % m;         // 除留余数法计算模块
    if (ht[l]=="")
       ht[l] = name;
    else {
       // 用线性补偿探测处理冲突，并处理表溢出
       k = 0;
       do {
           l = (l+17) % m;
       } while(ht[l]!="" && ++k<=ht.size());
       if (ht[l] == "")
            ht[l]= name;
       else
       if (k>ht.size()) {
          cout << "哈希表溢出！" << endl;
          overflowBucket.push_back(name);
       }
    }
}
// 首先将参数s平方，然后取其各位数字并保存到数组a，最后返回第4、5位数
size_t hashVector::mid(size_t s)
{
   int i=0, a[10];
   size_t d = 1, s0;
   s0 = s*s;
   while(s0>d) d *= 10;
   d /= 10;
   while(d != 0) {
      a[i++] = s0/d;
      s0 = s0%d;
      d = d/10;
   }
   return (a[3]*10+a[4]);
}
// 在哈希表中查找指定的姓名
void hashVector::search(string name)
{
    size_t l;
    bool found = false;
    // 计算哈希函数
    size_t s = hstr1(name);
    l = mid(s) % m;
    if (ht[l]==name) {
       cout << name << "已找到！在" << l << "号纪录\n";
       found = true;
    }
    int k = 0;
    while (ht[l]!=name && ht[l]!="" && ++k<=ht.size()) {
        // 线性补偿探测
        l = (l+17) % m;
        if (ht[l]==name && !found) {
          cout << name << "已找到！在" << l << "号纪录\n";
          found = true;
          break;
        }
    }
    if(k>ht.size())
       for (size_t i=0; i<overflowBucket.size(); i++)
           if(overflowBucket[i]==name) {
              cout << name << "已找到！在溢出桶" << i << "号纪录\n";
              found = true;
              break;
           }
    if (!found)
       cout << name << "未找到！\n";
}

void hashVector::print_table()
{
    // 显示建立的哈希表
    size_t j, l;
    cout << "**************************   当前哈希表   *************************\n";
    cout << " 编号     姓     名\t 编号     姓     名\t 编号     姓     名\n";
    j = 0;
    for (l=0; l<m; l++) {
       if (ht[l] != "") {
	      cout << setw(4) << l << setw(15) << ht[l] << "\t";
          j++;
	      if ((j+1) % 3==1)
             cout << endl;
	   }
   }
   cout << "\n总人数是: " << table_size() << endl;
   cout << size() << " 个槽已被占用\n" ;
   cout << "装填因子是: " << load_factor() << endl;
}
#endif
//---------------------------------------------------------------------------