hash.cpp

数据库索引技术中的可扩充线性哈希表visual C++实现

#include<iostream>
#include<fstream>
#define MAXN 838860
using namespace std;

const int tablesize=4;//length of each table bloack

const int HASH=3527;//to choose

ifstream fp("book.dat");
ofstream fo("result.txt");
int global=0;//depth
int table_count=0;//htable count
int entry_size=0;//limitation of entry_pointer
int entry_pointer=0;
int hashf[32];//hash function
int freehead=-1;
int freetail=-1;

/*
struct hash_entry{
	int size;
	int *entry;
	hash_entry(int s){
		size=s;
		entry_size=s/2;
		entry=new int[size];
		for(int i=0;i<size;i++){
			entry[i]=-1;
		}
	}
};
*/	
struct hash_entry{
	int size;
	int *entry;
	hash_entry(int s){
		size=s;
		entry_size=s/2;
		entry=new int[size];
		for(int i=0;i<size;i++){
			entry[i]=-1;
		}
	}
};
struct hash_table{
	
	int local;
	int next;//overflow table address
	int count;
	int data[tablesize][2];
	hash_table(){
		for(int i=0;i<tablesize;i++){
			data[i][0]=-1;//id
			data[i][1]=-1;//rid
		}
		//parent=-1;
		next=-1;
		count=0;
		local=global;
	}
}htable[MAXN];

struct book{
	int rid;
	int id;
	char name[57];
	int year;
	char press[33];
	char author[33];
};



	//find
	/*
	int find(int id,hash_entry he){//return rid
		hash_table temp;
		int key=id%hashf[he->global-1];
		temp=htable[hash_entry.entry[key]];
		do{
			for(i=0;i<temp.count;i++){
				if(id==temp.data[i][0]){
					return temp.data[i][0];
				}
			}
			temp=htable[temp.next];
		}while(temp.next!=-1);
		return -1;
	}
	*/

bool read_hash(){
	int i,k;
	fstream fi("index1.txt");//in
	fi>>table_count;
	fi>>freehead;
	fi>>freetail;
	for(i=0;i<table_count;i++){
		//read in each table
		fi>>htable[i].local;
		fi>>htable[i].next;
		fi>>htable[i].count;
		for(k=0;k<tablesize;k++){
			fi>>htable[i].data[k][0];
			fi>>htable[i].data[k][1];
		}
	}
	fi.close();
	return true;
}

bool write_hash(){
	ofstream fi("index1.txt");//out
	fi<<table_count<<endl;
	fi<<freehead<<endl;
	fi<<freetail<<endl;
	for(int i=0;i<table_count;i++){
		fi<<htable[i].local<<" ";
		fi<<htable[i].next<<" ";
		fi<<htable[i].count<<" ";
		for(int k=0;k<tablesize;k++){
			fi<<htable[i].data[k][0]<<" ";
			fi<<htable[i].data[k][1]<<" ";
		}
		fi<<endl;
	}
	return true;
}

hash_entry* read_entry(){
	int size;
	ifstream fi("entry.txt");
	fi>>global;
	fi>>entry_size;
	fi>>entry_pointer;
	fi>>size;
	hash_entry *he=new hash_entry(size);
	for(int i=0;i<he->size;i++){
		fi>>he->entry[i];
	}
	return he;
}//to do

