?
Solved

hash table with chaining using a dynamic array

Posted on 2003-03-08
13
Medium Priority
?
608 Views
Last Modified: 2008-02-01
I'm trying to create a hash table using chaining and I need to use a dynamic array because if the load of the table gets to a certain point, I need to rehash using a larger table size.  I'm using MSVC++ 6.0 and it's throwing some errors that I'll include later.  First off, here is my linked list (the chaining part) struct:

struct Node{
     struct Node *Next;
     int Data;
};


My dynamic array:

struct Node *HashTable;
HashTable = new Node[HASH_TABLE_SIZE];


Now I'm trying to use that as the hash table and to make it larger I do:

HashTable = new Node[NEW_HASH_TABLE_SIZE];


This is the error MSVC++ 6.0 is giving me:
htchain.cpp(139) : error C2501: 'HashTable' : missing storage-class or type specifiers
htchain.cpp(139) : error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
htchain.cpp(139) : error C2440: 'initializing' : cannot convert from 'struct Node *' to 'int'
        This conversion requires a reinterpret_cast, a C-style cast or function-style cast

I can't even initialize the table, let alone ever expand it.  I tried making a basic dynamic array like this:

int *vector = new int[10];


And that works, but if I try this, it throws the same error:

int *vector;
vector = new int[10];


The odd thing is that if I do:

int *vector = new int[10];  //or this:
struct Node *HashTable[HASH_TABLE_SIZE];


