哈希表

哈希表

1. 哈希表的特点：关键字在表中位置和它之间存在一种确定的关系。hash : 翻译为“散列”，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。
2. 实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有：

• 计算哈希函数所需时间
• 关键字的长度
• 哈希表的大小
• 关键字的分布情况
• 记录的查找频率

1. 由于哈希表高效的特性，查找或者插入的情况在大多数情况下可以达到O(1)，时间主要花在计算hash上，当然也有最坏的情况就是hash值全都映射到同一个地址上，这样哈希表就会退化成链表，查找的时间复杂度变成O(n)，但是这种情况比较少，只要不要把hash计算的公式外漏出去并且有人故意攻击（用兴趣的人可以搜一下基于哈希冲突的拒绝服务攻击），一般也不会出现这种情况。

---

下面这个程序是用C++实现的一个包含hash算法的小程序，可以让电话或者姓名作为key，从而查找记录。

	// MyHashTable.cpp : 定义控制台应用程序的入口点。
////设计哈希表实现电话号码查询系统
//说明：一是从文件old.txt中读取的数据自己在程序运行前建立，
//      二是由系统随机生成数据，在程序运行由随机数产生器生成，并且将产生的记录保存到 new.txt文件。

//存在的问题：使用随机产生的文件，在显示时出现乱码


// #include <stdafx.h> 
#include<fstream>//文件流
#include<iostream>
#include <string>
#include<stdlib.h>
using namespace std;

const int D[] = {3,5,8,11,13,14,19,21};//预定再随机数
const int HASH_MAXSIZE = 50;//哈希表长度

//记录信息类型
class DataInfo
{
public:
    DataInfo();//默认构造函数
    friend ostream& operator<<(ostream& out, const DataInfo& dataInfo); //重载输出操作符
    //friend class HashTable;

//private:
    string name;//姓名
    string phone;//电话号码
    string address;//地址 
    char sign;//冲突的标志位，'1'表示冲突，'0'表示无冲突
};

DataInfo::DataInfo():name(""), phone(""), address(""), sign('0')
{

}

ostream& operator<<(ostream& out, const DataInfo& dataInfo) //重载输出操作符
{
    cout << "姓名：" << dataInfo.name << "   电话：" << dataInfo.phone 
         << "    地址：" << dataInfo.address << endl;
    return out;
}

//存放记录的哈希表类型
class HashTable
{
public:
    HashTable();//默认构造函数
    ~HashTable();//析构函数
    int Random(int key, int i);// 伪随机数探测再散列法处理冲突
    void Hashname(DataInfo *dataInfo);//以名字为关键字建立哈希表    
    int Rehash(int key, string str);// 再哈希法处理冲突   注意处理冲突还有链地址法等
    void Hashphone(DataInfo *dataInfo);//以电话为关键字建立哈希表       
    void Hash(char *fname, int n);// 建立哈希表
    //fname 是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式  

    int Findname(string name);// 根据姓名查找哈希表中的记录对应的关键码
    int Findphone(string phone);// 根据电话查找哈希表中的记录对应的关键码
    void Outhash(int key);// 输出哈希表中关键字码对应的一条记录
    void Outfile(string name, int key);// 在没有找到时输出未找到的记录
    void Rafile();// 随机生成文件，并将文件保存在 new.txt文档中
    void WriteToOldTxt();//在运行前先写入数据    

//private:
        DataInfo *value[HASH_MAXSIZE];
    int length;//哈希表长度
};

HashTable::HashTable():length(0)//默认构造函数
{
    //memset(value, NULL, HASH_MAXSIZE*sizeof(DataInfo*));
    for (int i=0; i<HASH_MAXSIZE; i++)
    {
        value[i] = new DataInfo();
    }
}

HashTable::~HashTable()//析构函数
{
    delete[] *value;
}

