overloading [] operator hashtable

Smac89 (1727)
Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include "AVL.h"
#include <sstream>
//#include <iostream> <--declared in AVL.h
#include <string>
#include <stdint.h>

using AVL_TREE::insert;
using AVL_TREE::create;

template <typename P, typename R> 
struct Pair {
	P key;
	R value;
	
	Pair(){}
	Pair( const P& k, const R& v):key(k), value(v) {}
	
	bool operator ==( const Pair &rh ) const {
		return key == rh.key;
	}
	
	bool operator < ( const Pair &rh ) const {
		return key < rh.key;
	}
};

template <typename T, typename R> 
class HashTable {
	const unsigned TABLESIZE;
	avl_tree <Pair<T,R> > *TABLE;
	
	//-----------------------------------------------
	// MurmurHash2, 64-bit version, by Austin Appleby
	uint64_t MurmurHash64A (const void *, unsigned, unsigned int=0x35a4e9000000001);
	
	std::string to_string (const T& t) {
		std::ostringstream os;
		os << t;
		return os.str();
	}
	
	Pair<T, R> *find (avl_tree <Pair<T, R> > *root, const Pair<T, R> &info ) {
		int dir;
		while ( root != None ) {
			if ( root->data == info ) return root->data;
			dir = root->data < info;
			root = root->Link[dir];
		}
		return info;
	}
	
public:
	HashTable( const unsigned &SIZE ):
	TABLESIZE(SIZE), TABLE(new avl_tree < Pair<T, R> > [SIZE]){}
	
	R operator [] ( const T& ret ) {
		std::string temp(to_string(ret));
		unsigned index = MurmurHash64A(temp.c_str(), temp.length()) % TABLESIZE;
		
		Pair<T,R> *tree = find(TABLE[index], Pair<T, R>(ret, 0));
//		if ( !tree.value ) {
//			TABLE[index] = &insert( &TABLE[index], Pair<T, R>(ret, 0));
//			tree = find( &TABLE[index], Pair<T, R>(ret, 0) );
//		}
		return tree.value;
	}
	
	~HashTable() {
		delete [] TABLE;
	}

};

int main() {
	//Store number of sequences for a collatz number
	HashTable <int, int> table(2011);
	std::cout <<table[5] << std::endl;
	return 0;
}

template <typename T, typename R>
uint64_t HashTable <T, R>::MurmurHash64A (const void * key, unsigned len, unsigned seed)
{
	const uint64_t m = 0xc6a4a7935bd1e995;
	const int r = 47;
	uint64_t h = seed ^ (len * m);
	const uint64_t * data = (const uint64_t *)key;
	const uint64_t * end = data + (len>>3);
	
	while(data != end)
	{
		uint64_t k = *data++;
		k *= m; 
		k ^= k >> r; 
		k *= m; 
		h ^= k;
		h *= m; 	
	}
	const unsigned char * data2 = (const unsigned char*) data;
	switch(len & 7)
	{
		case 7: h ^= uint64_t(data2[6]) << 48;
		case 6: h ^= uint64_t(data2[5]) << 40;
		case 5: h ^= uint64_t(data2[4]) << 32;
		case 4: h ^= uint64_t(data2[3]) << 24;
		case 3: h ^= uint64_t(data2[2]) << 16;
		case 2: h ^= uint64_t(data2[1]) << 8;
		case 1: h ^= uint64_t(data2[0]);
        	h *= m;
	};
 
	h ^= h >> r;
	h *= m;
	h ^= h >> r;
	return h;
}


The idea with overloading the [] operator is so that I can do something like:
table[76] = 34 //Dictionary format
This should find the pair<76, ?> and return ? or change ? to 34 if the assignment operator (=) is present. Not sure how possible it is, but I have seen the same thing being done in python.
Or line 77 which should return the value in that Pair.

Can someone take a look at the way I allocated the table in the hashtable class (line 54). I want this to contain pointers to avl_trees.

Next how would I write line 60 with respect to the find function so that it returns a Pair data structure or null if not found?

Help with line 61 to 64 would be great.

Link to AVL.h: http://www.cplusplus.com/forum/beginner/108093/#msg588108
Smac89 (1727)
Works now

1
2
3
4
5
6
7
8
9
10
11
 
R &operator [] ( const T& ret ) {
		std::string temp(to_string(ret));
		unsigned index = MurmurHash64A(temp.c_str(), temp.length()) % TABLESIZE;
		
		Pair<T,R> *tree = find( TABLE[index], Pair<T, R>(ret, 0));		
		if ( tree == None ) {
			TABLE[index] = insert( TABLE[index], Pair<T, R>(ret, 0));
			tree = find( TABLE[index], Pair<T, R>(ret, 0));
		}
		return tree->value;
}



Still have to test number of collisions in table but sleepy now so that's for tomorrow
Last edited on
LB (13399)
Smac89 wrote:
1
2
3
4
5
 
#include "AVL.h"
#include <sstream>
//#include <iostream> <--declared in AVL.h
#include <string>
#include <stdint.h>
Don't do that. Never rely on headers included by other headers. If you use something, include it's header - it doesn't do harm thanks to the include guards.

Also, <cstdint> is preferred to <stdint.h>.
Last edited on
Smac89 (1727)
Thanks

1
2
3
4
5
6
7
 
#pragma once
#include "AVL.h"
#include <iostream>
#include <sstream>
#include <string>
#include <cstdint>
#include <cstdio>
Topic archived. No new replies allowed.