There are no errors (but then I can never expand the table size, and that's my problem in the first place!).  I'd really appreciate any help, this is really important.
0
Comment
Question by:Telekin
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 4
  • 2
13 Comments
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8096151

I assume that these are code snippets, your hash table is wrapped by a class, and that resizing the hash table is a class method?

Editing your code directly, try this:


struct Node *HashTable;
HashTable = new struct Node[HASH_TABLE_SIZE];

HashTable = new struct Node[NEW_HASH_TABLE_SIZE];


Kdo
0
 

Author Comment

by:Telekin
ID: 8096293
I tried that and it still throws an error.

struct Node *HashTable;
HashTable = new struct Node[HTABLESIZE];

Error:
htchain.h(127) : error C2501: 'HashTable' : missing storage-class or type specifiers
htchain.h(127) : error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'
htchain.h(127) : error C2440: 'initializing' : cannot convert from 'struct Node *' to 'int'
        This conversion requires a reinterpret_cast, a C-style cast or function-style cast

I can't expand the array because it will throw the same error as above.  I'm thinking maybe it has something to do with the fact that the dynamic array is a pointer and the struct has a pointer in it too?  I'm not sure, dynamic arrays are a little new to me, but I have been searching online for quite some time and nothing seems to work.
0
 

Author Comment

by:Telekin
ID: 8096300
Could this be the problem?

void HashTableCreate(void)
{
     int i;
     for(i=0; i<HTABLESIZE; i++){
          HashTable[i] = 0;
     }
}

Should the initialization be HashTable[i] = null; ?
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8096304
I'll admit that I guessed at that.  :(  Sorry.


How cumbersome will it be to typedef the struct?

typedef struct
{
  TNode *Next;
  int   Data;
} TNode;

Some compilers (most, actually) will give an error on the "TNode *Next;" statement as "TNode" isn't yet defined.  You'll need a "forward reference" indication and after having been at my desk for about 18 hours so far today it escapes me.  :(

It might be as simple as "typedef TNode;" but my brain really is on "frazzle" right now.

Kdo
0
 

Author Comment

by:Telekin
ID: 8096538
Alright, I tried it again (and I looked up the forward reference at google) and this is what I came up with:

struct node;  //forward reference
typedef node *Node;  //typedef

struct node
{
     Node Next;
     int   Data;
};

Node *HT;  //create dynamic array
HT = new Node[100];  //try to allocate space

This still gives me the same 3 errors... I don't know what's going on.  I found this at the following link (linked list basics) http://www.cecs.csulb.edu/~maples/cecs274/C++Notes/C++Ch4B.doc

I appreciate your help very much.  I'm still unsure how to do this however.  I'm starting to think that I should just create another array like Node *HT[NEWSIZE] and just copy everything from the old list to the new one (rehashing of course into the new table size).  I guess this kind of defeats the purpose of dynamic arrays doesn't it?  If you have any other ideas I'd be grateful.
0
 

Expert Comment

by:peter_sheynkman
ID: 8097110
try this :

typedef struct _Node{
    struct Node *Next;
    int Data;
}Node;


Node *HashTable;
HashTable = new Node[HASH_TABLE_SIZE];


HashTable = new Node[NEW_HASH_TABLE_SIZE];

Peter
0
 

Author Comment

by:Telekin
ID: 8097857
Still errors:

typedef struct _Node{
   struct Node *Next; //<----- previous declaration of Node
   int Data;
}Node;                //error C2371: 'Node' : redefinition; different basic types, see declaration of 'Node'

Node *HashTable;
HashTable = new Node[HTABLESIZE];  //error C2501: 'HashTable' : missing storage-class or type specifiers
                                   //error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct Node *'

As you can see, I can't even declare HashTable as a new array of Nodes with an original size, let alone with a rehashed size.  I've even tried a few things that I'm not sure would affect (like Node **HashTable), but I still have errors.
0
 

Expert Comment

by:peter_sheynkman
ID: 8097947
put your declaration inside h file with ifndef and include it in cpp file:

Node.h file:

#ifndef __NODE_H
#define __NODE_H

typedef struct _Node{
  struct Node *Next;
  int Data;
}Node;  

#endif

in cpp file :              
#include "Node.h"

Node *HashTable;
HashTable = new Node[HTABLESIZE];  
0
 

Author Comment

by:Telekin
ID: 8098012
I tried what you said and the compiler gives me an error that says error C2371: 'Node' : redefinition; different basic types.  It is referring to the struct Node *Next inside the typedef struct _Node.

#ifndef __NOODE_H
#define __NOODE_H

typedef struct _Node{
  struct Node *Next;
  int Data;
}Node;  //error: redefinition of struct Node

#endif

If I change the last Node to something else, i.e.  "}Node;" becomes "}LNode;" then the program compiles without any errors.  When it comes to creating an instance, however, the compiler gives me the same three errors:

error C2501: 'HashTable' : missing storage-class or type specifiers
error C2040: 'HashTable' : 'int' differs in levels of indirection from 'struct _Node *'
error C2440: 'initializing' : cannot convert from 'struct _Node *' to 'int'
        This conversion requires a reinterpret_cast, a C-style cast or function-style cast
0
 
LVL 46

Accepted Solution

by:
Kent Olsen earned 200 total points
ID: 8098520
Hi Telekin,

Apologies for being away, but even I have to sleep now and then.  :)


I don't have ready access to a compiler today (didn't yesterday, either) so I can't actually build you a solution.  But let's address a couple of things about hash tables and the way that C++ works.

Assuming that this (or something similar) works:

HashTable = new Node[HASH_TABLE_SIZE];

Your code will define a hash table that will hold up to  HASH_TABLE_SIZE entries.  Following that up with a subsequent:

HashTable = new Node[NEW_HASH_TABLE_SIZE];

reserves you a NEW HashTable that will hold up to NEW_HASH_TABLE_SIZE entries.  Unless you've saved the old pointer somewhere or have overloaded the 'new' operator, the old table is off in the ozone.  I assume that what you're really wanting to do is extend the current table, but since this is a hash table, even that has pitfalls.

Unless the hashing algorithm is guaranteed to yield results without collisions (a very rare implementation) the table needs to have a primary and overflow area.  You've provided just some snippets of code, so I assume that HASH_TABLE_SIZE is the total number of primary and overflow entries.

NEW_HASH_TABLE_SIZE is some value larger than HASH_TABLE_SIZE.  Be default, it should do nothing more than extend the overflow size.  One of your comments suggests that you intend it for primary nodes.  If so, you WILL have to compute the new address (offset) for each node and reposition it in the new table.


