hashtable简单实现[开放地址法+字符统计]&[c++]

hashtable的最主要问题就是碰撞冲突的解决，常用的方法一般是开放地址法和链表法，这里主要用的是开放地址法。

最基本的hashtable实现

// HashTable.cpp : 定义控制台应用程序的入口点。
//开放地址法，简单hashtable

#include "stdafx.h"
#include <iostream>
#include <hash_map>
using namespace std;

const int HashSize=13;

class HashTable
{
private:
    int *hashtable;
public:
    //int *hashtable;
    HashTable(){
        hashtable=new int[HashSize];
        if(hashtable==NULL){
            cerr<<"hashtable init failed"<<endl;
            exit(0);
        }
        for(int i=0 ; i<HashSize ; i++)
            hashtable[i]=-1;
    }
    ~HashTable(){
        delete []hashtable;
    }

    unsigned HashValue(unsigned value){
        int key;
        key=(unsigned)(value % HashSize);
        if(hashtable[key]!=-1)
            return HashValue(key+1);
        return key;
    }

    void HashInsert(unsigned value){
        int key=HashValue(value);
        hashtable[key]=value;
    }

    int HashFind(unsigned value){
        int key=(unsigned)(value % HashSize);
        int i=0;
        while(hashtable[key]!=-1 && i++<HashSize){
            if(hashtable[key]==value)
                return key;
            else
                key=(key+1)%HashSize;
        }
        return -1;
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
    int array[HashSize]={19,14,23,1,68,20,84,27,55,11,10,79};
    HashTable h;
    for(int i=0 ; i<HashSize-1 ; i++){
        h.HashInsert(array[i]);
    }
    for(int k=0 ; k<HashSize-1 ; k++){
        cout<<array[k]<<":"<<h.HashFind(array[k])<<endl;
    }
    return 0;
}

使用hashtable对文件中的字符统计

// HashForWord.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

const int HashSize=15;

typedef struct HashNode
{
    char *key;
    int count;
}hashNode;

class HashTable
{
private:
    hashNode hashtable[HashSize];
public:
    HashTable(){
        for(int i=0 ; i<HashSize ; ++i){
            hashtable[i].count=0;
            hashtable[i].key=NULL;
        }
    }

    ~HashTable(){
        for(int i=0 ; i<HashSize ; ++i){
            delete hashtable[i].key;
        }
    }

    int HashIndex(int key,char *value){
        int index= key % HashSize;
        if(hashtable[index].count!=0){
            if(strcmp(hashtable[index].key,value)==0)
                return index;
            else
                return HashIndex(index+1,value);
        }
        return index;
    }

    int HashValue(char *value){
        int h=0;
        for(int i=0 ; value[i]!='\0' ; ++i){
            h=31*h+value[i];
        }

        return HashIndex(h,value);
    }

    void HashInsert(char *value){
        int index=HashValue(value);
        //cout<<value<<":"<<index<<endl;
        if(hashtable[index].key==NULL){
            hashtable[index].key=new char[strlen(value)+1];
            strncpy(hashtable[index].key,value,strlen(value));
            hashtable[index].key[strlen(value)]='\0';

            hashtable[index].count=1;
            return;
        }else if(strcmp(hashtable[index].key,value)==0){
            hashtable[index].count++;
            return;
        }

    }

    void output(){
        ofstream out;
        out.open("C:\\Users\\Thinkpad\\Desktop\\wordresult.txt");
        for(int i=0 ; i<HashSize  ; ++i){
            if(hashtable[i].key){
                out<<hashtable[i].key<<":"<<hashtable[i].count<<endl;
            }
        }
        out.close();
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    HashTable ht;
    char str[20];
    ifstream in;
    in.open("C:\\Users\\Thinkpad\\Desktop\\wordlist.txt");
    if(in.is_open()){
        while(!in.eof()){
            in>>str;
            ht.HashInsert(str);
        }
    }else{
        cout<<"open file failed!"<<endl;
    }

    ht.output();
    in.close();
    return 0;
}

    嗯，先从简单写起吧，之后写复杂的。