Solved

hashing and database

Posted on 2000-04-27
20
267 Views
Last Modified: 2010-05-18
Hi. I am trying to do a database using a hashtable. I have the class. This is to make a CGI application that search, using the hashtable for the corresponding restaurant entered in the form.
0
Comment
Question by:milalik
  • 15
  • 3
  • 2
20 Comments
 

Author Comment

by:milalik
ID: 2755723
I got ten files like this with ten restaurants(at least) each:


Name: Dario's Gourmet
Address: Route 156, km. 8
Phone number: 890-6143
Specialty: Continental

Name: Dos Amigos
Address: Route 107, km. 2.1
Phone number: 882-8000
Specialty: Puerto Rican

Name: Golden Crown
Address: Route 110, km. 9.2
Phone number: 890-2016
Specialty: Chinese

Name: Molina's Restaurant
Address: Route 2, km. 124.5
Phone number: 891-1487
Specialty: Sea Food

Name: Cathy's Chinese Restaurant
Address: Route 459, km. 2.9, Bo. Esteves
Phone number: 891-1720
Specialty: Chinese


Name: Bohio
Address: Route 102, km. 13.9
Phone number: 851-2755
Specialty: Sea Food

Name: Cascada
Address: Parador Boquemar
Phone number: 851-2158
Specialty: Sea Food

..
..
..

The file name are the towns where the restaurants are located.
                 
               

               
0
 

Author Comment

by:milalik
ID: 2755736
The classes for the hashtable that I am using are:


#ifndef __AbsHash
#define __AbsHash
// HashTable abstract class interface
                 //
// Etype: must have zero-parameter constructor and
// operator==; implementation may require operator!=;
//implementation will require either
                 //     operator= or copy constructor, perhaps both
                 // unsigned int Hash( const Etype & Element, int TableSize )
                 //     must be defined
                 // CONSTRUCTION: with (a) no initializer;
                 //     copy constructor of HahsTable objects is DISALLOWED
                 //
                 // ******************PUBLIC OPERATIONS*********************
                 //     All of the following are pure virtual functions
                 // int Insert( Etype X )  --> Insert X
                 // int Remove( Etype X )  --> Remove X
                 // Etype Find( Etype X )  --> Return item that matches X
                 // int WasFound( )        --> Return 1 if last Find succeeded
                 // int IsFound( Etype X ) --> Return 1 if X would be found
                 // int IsEmpty( )         --> Return 1 if empty; else return 0
                 // int IsFull( )          --> Return 1 if full; else return 0
                 // void MakeEmpty( )      --> Remove all items

                 template <class Etype>
                 class AbsHTable
                 {
                   public:
                     AbsHTable( ) { }
                     virtual ~AbsHTable( ) { }

                     virtual int Insert( const Etype & X ) = 0;
                     virtual int Remove( const Etype & X ) = 0;
                     virtual const Etype & Find( const Etype & X ) = 0;
                     virtual int WasFound( ) const = 0;
                     virtual int IsFound( const Etype & X ) const = 0;
                     virtual int IsEmpty( ) const = 0;
                     virtual int IsFull( ) const = 0;
                     virtual void MakeEmpty( ) = 0;

                   private:
                         // Disable copy constructor
                     AbsHTable( const AbsHTable & ) { }
                 };
                 #endif  

0
 

Author Comment

