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
Solved

Hash Tables and Data Base

Posted on 2000-04-21
29
267 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
ID: 2739025
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
ID: 2739033
Adjusted points from 90 to 190
0
 

Author Comment

by:milalic
ID: 2739034
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
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 
LVL 1

Expert Comment

by:ntdragon
ID: 2739226
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
ID: 2739256
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
ID: 2739262
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
ID: 2739264
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
ID: 2739269
// 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
ID: 2739282
#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
ID: 2739288
I'll appreciate ur help
thanx
0
 

Author Comment

by:milalic
ID: 2739291
I'll appreciate ur help
thanx
0
 
LVL 1

Expert Comment

by:ntdragon
ID: 2739678
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
ID: 2740102
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
ID: 2740621
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
 

Author Comment

by:milalic
ID: 2740836
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
ID: 2742307
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
ID: 2742560
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
ID: 2742612
how do  make this folders?and how do I search for files inside them?
0
 
LVL 1

Expert Comment

by:ntdragon
ID: 2743122
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
ID: 2743127
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
ID: 2743265
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
ID: 2743306
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
ID: 2745051
What I mean is how do I open a folder so i can search for a file
0
 
LVL 1

Expert Comment

by:ntdragon
ID: 2745434
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
ID: 2745447
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
ID: 2749349
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
ID: 2749355
not getting what you mean in your last comments
0
 
LVL 1

Accepted Solution

by:
ntdragon earned 190 total points
ID: 2752334
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
ID: 2753960
I'll try do do that you explainin there
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

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…
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

789 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