• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 628
  • Last Modified:

hash table with chaining using a dynamic array

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
Telekin
Asked:
Telekin
  • 7
  • 4
  • 2
1 Solution
 
Kent OlsenData Warehouse Architect / DBACommented:

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
 
TelekinAuthor Commented:
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
 
TelekinAuthor Commented:
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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
Kent OlsenData Warehouse Architect / DBACommented:
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
 
TelekinAuthor Commented:
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
 
peter_sheynkmanCommented:
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
 
TelekinAuthor Commented:
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
 
peter_sheynkmanCommented:
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
 
TelekinAuthor Commented:
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
 
Kent OlsenData Warehouse Architect / DBACommented:
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
 
TelekinAuthor Commented:
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
 
TelekinAuthor Commented:
Great job and quick response, didn't quite solve my entire problem though.
0
 
Kent OlsenData Warehouse Architect / DBACommented:
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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 7
  • 4
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now