by:milalik
ID: 2755743
// HashTable class interface
                 //
                 // Etype: must have zero-parameter and copy constructor,
                 //     operator= and operator!=
                 // unsigned int Hash( const Etype & Element, int TableSize )
                 //     must be defined
                 // CONSTRUCTION: with (a) no initializer;
                 // Copy constructon of HashTable objects is DISALLOWED
                 // Deep copy is supported
                 //
                 // ******************PUBLIC OPERATIONS*********************
                 // int Insert( Etype X )  --> Insert X
                 // int Remove( Etype X )  --> Remove X
                 // Etype Find( Etype X )  --> Return item that matches X
                 // int WasFound( )        --> Return 1 if last Find succeeded
                 // int IsFound( Etype X ) --> Return 1 if X would be found
                 // int IsEmpty( )         --> Return 1 if empty; else return 0
                 // int IsFull( )          --> Return 1 if full; else return 0
                 // void MakeEmpty( )      --> Remove all items
                 // ******************ERRORS********************************
                 // Predefined exception is propogated if new fails

                 #ifndef __HashTable
                 #define __HashTable

                 #include "AbsHash.h"

                 template <class Etype>
                 class HashTable : public AbsHTable<Etype>
                 {
                   public:
                     enum KindOfEntry { Active, Empty, Deleted };

                     HashTable( );
                     ~HashTable( ) { delete [ ] Array; }

                     const HashTable & operator=( const HashTable & Rhs );

                     int Insert( const Etype & X );
                     int Remove( const Etype & X );         // Return 1 if found, 0 if not
                     const Etype & Find( const Etype & X ); // Return item in table
                     int IsFound( const Etype & X ) const;  // Return 1 if found
                     int WasFound( ) const;                 // Return 1 if last find ok
                     int IsEmpty( ) const;
                     int IsFull( ) const { return 0; }      // Return 1 if full
                     void MakeEmpty( );
                   private:
                     struct HashEntry
                     {
                         Etype Element;         // The item
                         KindOfEntry Info;      // Active, empty, or deleted

                         HashEntry( ) : Info( HashTable<Etype>::Empty ) { }
                         HashEntry( const Etype & E, KindOfEntry i = Empty ) :
                             Element( E ), Info( i ) { }
                     };

                     enum { DefaultSize = 11 };

                     int ArraySize;       // The size of this array
                     int CurrentSize;     // The number of non-empty items
                     int LastFindOK;      // True of last search was successful
                     HashEntry *Array;    // The array of elements

                         // Some internal routines
                     void AllocateArray( );
                     unsigned int FindPos( const Etype & X ) const;
                 };
                 #endif






                 #include "Hash.h"

                 // Find next prime > N; assume N >= 5

                 int NextPrime( int N )
                 {
                     if( N % 2 == 0 )
                         N++;

                     for( ; ; N += 2 )
                     {
                         int i;

                         for( i = 3; i * i <= N; i += 2 )
                             if( N % i == 0 )
                                 break;
                         if( i * i > N )
                             return N;
                     }
                 }

                 // Allocate the hash table array

                 template <class Etype>
                 void
                 HashTable<Etype>::AllocateArray( )
                 {
                     Array = new HashEntry[ ArraySize ];
                 }

                 // HashTable constructor

                 template <class Etype>
                 HashTable<Etype>::HashTable( ) : ArraySize ( DefaultSize )
                 {
                     AllocateArray( );
                     CurrentSize = 0;
                 }

                 // Clear the hash table

                 template <class Etype>
                 void
                 HashTable<Etype>::MakeEmpty( )
                 {
                     CurrentSize = 0;
                     for( int i = 0; i < ArraySize; i++ )
                         Array[ i ].Info = Empty;
                 }

                 // Return item in hash table that matches X
                 // Success can be tested by WasFound

                 template <class Etype>
                 const Etype &
                 HashTable<Etype>::Find( const Etype & X )
                 {
                     unsigned int CurrentPos = FindPos( X );
                     LastFindOK = Array[ CurrentPos ].Info == Active;
                     return Array[ CurrentPos ].Element;
                 }

                 // Routine to resolve collisions and locate
                 // cell that must contain X if X is found

                 template <class Etype>
                 unsigned int
                 HashTable<Etype>::FindPos( const Etype & X ) const
                 {
                     unsigned int i = 0;   // The number of failed probes
                     unsigned int CurrentPos = Hash( X, ArraySize );

                     while( Array[ CurrentPos ].Info != Empty &&
                            Array[ CurrentPos ].Element != X )
                     {
                         CurrentPos += 2 * ++i - 1;    // Compute ith probe
                         if( CurrentPos >= ArraySize ) // Implement the mod
                             CurrentPos -= ArraySize;
                     }

                     return CurrentPos;
                 }

                 // Test if X is in the hash table

                 template <class Etype>
                 int
                 HashTable<Etype>::IsFound( const Etype & X ) const
                 {
                     unsigned int CurrentPos = FindPos( X );
                     return Array[ CurrentPos ].Info == Active;
                 }


                 // Return true if last Find operation was successful

                 template <class Etype>
                 int
                 HashTable<Etype>::WasFound( ) const
                 {
                     return LastFindOK;
                 }

                 // Remove X from hash table
                 // Return true if X was removed; false otherwise

                 template <class Etype>
                 int
                 HashTable<Etype>::Remove( const Etype & X )
                 {
                     unsigned int CurrentPos = FindPos( X );

                     if( Array[ CurrentPos ].Info != Active )
                         return 0;

                     Array[ CurrentPos ].Info = Deleted;
                     return 1;
                 }

                 // Insert X into hash table
                 // Return false if Xis a duplicate; true otherwise
                 // Rehash automatically as needed

                 template <class Etype>
                 int
                 HashTable<Etype>::Insert( const Etype & X )
                 {
                     unsigned int CurrentPos = FindPos( X );

                         // Don't insert duplicates
                     if( Array[ CurrentPos ].Info == Active )
                         return 0;

                         // Insert X as active
                     Array[ CurrentPos ] = HashEntry( X, Active );
                     if( ++CurrentSize  < ArraySize / 2 )
                         return 1;

                         // REHASHING CODE
                         // Save old table
                     HashEntry *OldArray = Array;
                     int OldArraySize = ArraySize;

                         // Create a new double-sized, empty table
                     CurrentSize = 0;
                     ArraySize = NextPrime( 2 * OldArraySize );
                     AllocateArray( );

                         // Copy table over
                     for( int i = 0; i < OldArraySize; i++ )
                         if( OldArray[ i ].Info == Active )
                             Insert( OldArray[ i ].Element );

                         // Recycle OldArray
                     delete [ ] OldArray;
                     return 1;
                 }

                 // Deep copy of the hash table

                 template <class Etype>
                 const HashTable<Etype> &
                 HashTable<Etype>::operator=( const HashTable<Etype> & Rhs )
                 {
                     if( this != &Rhs )
                     {
                         delete [ ] Array;
                         ArraySize = Rhs.ArraySize;
                         AllocateArray( );
                         for( int i = 0; i < ArraySize; i++ )
                             Array[ i ] = Rhs.Array[ i ];
                         CurrentSize = Rhs.CurrentSize;
                     }

                     return *this;
                 }

                 // Phoney IsEmpty routine

                 template <class Etype>
                 int
                 HashTable<Etype>::IsEmpty( ) const
                 {
                     return CurrentSize == 0;   // Doesn't work with deletions
                 }
