Solved

# HashTable .....

Posted on 2003-12-05

Hi C++ Experts,

I am trying to understand a HashTable class template and its implementation. But there are several places I couldn't figure out why. I would appreciate some helps.

Here is the class template of a HashTable :

(from Data Structure with C++, Schaum's)

--------------------------------------

template <class K, class T, class H=Hash<K> >

class HashTable

{ protected :

typedef pair<K,T> Pair ;

typedef vector<Pair> Vector ;

typedef Vector::iterator VIt ;

typedef Vector::const_iterator CVIt ;

static const float LOAD ; // line 01, Q1

static const CAP = 109 ; // line 02, Q2

public :

HashTable(int cap=CAP, const H& h=H() ) : _(cap), _hash(h) {}

T& operator[](K) ;

bool insert(K,T) ;

bool remove(K) ;

int size() const ;

int capacity() const { return _.size() ;}

void dump const ;

protected :

Vector _ ;

H _hash ;

int hash(K) ;

void rebuild() ;

} ;

template <class K, class T, class H>

const float HashTable<K,T,H>::LOAD = 0.75 ; // line 03, Q1

template <class K, class T, class H>

T& HashTable<K,T,H>::operator[](K key)

{ const K ZERO_K = K() ;

int k0 = hash(key), k = k0 ;

while (_[k].first != key && _[k].first != ZERO_K)

k = (k+1)% _.size() ;

if( _[k].first == key) return _[k].second ;

if( size()+1 < LOAD* _.size()) // line 04, Q1

{ _[k] = Pair(key, T()) ;

return _[k].second ;

}

else

{ rebuild() ;

return operator[](key) ;

}

}

template <class K, class T, class H>

int HashTable<K,T,H>::size() const

{ int n = 0 ;

const K ZERO_K = K() ;

for(int i = 0 ; i<_.size(); i++)

if (_[i].first != ZERO_K) ++n ;

return n ;

}

template <class K>

struct Hash

{

int operator()(K s)

{ int h = 0 ;

for (int i = 0; i< s.length(); i++)

h += s[i] ;

return h ;

}

} ;

blah ... blah ... blah ...

------------------------------------------

Here are my questions :

Q1 : line 01, 03, 04 : I have trouble understand the variable LOAD. I don't really know why we need it and what does it do ?

Q2 : line 02 : I thought a static variable of a class can NOT be defined inside the class ? It has to be defined outside the class like LOAD in line 03. Or did I miss understand anything ?

Q3 : Is there a built in HashTable class Template in STL ? or there is only <map> in STL ??

Thanks !!!

meow.