Hash tables

[Nick]

Hi,
Could someone please help me out with this if you can? I am trying to
finish an assignment for class, and it involves a hashtable. I have to resize
the table and rehash all old elements into the table. I actually have two
problems. One is with the constructor of my class. I am trying to use a
pointer to the table, but when I initialize it I get a lot of compiler errors.
I am using the DEV-C++ environment with the cygwin compiler. Here is the
code if it helps. Also, any ideas on how to write the resize would be greatly
appreciated.

Nick

static const int num_primes = 25;
static const unsigned long prime_list[] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457
};

class HashMap {

public:
typedef string key_type;
typedef int value_type;
typedef pair<key_type, value_type> Entry;
typedef list<Entry>::iterator iterator;
typedef vector<list<Entry> > Table;

private:
size_t entries; // number of entries
size_t tsize; // index to table size

Table ht; // hash table

public:
//construct empty hashtable, set size to first prime number
//in sequence, set entries to zero
HashMap():entries(0),tsize(0), ht(prime_list[tsize]){}

//-----------------------------------------------------------------------------
//utility routines
size_t size() const { return entries; }
size_t table_size() const { return prime_list[tsize]; }
float load_factor() const { return float(size())/table_size(); }

//----------------------------------------------------------------------------
//destructor
~HashMap()
{ }

//------------------------------------------------------------------------------

//increase number of entries by one when insert oper used.
void increment(void)
{
entries++;
}

//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
//hash function, computes hash value on key(string)
// and takes modulus of table size
size_t hashf(key_type const& kt)
{
size_t val = 0;
for(int i = 0; i < kt.size(); i++)
{
val = val * 5 + kt[i];
}
return val % table_size();
}
//------------------------------------------------------------------------------
//insert function
void insert(const key_type& k, const value_type& v)
{
//if(find(k))
//{
//cout<<"Duplicate Entry!"<<endl;
//return;
// }
size_t p = hashf(k);
ht[p].push_front(Entry(k, v));
increment();

}

//------------------------------------------------------------------------------
//resize() function




//------------------------------------------------------------------------------
//search function

pair<bool,iterator> find(key_type const& k)
{

size_t p = hashf(k);
iterator it;

for (it = ht[p].begin(); it != ht[p].end(); ++it)
{
if (it->first == k)
{
return pair<bool, iterator>(true ,it);
}
}

return pair<bool,iterator>(false, it);
}
//------------------------------------------------------------------------------
//print_table routine. Assigns two iterators and checks each "slot"
//int the table to see if a value is in there
//If so, it iterates through the items in the table an prints the values.
//It first prints the index of the table where the data resides.
void print_table()
{
iterator start, stop;
for(int i = 0; i < table_size(); i++)
{
if(!ht[i].empty())
{
start = ht[i].begin();
stop = ht[i].end();
while(start != stop)
{
cout<<"Position: "<<i<<" "<<setw(4)<<start->first<<setw(4)<<start->second<<endl;
start++;
}
}
}
}

};
//----------------end of file---------------------------------------------------

#endif

[Danny Kalev]

On the face of it, your constructor seems flawless. There are two
options: either your code contains a bug somewhere else that the
compiler detects only when the constructor's code is compiled (this is a
common phenomenon with templates) or more likely -- your compiler is not
up to the latest C++ standard in terms of template support and STL
compliance so you want to try to compile this project under a different
compiler, say C++ Builder and see if the errors persist. Btw, what are
the error messages you're getting?

Danny

Nick wrote:
>
> Hi,
> Could someone please help me out with this if you can? I am trying to
> finish an assignment for class, and it involves a hashtable. I have to resize
> the table and rehash all old elements into the table. I actually have two
> problems. One is with the constructor of my class. I am trying to use a
> pointer to the table, but when I initialize it I get a lot of compiler errors.
> I am using the DEV-C++ environment with the cygwin compiler. Here is the
> code if it helps. Also, any ideas on how to write the resize would be greatly
> appreciated.
>
> Nick
>
> static const int num_primes = 25;
> static const unsigned long prime_list[] =
> {
> 53, 97, 193, 389, 769,
> 1543, 3079, 6151, 12289, 24593,
> 49157, 98317, 196613, 393241, 786433,
> 1572869, 3145739, 6291469, 12582917, 25165843,
> 50331653, 100663319, 201326611, 402653189, 805306457
> };
>
> class HashMap {
>
> public:
> typedef string key_type;
> typedef int value_type;
> typedef pair<key_type, value_type> Entry;
> typedef list<Entry>::iterator iterator;
> typedef vector<list<Entry> > Table;
>
> private:
> size_t entries; // number of entries
> size_t tsize; // index to table size
>
> Table ht; // hash table
>
> public:
> //construct empty hashtable, set size to first prime number
> //in sequence, set entries to zero
> HashMap():entries(0),tsize(0), ht(prime_list[tsize]){}
>
> //-----------------------------------------------------------------------------
> //utility routines
> size_t size() const { return entries; }
> size_t table_size() const { return prime_list[tsize]; }
> float load_factor() const { return float(size())/table_size(); }
>
> //----------------------------------------------------------------------------
> //destructor
> ~HashMap()
> { }
>
> //------------------------------------------------------------------------------
>
> //increase number of entries by one when insert oper used.
> void increment(void)
> {
> entries++;
> }
>
> //------------------------------------------------------------------------------
>
> //------------------------------------------------------------------------------
> //hash function, computes hash value on key(string)
> // and takes modulus of table size
> size_t hashf(key_type const& kt)
> {
> size_t val = 0;
> for(int i = 0; i < kt.size(); i++)
> {
> val = val * 5 + kt[i];
> }
> return val % table_size();
> }
> //------------------------------------------------------------------------------
> //insert function
> void insert(const key_type& k, const value_type& v)
> {
> //if(find(k))
> //{
> //cout<<"Duplicate Entry!"<<endl;
> //return;
> // }
> size_t p = hashf(k);
> ht[p].push_front(Entry(k, v));
> increment();
>
> }
>
> //------------------------------------------------------------------------------
> //resize() function
>
> //------------------------------------------------------------------------------
> //search function
>
> pair<bool,iterator> find(key_type const& k)
> {
>
> size_t p = hashf(k);
> iterator it;
>
> for (it = ht[p].begin(); it != ht[p].end(); ++it)
> {
> if (it->first == k)
> {
> return pair<bool, iterator>(true ,it);
> }
> }
>
> return pair<bool,iterator>(false, it);
> }
> //------------------------------------------------------------------------------
> //print_table routine. Assigns two iterators and checks each "slot"
> //int the table to see if a value is in there
> //If so, it iterates through the items in the table an prints the values.
> //It first prints the index of the table where the data resides.
> void print_table()
> {
> iterator start, stop;
> for(int i = 0; i < table_size(); i++)
> {
> if(!ht[i].empty())
> {
> start = ht[i].begin();
> stop = ht[i].end();
> while(start != stop)
> {
> cout<<"Position: "<<i<<" "<<setw(4)<<start->first<<setw(4)<<start->second<<endl;
> start++;
> }
> }
> }
> }
>
> };
> //----------------end of file---------------------------------------------------
>
> #endif