Hash Tables and Data Base

This is for eventually developing a CGI application that will have a form and if you enter a restaurant name it will search the hash table(which would be my database)and output the correspondin information of the restaurants.This is the main I have manage to do so far.

#include<iostream>
#include<string>
#include "Hash.h"
#include "Hash.cpp"
using namespace std;

unsigned int Hash(const string & Element, int TableSize);

main()
{
  HashTable <string> H;
  string name;
  cout<<"Enter Name: ";
  cin>>name;

  H.Insert(name);
      

  //to check if it is hashing
  const string &Result2= H.Find(name);
  if(H.WasFound())
  {
    cout<<"Found "<< Result2;
    cout<< '\n';
  }
  else
  {
  cout<<"not found; ";
  cout<<'\n';
  }
      
  return 0;
}


unsigned int Hash(const string &Element, int TableSize)
{
  unsigned int HashVal=0;
  for(int i=0;i<Element.length();i++)
     HashVal=(HashVal*128+Element[i])% TableSize;
  return HashVal;
}

Adjusted points from 90 to 190

My questions:

1. Do I have to do the database(inserting of all the restaurants) in the same program as the searching part?

2. Is there a way that when I hash the restaurant names I can know in which file si each restaurant?

View my other question that is related to this. There you will find my classes used for this and some more stuff related to this.
https://www.experts-exchange.com/jsp/qShow.jsp?ta=cplusprog&qid=10331226 

Thanx again for your help

i don't understand your problem
you can do what ever you want

1)you can do what you want
2)yes

it all depends on you hash and how you make it if you ask me you shouldn't make it in the memory you can make it on the hard drive make for the restaurants folders in each folder make file for each restaurant
and make the hash function by the two first letters of the restaurant name
like:
if you have restaurants named allen and alone
they will be in folder named:AL
there will be two files first allen.txt
second alone.txt each will contain the info of the restaurant

then it very easy to know in witch file
the current resturant

and about the first as you wish

How do I make it on hard drive?
I'll post my classes here again so you can view them.

What you don't understand of my first question?

1. Do I have to do the database(inserting of all the restaurants) in the same program as the searching part?

What I mean is it better doing the database apart from the program that performs the searching?

About this you wrote:it all depends on you hash and how you make it if you ask me you shouldn't make it in the memory you can make it on the hard drive make for the restaurants folders in each folder make file for each restaurant
and make the hash function by the two first letters of the restaurant name
like:
if you have restaurants named allen and alone
they will be in folder named:AL
there will be two files first allen.txt
second alone.txt each will contain the info of the restaurant

Can you explain a little more? I'm not understanding what you mean.

My classes:


#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

// 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
}

I'll appreciate ur help
thanx

I'll appreciate ur help
thanx

ok lets see
how linked hash table works
you have an array 0..n of pointers to class named data<for example>
you have a function that gives you for each restaurant name an entry in the array 0..n
in this entry<and in each other>
you have a linked list of data class
now for adding a restaurant you go to the end of the list and add new class
for searching a restaurant you go through the class's in the list till you find your restaurant
if your function is well made and the array is big eoungh for your data
all the operations will take O(1)
by big enough i mean something like
1/10 of your data
by well made func i mean a func that won't leave empty entrys at the array

this hash table takes a lot of memory
'cause if you have 1,000,000 restaurant
then you have to have an array of 100,000 lists and 1,000,000 class's in the memory

so what you can do is instead of using
an array you can use folders on your hard drive and instead of using linked list of class's use can use files in those folders

about the function i told you to take the two\three first letters of the restaurant name and make folder for each combination

in that way you"ll have only one resturant each time <or more if it multiuser prog>and not all of them
'cause as you understand it not posibble
that you"ll need all the restaurants

and each time someone search for a restaurant like :allon<restaurant name>
you go to folder named:al<if you use two letters>,all<if you use three letters>
there you find file named allom
and read it to memory

now about the inserting you can do it in diffrent programs it is very easy to do if you use such hash table

about file you always will know in witch file is your restaurant 'cause all this idea build on it

1.Would the class I posted here will work for what you saying?How?

2.Could you provide and example of what you are describing about the folders?How I am suppossed to create the folders with the files inside it?
 
It is a little confusing for me. I don't know, maybe I am getting a little frustrated or something.

i think you won't need your code or most of it

about the floders
let make them by the first two letters
of the name

write a program that will make a folder
named hash1 and in it it will make folders with all combinations of two letters

like:
aa,ab,ac,ad,...,ba,...,za,...,zz
then make a func that will insert restaurants it asks for the resturant name find the right folder for the restaurant and in this folder it makes a file named by the name of the restaurant with the restaurant data in it
example:the restaurant name is jahnon
the func will go to folder "ja" and there it will make a file named jahnon.txt in this file will be all the info about this restaurant

now your search func also will read the restaurant name from the user then it will go to the right folder there it will search for the right file
example:the requested restaurant is "jahnon"
the func will check the first two letters that are "j" and "a" then it will go to folder "ja" and search there for the file jahnon when it will find it
it will open it and read the file to the memory

1. How do I make a folder? I know how to make files butnot folders.

The, you telling me that I don't need to use the class I made? That i should make a hash function that allows me to create the folders and hash each name using its first letters only?

What you mean by this: i think you won't need your code or most of it

thanx

i mean you"ll have to rewrite it
'cause your in your code code you don't use files

you should write the search and the insert funcs as i told you

now about the folders and the files what are you using to write this prog ??

Unix and Windows.....So you mean I have to rewrite my insert and my search so it works with what you say?

how do  make this folders?and how do I search for files inside them?

you need that your insert func will create a file in the right folder

and your search func will read a file from the right folder

about where you write it
i ment c or c++

now the folders:
 
 #include <dir.h>
  int mkdir(const char *path);
  int _wmkdir(const wchar_t *path);

check dir.h for the reset
for files you said you know how to make,read,write them  
 

Yes I know how to make files and read them. But how do I open a folder so I'll be able to open the files?

it easy when you open a file
like res.txt
you write the path before

what i mena is for opening a file you should give the file name so write it with full path like:
"c:\hash\re\res.txt" //it will be the
                     //file name

What I mean is how do I open a folder so i can search for a file

i took it from help in C++Builder

FileSearch example
 
 The following example uses and edit control and a button on a form.  When the button is clicked, the current directory is searched for the  filename specified in the edit control. A message box indicates whether  or not the file is found.
 
 void __fastcall TForm1::Button1Click(TObject  *Sender)
 
 {
          AnsiString asFileName = FileSearch(Edit1->Text,  GetCurrentDir());
          if (asFileName == "")
                  Application->MessageBox(("Couldn't find " +  Edit1->Text + ".").c_str(), "FileSearch Example",  IDOK);
          else
                  Application->MessageBox(("Found " + asFileName  + ".").c_str(), "FileSearch Example", IDOK);
  }
 
 

second idea you can try to open a file
with the name you want
like "res.txt"
<you can use class fstream>

if there isn't such file you"ll get NULL
or something else that will tell you that there isn't such file
<depends on what you are using to open files>
or you"ll succed and you"ll open the file

I justwant to be able to create a folder like you suggested in my insert routine in a folder called restaurant, and put the corresponding files that hash in that folder inside it.

In my search routine I want to open the corresponding folder so I can opne the corresponding file.

not getting what you mean in your last comments

I'll try do do that you explainin there