0
 

Author Comment

by:milalik
ID: 2755751
I need to create a database of all the restaurants in this towns and be able to search for them using
                 the hashtable. I have only managed to do this:

                 #include<iostream>

                 #include<string>

                 #include "Hash.h"

                 #include "Hash.cc"

                 //using namespace std;



                 unsigned int Hash(const string & Key, int SizeOfTable);



                 main()

                 {

                    HashTable <string> Restaurants;

                    string  name;

                    cout<<"Enter Name: ";
                    getline(cin,name);





                    Restaurants.Insert(name);



                     //To see if it is hashing it

                    const string &Result2= Restaurants.Find(name);
                         

                    if(Restaurants.WasFound())

                 {

                 cout<<"Found "<< Result2;

                 cout<< '\n';

                 }

                 else

                 {

                    cout<<"not found; ";

                     cout<<'\n';

                 }

                   const string &Result3= Restaurants.Find("El Buho");

                    if(Restaurants.WasFound())

                     {

                 cout<<"Found "<< Result3;

                 cout<< '\n';

                     }

                    else

                     {

                 cout<<"El Buho not found ";

                 cout<<'\n';

                     }





                  return 0;

                 }
0
 

Author Comment

by:milalik
ID: 2755775
abesoft suggested this:

The problem is that your CGI needs to access the "database" of information every time that it is called, so you have to either create a disk-based database system(that stores hash tables, indeces, etc on disk), or use a simple format on disk that you can read into
memory and generate the advanced data structures each time you use it.




Reading in 30 records will _not_ take very long. If you had millions of records (or even thousands) I would suggest you look into the first alternative.

The approach you should take is simple: create your database classes:

class Database{
   public:
      void Add( const char *datarecord)
            {!!!1!!!}
     
      char *LookupByName( const char *n);
      void Read( const char *fileName)
       {
         // open the named file
         // Read in each line
         // Call Add for each item read
        }
  };

