Solved

Hash Tables and Data Base

Posted on 2000-04-21
29
263 Views
Last Modified: 2010-04-02
I am working with a Hash table and I want to do a database using this Hash table. This database will be of a series of restaurants which i have in some files which are divided by town.for example i got this files called AGUADILLA that looks like this:

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

I also have another one named AGUADA:

Name: Colinas
Address: Parador_J.B._Hidden_Village
Phone number: 868-8686
Specialty: Steaks_and_Sea_Food

Name: Buena_Mesa
Address: Route_2,_km.138.5,_Bo.Naranjo
Phone number: 252-1158
Specialty: Vegetarian

Name: Aguada_Sea_Food
Address: 103_Jimenez
Phone number: 868-2136
Specialty: Sea_Food



0
Comment
Question by:milalic
  • 19
  • 10
29 Comments
 

Author Comment

by:milalic
Comment Utility
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;
}

0
 

Author Comment

by:milalic
Comment Utility
Adjusted points from 90 to 190
0
 

Author Comment

by:milalic
Comment Utility
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.
http://www.experts-exchange.com/jsp/qShow.jsp?ta=cplusprog&qid=10331226

Thanx again for your help
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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
0
 

Author Comment

by:milalic
Comment Utility
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?
0
 

Author Comment

by:milalic
Comment Utility
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.

0
 

Author Comment

by:milalic
Comment Utility
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

0
 

Author Comment

by:milalic
Comment Utility
// 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
0
 

Author Comment

by:milalic
Comment Utility
#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:milalic
Comment Utility
I'll appreciate ur help
thanx
0
 

Author Comment

by:milalic
Comment Utility
I'll appreciate ur help
thanx
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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
0
 

Author Comment

by:milalic
Comment Utility
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.
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:milalic
Comment Utility
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
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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 ??
0
 

Author Comment

by:milalic
Comment Utility
Unix and Windows.....So you mean I have to rewrite my insert and my search so it works with what you say?
0
 

Author Comment

by:milalic
Comment Utility
how do  make this folders?and how do I search for files inside them?
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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++
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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  
 
0
 

Author Comment

by:milalic
Comment Utility
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?
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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


0
 

Author Comment

by:milalic
Comment Utility
What I mean is how do I open a folder so i can search for a file
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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);
  }
 
 
0
 
LVL 1

Expert Comment

by:ntdragon
Comment Utility
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
0
 

Author Comment

by:milalic
Comment Utility
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.
0
 

Author Comment

by:milalic
Comment Utility
not getting what you mean in your last comments
0
 
LVL 1

Accepted Solution

by:
ntdragon earned 190 total points
Comment Utility
what i ment is if you're searching for restaurant named "res"
you don't know if there is one
what you should do is
get the folder name from the restaurant name<the two first letters "r" & "e">
that is "re" then to try to open a file named "c:\hash\re\res.txt" if you"ll open it then there is such restaurant and you"ll read the data about it
if you won't then there isn't such restaurant
0
 

Author Comment

by:milalic
Comment Utility
I'll try do do that you explainin there
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

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…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
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.

744 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

17 Experts available now in Live!

Get 1:1 Help Now