bool write_entry(hash_entry *he){
	ofstream fo("entry.txt");
	fo<<global<<endl;
	fo<<entry_size<<endl;
	fo<<entry_pointer<<endl;
	fo<<he->size<<endl;
	for(int i=0;i<he->size;i++){
		fo<<he->entry[i]<<endl;
	}
	return true;
}//to do
/*
int compact(int headloc,int hp,int tailloc,int tp){
	//initially(loc,-1,loc,-1),return head,or -1 if error
	int head=headloc,tail=tailloc,headpointer=hp,tailpointer=tp;
	if(head==tail&&headpointer==-1&&tailpointer==-1){//initialize
		while(htable[head].next!=-1){
			if(htable[head].count<tablesize)break;
			head=htable[head].next;
		}
		if(htable[head].count==tablesize)return 1;//already done
		for(int i=0;i<tablesize;i++){
			if(htable[head].data[i][0]==-1){
				headpointer=i;
				break;
			}
		}
		if(headpointer==-1){
			cout<<"error finding head in htable["<<head<<"]"<<endl;
			return -1;
		}
		//head found
		//search tail
		if(headpointer==3){
			tail=htable[head].next;
			tailpointer=0;
			if(tail==-1)return 1;//already done
		}
		else{
			tail=head;
			tailpointer=headpointer+1;
			if(tail==-1)return -1;//already done
		}
		while(htable[tail].data[tailpointer][0]==-1){//find until it is not a hole
			tailpointer++;
			if(tailpointer==4){
				tail=htable[tail].next;
				tailpointer=0;
				if(tail==-1)return 1;//done
			}
		}
	}
	else{//continue compact
		//tail move forward
		while(htable[tail].data[tailpointer][0]==-1){
			tailpointer++;
			if(tailpointer==4){
				tail=htable[tail].next;
				tailpointer=0;
				if(tail==-1)return 1;//done
			}
		}
		while(htable[head].data[headpointer][0]!=-1){
			headpointer++;
		/*	if(head==htable[tail].next){//head may run further than tail
				tail=head;
				tailpointer=headpointer+1;
				if(tailpointer==4){
					if(htable[tail].next==-1)return 1;
					else {
						tail=htable[tail].next;
						tailpointer=0;
					}
				}
			}
			if(headpointer==4){
				head=htable[head].next;
				headpointer=0;
				if(head==-1)return 1;//done
			}
		}
		
	}
	//do compact
	int id=htable[tail].data[tailpointer][0];
	int rid=htable[tail].data[tailpointer][1];
	if(id==-1){
		cout<<"error compacting: head "<<head<<" headpointer"<<headpointer<<endl;
		cout<<"error compacting: tail "<<tail<<" tailpointer"<<tailpointer<<endl;
	}
	htable[head].data[headpointer][0]=id;
	htable[head].data[headpointer][1]=rid;
	htable[head].count++;
	if(htable[head].count>tablesize)cout<<"error compacting: head "<<head<<" headpointer"<<headpointer<<endl;
	htable[tail].data[tailpointer][0]=-1;
	htable[tail].data[tailpointer][1]=-1;
	htable[tail].count--;
	if(htable[tail].count<0)cout<<"error compacting: tail "<<tail<<" tailpointer"<<tailpointer<<endl;
	int k=compact(head,headpointer,tail,tailpointer);
	if(k!=-1)return k;
	if(k==-1)return -1;//......
}

void free_table(int location){//add to free buckit, or -1 for no more free buckit
	int current=location,pre=location;
	while(htable[current].count!=0){
		pre=current;
		if(htable[current].next==-1){
			return;
		};
		current=htable[current].next;
	}
	if(freehead==-1){
		freehead=current;//first buckit
	}
	else{
		htable[freetail].next=current;
	}
	while(htable[current].next!=-1){
		current=htable[current].next;
	}
	freetail=current;//last buckit
	htable[pre].next=-1;
}
*/
int ask_free(){//get free buckit
	int free;
	if(freehead!=-1){//yes
		free=freehead;
		if(freehead==freetail){
			freehead=-1;
			freetail=-1;
		}else{
			freehead=htable[freehead].next;
		}
		return free;
	}
	else{//no
		free=table_count;
		table_count++;
		return free;
	}
}
/*
bool move(int location1,int offset,int location2){
	if(location1==location2)return true;
	int id=htable[location1].data[offset][0];
	int rid=htable[location1].data[offset][1];
	while(htable[location2].next!=-1){
		if(htable[location2].count<tablesize)break;
		location2=htable[location2].next;
	}
	if(htable[location2].count==tablesize&&htable[location2].next==-1){
		htable[location2].next=ask_free();
		location2=htable[location2].next;
	}
	htable[location2].data[htable[location2].count][0]=id;
	htable[location2].data[htable[location2].count][1]=rid;
	htable[location2].count++;
	htable[location1].data[offset][0]=-1;
	htable[location1].data[offset][1]=-1;
	htable[location1].count--;
	cout<<"moved from "<<location1<<" to "<<location2<<endl;
	return true;
}
*/
int insert(book b,hash_entry *he){//open hashing
	int key=b.id%HASH;
	if(b.rid==2802)cout<<key<<endl;
	int flag=-1;
	if(b.rid==2802)cout<<flag<<endl;
	if(he->entry[key]==-1)he->entry[key]=table_count++;
	if(b.rid==2802)cout<<he->entry[key]<<endl;
	int loc=he->entry[key];
	if(b.rid==2802)cout<<"loc"<<loc<<"count"<<htable[loc].count<<endl;
	if(htable[loc].count!=tablesize){
		htable[loc].data[htable[loc].count][0]=b.id;
		htable[loc].data[htable[loc].count][1]=b.rid;
		htable[loc].count++;
		flag=1;
		if(b.rid==2802)cout<<"loc"<<loc<<"count"<<htable[loc].count<<endl;
	}
	while(htable[loc].next!=-1&&flag==-1){
		if(htable[loc].count!=tablesize){