Extendable Hashing in C++

[Meiki Jay]

Hallo,
ich muss derzeit ein C++ eine extendable hashing Tabelle mit merge sort implementieren! Vorerst muss ich aber nur das extandable hashing machen, jedoch habe ich keine Ahnung wie ich das machen soll, kann mir da vielleicht irgendjemand helfen?

Ich habe bereits C++ Vorkenntnise und kann im allgemeinen programmieren, ich weiss nur nicht wie ich das mit dem extandable hashing hinkriegen soll...

Danke schonmal im voraus,
Meiki

 

[vfl_freak]

Moin,

so wirklich kann ich Dir da nicht helfen, zumal Du auch nicht geschrieben hast, was genau Du denn tun sollst!

Aber google mal nach "extendible hashing" (Achtung: es heißt "extendible", nicht "extendable") - es scheint etliche Seiten zu geben, die Dir vermutlich als Ansatz weiterhelfen können!

gruß
Klaus

 

[Meiki Jay]

Ich hab mal mein glück versucht einen Code zu implementieren, das ist dabei rasugekommen:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <ext/hash_map>

#define MAX_BUCKETS 512
#define SIZE 10

int makesub(char *in, int depth) {
	char key[21];
	int i;
	int hash, sub = 0;
	int remainder;
	strncpy(key, in, 20);
	key[20] = ' ';
	hash = hasher(key);
	for(i=0; i < depth; i++) {
		sub = sub << 1;
		remainder = hash % 2;
		sub = sub + remainder;
		hash = hash >> 1;
	}
	return sub;
}

struct rec_tag {
	char key_field[21];
};

typedef struct buck_tag	{
		long number_of_records;
		int bucket_bits;
		struct rec_tag record[SIZE];
	} BUCKET;

struct head_tag {
	int bits_used_in_index;
	long buckets_used;
};



int doublidx(int bits, long *addresses) {
	int i;
	int size;
	long old_table[MAX_BUCKETS];
	size = pow(2, bits);
	if((size * 2) == MAX_BUCKETS) puts("WARNING: You are about to run out of index space!");
	memcpy(old_table, addresses, (size * sizeof(long)));
	for(i=0; i < size; i++)	{
		addresses[i*2] = old_table[i];
		addresses[i*2 +1] = old_table[i];
	}
	
	return (bits + 1); 
}

int moverecs(BUCKET * old, BUCKET * neu) {
	char spaces[21] = "                    "; 
	int i, j, sub, n_sub;
	int odd, flag, space, check;
	old->bucket_bits += 1;
	n_sub = 0;
	for(i=0; i < SIZE; i++) {
		sub = makesub(old->record[i].key_field, old->bucket_bits);
		odd = sub%2;
		if(odd) {
			memcpy(&neu->record[n_sub], &old->record[i], sizeof(struct rec_tag));
			strcpy(old->record[i].key_field, spaces);
			n_sub++;
		} 
	}
	neu->number_of_records = n_sub;
	neu->bucket_bits = old->bucket_bits;
	
	for(i=0, flag=0; i < SIZE && flag==0; i++) {
		space = strcmp(old->record[i].key_field, spaces);
		if(space == 0) {
			for(j=i+1, check=1; j < SIZE && check != 0; j++)
				check = strcmp(old->record[j].key_field, spaces);
			if(j < SIZE) {
				memcpy(&old->record[i], &old->record[j-1], sizeof(struct rec_tag));
				strcpy(old->record[j-1].key_field, spaces);
			}     
			else flag = 1;
		}
	}
	
	old->number_of_records -= n_sub;
	return 0;
}

dabei krieg ich aber folgenden Fehler: hashing.h:18: error: `hash' undeclared (first use this function)

Außerdem muss ich noch Aus- und Eingabe (also Einfügen und Abfragen) implementieren. Da weiss ich auch nicht wie ich das machen sollte

Danke für die Hilfe!
lg Meiki