void HashTable::WriteToOldTxt()
{
    ofstream openfile("old.txt");
    if (openfile.fail())
    {
        cout << "文件打开错误！" << endl;
        exit(1);
    }

    string oldname;
        string oldphone;
    string oldaddress;

    for (int i=0; i<30; i++)
    {
        cout << "请输入第" << i+1 << "条记录:" << endl;        
        cin >> oldname ;
        cin >> oldphone;
        cin >> oldaddress;
        openfile << oldname << "  " << oldphone << "  " << oldaddress << "," << endl;
    }
    openfile.close();
}


int HashTable::Random(int key, int i)// 伪随机数探测再散列法处理冲突
{//key是冲突时的哈希表关键码，i是冲突的次数，N是哈希表长度
    //成功处理冲突返回新的关键码，未进行冲突处理则返回-1
    int h;
    if(value[key]->sign == '1')//有冲突
    {
        h = (key + D[i]) % HASH_MAXSIZE;
        return h;
    }
    return -1;
}

void HashTable::Hashname(DataInfo *dataInfo)//以名字为关键字建立哈希表
{//利用除留取余法建立以名字为关键字建立的哈希函数，在发生冲突时调用Random函数处理冲突
    int i = 0;  
    int key = 0;

        for (int t=0; dataInfo->name[t]!='\0'; t++)   
    {       
        key = key + dataInfo->name[t];
    }
    key = key % 42;
    while(value[key]->sign == '1')//有冲突
    {
        key = Random(key, i++);//处理冲突
    }
    if(key == -1) exit(1);//无冲突
    length++;//当前数据个数加
    value[key]->name = dataInfo->name;
    value[key]->address = dataInfo->address;
    value[key]->phone = dataInfo->phone;
    value[key]->sign = '1';//表示该位置有值
    //cout << value[key]->name << "  " << value[key]->phone << "  "  << value[key]->address << endl;
}

int HashTable::Rehash(int key, string str)// 再哈希法处理冲突
{//再哈希时使用的是折叠法建立哈希函数    
    int h;
    int num1 = (str[0] - '0') * 1000 + (str[1] - '0') * 100 + (str[2] - '0') * 10 + (str[3] - '0');
    int num2 = (str[4] - '0') * 1000 + (str[5] - '0') * 100 + (str[6] - '0') * 10 + (str[7] - '0');
    int num3 = (str[8] - '0') * 100  + (str[9] - '0') * 10  + (str[10] - '0');
    h = num1 + num2 + num3;
    h = (h + key) % HASH_MAXSIZE;
    return h;
}

void HashTable::Hashphone(DataInfo *dataInfo)//以电话为关键字建立哈希表
{//利用除留取余法建立以电话为关键字建立的哈希函数，在发生冲突时调用Rehash函数处理冲突
    int key = 0;    
    int t;

    for(t=0; dataInfo->phone[t] != '\0'; t++)
    {   
        key = key + dataInfo->phone[t];
    }
    key = key % 42;
    while(value[key]->sign == '1')//有冲突
    {
        key = Rehash(key, dataInfo->phone);
    }
    length++;//当前数据个数加
    value[key]->name = dataInfo->name;
    value[key]->address = dataInfo->address;
    value[key]->phone = dataInfo->phone;   
    value[key]->sign = '1';//表示该位置有值    
}

void HashTable::Outfile(string name, int key)//在没有找到时输出未找到的记录
{
    ofstream fout;
    if((key == -1)||(value[key]->sign == '0'))//判断哈希表中没有记录
    {
        fout.open("out.txt",ios::app);//打开文件

        if(fout.fail())
        {
            cout << "文件打开失败!" << endl;
            exit(1);
        }
        fout << name << endl;//将名字写入文件,有个问题，每次写入的时候总是将原来的内容替换了
        fout.close();
    }
}