Now back to the coding problem.  The basic items that your progam needs is:

int  PrimaryBlocks;
int  OverflowBlocks;

Node *HashTable;
Node *OldHashTable;

/*  Create the initial table  */

HashTable = new Node[PrimaryBlocks+OverflowBlocks];

/*  Build the hash table, work with it, etc.  */


At some point the hash table may need to be extended.  You'll need to decided whether to extend the overflow area (by far the easiest), or the primary area (resulting in more initial reprocessing but perhaps better overall performance), or both.

/*  Extend the hash table  */

PrimaryBlocks = NewPrimaryBlockCount;
OverflowBlocks = NewOverflowBlockCount;

OldHashTable = HashTable;
HashTable = new Node[PrimaryBlocks+OverflowBlocks];

/*  Move the items in OldHashTable to HashTable,
    If PrimaryBlocks is unchanged, this is just a copy  */

delete HashTable[];  /*  free up the old memory  */


With the exception of the 'new' operator, all of the code that you've posted, and all of the code in these responses is really just C.  I suggest that you rework the hash table code into a class.  Your application will look much cleaner.

struct node;  //forward reference
typedef node *TNode;  //typedef

typedef struct
{
 TNode *Next;
 int   Data;
} TNode;

class THashTable
{
  private:
    int PrimaryNodes;
    int OverflowNodes;
    int PrimaryNodesUsed;
    int OverflowNodesUsed;

  public:
    TNode *FindNode (keyvalue);
    TNode *SaveNode (keyvalue, TNode *node);
    void  CreateTable (int primaryblocks, int overflow blocks);
    void  ResizeTable (int primaryblocks, int overflow blocks);
};

Its usage would resemble:

THashTable *HashTable = new THashTable();

HashTable->CreateTable (PrimaryCount, OverflowCount);

HashTable->AddNode (Node);

HastTable->ResizeTable (NewPrimaryCount, NewOverflowCount);


etc...

Kdo
0
 

Author Comment

by:Telekin
ID: 8100198
I tried the hash table from scratch using what you advised and it works!  However, I still have a little problem.  The way I'm initializing the hash table (in the constructor for my hash table class) is to set all the nodes to 0 initially:

for (int i=0; i<HASH_TABLE_SIZE; i++){
     HashTable[i] = 0;        //<-- error here
}

It throws this error:
error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'const int' (or there is no acceptable conversion)

Also, for referencing a single node within the hash table, I do this:

struct Node *p;
for(p=HashTable[i]; p!=0;){  //<-- error
  //do something if Node is not initialized 0 (null)
}

It throws this error:
error C2679: binary '=' : no operator defined which takes a right-hand operand of type 'struct Node' (or there is no acceptable conversion)

There are several references of this type in my code and they work when I used the old hash table code:
struct Node* HashTable[size];

Instead of the new:
Node *HashTable;
HashTable = new Node[size];

As you can see, I need to initialize the hash table nodes to something in order to tell if there is a node there or not (for fear of referencing something that isn't there and crashing my program).  Would you have any suggestions that would work in this case?
0
 

Author Comment

by:Telekin
ID: 8116967
Great job and quick response, didn't quite solve my entire problem though.
0
 
LVL 46

Expert Comment

by:Kent Olsen
ID: 8119637
We've gotten past the big hurdle.  :)  Just a couple of little bumps to go.


With regards to the compilation errors, I assume that you create the table as a table of Nodes, not a table of pointers to Nodes.  If so, you probably want to initialize the Node structures, not pointers.  In your loop:

for (int i=0; i<HASH_TABLE_SIZE; i++){
    HashTable[i] = 0;        //<-- error here
}

replace the line in error with:

  memset (&HashTable[i], 0, sizeof (Node));


The same concept with the second error:

struct Node *p;
for(p=HashTable[i]; p!=0;){  //<-- error
 //do something if Node is not initialized 0 (null)
}

'p' is a pointer to a Node, and HashTable[i] is a node.  Just modify the line so that the reference is to the address of HashTable[i] using the '&' operator.


Kdo
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question