Then, when your app starts, Read() the database, then Lookup() the data you need.  Obviously, the Add() routine will need to build up a hash table, etc, and the Lookup() routines will need to use
those data structures, but you already know how to do all of that. which include things like Add(), Lookup(), etc, and then write a routine that reads the db from disk and.....
0
 

Author Comment

by:milalik
ID: 2755794
Does that means I have to rewrite the class hashtable that I have? Or does it means that I need to make those classes friends of this new one? I really need some help, with this. Been two months working with this I am stuck. I'll appreciate your help.

thanx
0
 
LVL 1

Expert Comment

by:ntdragon
ID: 2756499
i don't understand is your hashtable uses disk space or memory
as i understood it on the disk so what the problem???
0
 

Author Comment

by:milalik
ID: 2757473
what you do not understand? What you mean if it used disk space or memory?
I'm trying to build a database using it, and need help. i also want to search this database using a form, since I want to make a cgi application.

1. How can I make a databse using this hashtable?
0
 

Author Comment

by:milalik
ID: 2757476
what you do not understand? What you mean if it used disk space or memory?
I'm trying to build a database using it, and need help. i also want to search this database using a form, since I want to make a cgi application.

1. How can I make a databse using this hashtable?
0
 
LVL 2

Accepted Solution

by:
abesoft earned 100 total points
ID: 2759333
OK, so you've got your basic record type:
struct Restaurant{
    string name;
    string address;
    //... Fill in other data records
    bool Read( ifstream &in);
    /* Fill in the code to read a record */
};

So you can use this with your template class to create a
    HashTable<Restaurant>

Now, the database class that I gave you before can be combined with your HashTable<Restaurant> to give you a single usable class that encapsulates most of your project.  By "combine", I mean that you could use inheritance, or you could simply make the hash table a data member of the Database class.  There are plusses and minuses to both approaches.

The other part of your assignment was (as I recall) to also have a listing based on another key.  To accomplish this, you can make a second "index", which I expect would be a list of pointers to restaurants, so that the second index will contain pointers to the original restaurants, and you don't have duplication of restaurant data.  This secondary index would also be a data member of the Database class.
0
6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

 

Author Comment

by:milalik
ID: 2760883
secondary index?
0
 

Author Comment

by:milalik
ID: 2761395
what you mean by this?
>>The other part of your assignment was (as I recall) to also have a listing based on another key.  To accomplish this, you can make a second "index", which I expect would be a list of pointers to restaurants, so that the second index will contain pointers to the original restaurants, and you don't have duplication of restaurant data.  This secondary index would also be a data member of the Database class.


0
 

Author Comment

by:milalik
ID: 2762433
help
0
 

Author Comment

by:milalik
ID: 2762999
Working on it, will post some code as soon as possible
0
 
LVL 1

Expert Comment

by:ntdragon
ID: 2763477
0
 

Author Comment

by:milalik
ID: 2764671
read the question, don't understand how to use folders
0
 
LVL 1

Expert Comment

by:ntdragon
ID: 2767242
ok
lets see
you have restaurants like:"res","boss",
"abc"
the idea of the folders is that you should have folders with names made of two letters and you should have all the combinations
like folder:aa,ab,ac,...,za,...zz
now each restaurant is placed in the floder that named as the two first letters of the restaurant name
like:"res" will be in folder "re"
"boss" will be in folder "bo"
"abc" will be in "ab"
all the info about the restaurant will be placed in a file placed in the right folder
now when you"ll search for a restaurant
you"ll check the two first letters
then go to the right folder and read the file of the restaurant you searched for

0
 

Author Comment

by:milalik
ID: 2768816
why do I need folders?
0
 
LVL 2

Expert Comment

by:abesoft
ID: 2769303
Under a DOS FAT-style file system (which unfortunately includes NTFS and FAT32), directory access is proportional to the size of the directory.  If you have more than 1,000 or so files in a directory, the performance is terrible, and over 2,000 it really stinks.  That's the main reason for dividing a huge file set into subdirectories.

It's the same reason that we use hash tables that send us into small linked lists, instead of putting all of the data into a single linked list.

Of course, you only have a couple of hundred restaurants, so it shouldn't be the problem.
0
 

Author Comment

by:milalik
ID: 2771426
Yes you are right abesoft. I am working on the codes you suggested. Hope they work. I will post them as soon as possible

thanx
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

760 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now