void HashTable::Outhash(int key)//输出哈希表中关键字码对应的记录
{  
    if((key==-1)||(value[key]->sign=='0'))
        cout << "没有找到这条记录！" << endl;
    else
    {       
        for(unsigned int i=0; value[key]->name[i]!='\0'; i++)
        {
            cout << value[key]->name[i];            
        }

        for(unsigned int i=0; i<10; i++)
        {
            cout << " ";
        }

        cout << value[key]->phone;

        for(int i=0; i<10; i++)
        {
            cout << " ";
        }

        cout << value[key]->address << endl;
    }
}

void HashTable::Rafile()//随机生成文件，并将文件保存在new.txt文档中
{
    ofstream fout;
    fout.open("new.txt");//打开文件，等待写入
    if(fout.fail())
    {
        cout << "文件打开失败！" << endl;
        exit(1);
    }
    for(int j=0; j<30; j++)
    {       
        string name = "";
        for(int i=0; i<20; i++)//随机生成长个字的名字
        {
            name += rand() % 26 + 'a';//名字是由个字母组成           
        }
        fout << name << "   ";//将名字写入文件

        string phone = "";
        for(int i=0; i<11; i++)//随机生成长位的电话号码
        {
            phone += rand() % 10 + '0';//电话号码是纯数字
        }
        fout << phone << "      ";//将电话号码写入文件

        string address = "";
        for(int i=0; i<29; i++)//随机生成长个字的名字
        {
            address += rand() % 26 + 'a';//地址是由个字母组成
        }
        address += ',';
        fout << address << endl;//将地址写入文件
    }
    fout.close();
}

void HashTable::Hash(char *fname, int n)//建立哈希表
//fname是数据储存的文件的名称，用于输入数据，n是用户选择的查找方式
//函数输入数据，并根据选择调用Hashname或Hashphone函数进行哈希表的建立
{
    ifstream fin;       
    int i;
    fin.open(fname);//读文件流对象
    if(fin.fail())
    {
        cout << "文件打开失败！" << endl;
        exit(1);
    }
    while(!fin.eof())//按行读入数据
    {
        DataInfo *dataInfo = new DataInfo();
        char* str = new char[100];      
        fin.getline(str, 100, '\n');//读取一行数据

        if(str[0] == '*')//判断数据结束
        {
            break;
        }

        i = 0;//记录字符串数组的下标
        //a-z:97-122     A-Z:65-90    
        //本程序的姓名和地址都使用小写字母
        while((str[i] < 97) || (str[i] > 122))//读入名字
        {
            i++;
        }

        for(; str[i]!=' '; i++)
        {           
            dataInfo->name += str[i];           
        }

        while(str[i] == ' ')
        {
            i++;
        }

        for(int j=0; str[i]!=' '; j++,i++)//读入电话号码
        {           
            dataInfo->phone += str[i];
        }

        while(str[i] == ' ')
        {
            i++;
        }

        for(int j=0; str[i]!=','; j++,i++)//读入地址
        {           
            dataInfo->address += str[i];
        }

        if(n == 1)
        {           
            Hashname(dataInfo);
        }
        else
        {           
            Hashphone(dataInfo);//以电话为关键字
        }

        delete []str;
        delete dataInfo;
    }   
    fin.close();
}

int HashTable::Findname(string name)//根据姓名查找哈希表中的记录对应的关键码
{
    int i = 0;
    int j = 1;
    int t;
    int key = 0;

    for(key=0, t=0; name[t] != '\0'; t++)
    {
        key = key + name[t];
    }
    key = key % 42;
    while((value[key]->sign == '1') && (value[key]->name != name))
    {  
        key = Random(key, i++);
        j++;
        if(j >= length) return -1;
    }
    return key;
}

int HashTable::Findphone(string phone)//根据电话查找哈希表中的记录对应的关键码
{  
    int key = 0;
    int t;

    for(t=0; phone[t] != '\0' ; t++)
        {
                key = key + phone[t];
        }
    key = key % 42;
    int j = 1;
    while((value[key]->sign == '1') && (value[key]->phone != phone))
    {
        key = Rehash(key, phone);
        j++;
        if(j >= length) 
                {
                    return -1;
                }
        }
    return key;
}

