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
117
118
119
120
121
122
123
|
#pragma warning(disable:4786)
#ifndef hmap_h
#define hmap_h
#include <vector>
#include "incl.h"
using namespace std;
// void add_elem( obj_type x, key_type k ) --> Insert x
// void del_elem( key_type k ) --> Remove x
// obj_type get_elem( key_type k ) --> Return item that matches x
// void make_empty( ) --> Remove all items
template <class obj_type, class key_type>
class hmap
{
private:
enum entry_type
{
ACTIVE, EMPTY, DELETED
};
struct hash_entry
{
obj_type element;
key_type key;
entry_type info;
hash_entry( const obj_type &e = obj_type( ), const key_type &k = key_type( ), entry_type i = EMPTY ) : element( e ), key( k ), info( i )
{ }
}
;
int occupied;
virtual bool isActive( int currentPos ) const;
virtual void rehash( );
virtual bool isPrime ( int n ) const;
virtual int nextPrime( int n ) const;
double maxOccupiedPercentage;
protected:
int lookups;
unsigned int hash( const string &key ) const;
vector<hash_entry> array;
public:
hmap( double moc );
virtual int findPos ( const key_type &k );
virtual void make_empty( );
virtual void add_elem ( const obj_type &x, const key_type &k );
virtual void del_elem ( const key_type &k );
virtual obj_type get_elem ( const key_type &k );
virtual void run_func( void (*func)(obj_type) );
virtual void run_func( void (*func)(obj_type, void*), void* v_arg );
// inline:
void getSize()
{
int size = 0;
for( int j = 0; j < array.size( ); j++ )
if (array[ j ].info == ACTIVE)
size++;
return size;
};
int getLookups()
{
return lookups;
};
int getCapacity()
{
return array.size();
};
double getLambda()
{
return static_cast<double>(getSize())/static_cast<double>(getCapacity());
}
obj_type& operator[]( key_type &k )
{
return get_elem( k );
}
};
template <class obj_type, class key_type>
class linearhmap : public hmap<obj_type, key_type>
{
public:
linearhmap(double moc) : hmap<obj_type, key_type>(moc)
{}
;
virtual int findPos( const key_type &k )
{
int collisionNum = 0;
int currentPos = hash( k ) % hmap<obj_type, key_type>::array.size( );
hmap<obj_type, key_type>::lookups++;
while( hmap<obj_type, key_type>::array[ currentPos ].info != hmap<obj_type, key_type>::EMPTY &&
hmap<obj_type, key_type>::array[ currentPos ].key != k )
{
hmap<obj_type, key_type>::lookups ++;
currentPos++;
if( currentPos >= hmap<obj_type, key_type>::array.size( ) )
currentPos -= hmap<obj_type, key_type>::array.size( );
}
return currentPos;
}
};
#include "hmap.cpp"
#endif
|