int main()
{
    //WriteToOldTxt();  
    int k;
    int ch; 
    char *Fname;
    HashTable *ht = new HashTable;
    while(1)
    {
        system("cls");//cls命令清除屏幕上所有的文字
        cout << "欢迎使用本系统！" << endl << endl;
        cout << "请选择数据" << endl;
        cout << "1.使用已有数据文件" << endl;
        cout << "2.随机生成数据文件" << endl;
        cout << "0.结束" << endl;
        cout << "输入相应序号选择功能：";
        cin >> k;
        switch(k)
        {
        case 0:
            return 0;
        case 1:
            Fname = "old.txt";//从数据文件old.txt(自己现行建好)中读入各项记录
            break;
        case 2:
            ht->Rafile();
            Fname = "new.txt";//由系统随机产生各记录，并且把记录保存到new.txt文件中
            break;
        default:
            cout << "输入序号有误，退出程序。" << endl; 
            return 0;
        }

        do
        {
            system("cls");
            cout << " 请选择查找方式" << endl;
            cout << "1.通过姓名查找" << endl;
            cout << "2.通过电话查找" << endl;
            cout << "输入相应序号选择功能：";
            cin >> ch;
            if((ch != 1) && (ch != 2))
                cout << "输入序号有误！" << endl;
        }while((ch != 1) && (ch != 2));

        ht->Hash(Fname, ch);
        while(ch == 1)
        {
            int choice;
            cout << endl << "请选择功能" << endl;
            cout << "1.输入姓名查找数据" << endl;
            cout << "2.显示哈希表" << endl;
            cout << "0.退出"<<endl;
            cout << "输入相应序号选择功能：";
            cin >> choice;
            switch(choice)
            {
            case 1: 
                {//注意此处应该加上大括号
                    int key1;                   
                    string name;                    
                    cout << "请输入姓名：";
                    cin >> name;                    
                    key1 = ht->Findname(name);
                    ht->Outfile(name, key1);
                    ht->Outhash(key1);  
                }
                break;

            case 2: 
                {
                    for(int i=0; i<HASH_MAXSIZE; i++)
                    {
                        if(ht->value[i]->sign!='0')
                        {
                            ht->Outhash(i); 
                        }
                    }   
                }                           
                break;


            default:
                cout << endl << "您的输入有误！" << endl;              
            }

            if(choice == 0) 
            {
                return 0;
            }
        }

        while(ch == 2)
        {
            int choice;
            cout << endl << "请选择功能" << endl;
            cout << "1.输入电话查找数据" << endl;
            cout << "2.显示哈希表"<<endl;
            cout << "0.退出"<<endl;
            cout << "输入相应序号选择功能：";
            cin >> choice;
            switch(choice)
            {
            case 1: 
                {
                    int key2;                   
                    string phone;                   
                    cout << "请输入11位的电话号码：";

                    do
                    {
                        cin >> phone;                       
                        if(phone.length() != 11)                    
                        {
                            cout << "电话号码应为11位！\n请重新输入：";
                        }

                    }while(phone.length() != 11);

                    key2 = ht->Findphone(phone);
                    ht->Outfile(phone, key2);
                    ht->Outhash(key2);
                }
                break;

            case 2: 
                {
                    for(int i=0; i<HASH_MAXSIZE; i++)
                    {
                        if(ht->value[i]->sign != '0') 
                        {
                            ht->Outhash(i); 
                        }
                    }
                }               
                break;

            default:
                 cout << endl << "您的输入有误！" << endl;              
            }

            if(choice == 0) 
            {
                return 0;
            }
        }

        while((ch != 1) && (ch != 2))
        {
            cout << "您的输入有误！请输入相应需要选择功能：";
        }
    }
    system("pause");    
    return 0;
}