6
\$\begingroup\$

I am a student and I am implementing data structures concept by myself using C and C++.

I have implemented the concept of hash table here by making a "Phone book" program that takes input which includes the user's name and his phone number and saves the data in the hash table.

The implementation covers insertion and searching operation. Collisions are also handled in this program by implementing the "chaining" concept.

The hasTable structure contains the basic key and value variables as well as the other two:

isEmpty: for checking if the slot in the table is filled or is Empty.

next: for storing data when collision happens. (chaining concept)

Can someone please review it and let me know of anything I should improve? Like in terms of optimizations, standard practices or how to cover boundary/error condition?

#include<iostream>
#include<cstring>
using namespace std;

struct hashTable{
    string key;
    int64_t value;
    bool isEmpty=true;
    hashTable *next;
};

class Contacts{
    int num;        //number of entries
    hashTable *phoneBook;
public:
    Contacts():phoneBook(NULL){
    }
    void ins(){
        int index;
        int64_t phoneNumber;
        string name;
        cout<<"enter number of entries: ";
        cin>>num;
        phoneBook=new hashTable[num];
        cout<<"Enter name and phone number respectively:"<<endl;
        for(int i=0;i<num;i++){
            cin>>name>>phoneNumber;
            index=hashing(name,num);
            if(phoneBook[index].isEmpty){        //if the slot is empty(no collision)...
                phoneBook[index].key=name;
                phoneBook[index].value=phoneNumber;
                phoneBook[index].isEmpty=false;     //it is now filled...
                phoneBook[index].next=NULL;
            }
            else{           //in case of collision...
                hashTable *temp=&(phoneBook[index]);
                while(temp->next!=NULL){
                    temp=temp->next;
                }
                temp->next=new hashTable;
                temp->next->key=name;
                temp->next->value=phoneNumber;
                temp->next->isEmpty=false;
                temp->next->next=NULL;
            }
        }
    }
    int hashing(string name,int n){
        int len,sum=0;
        //converting string into char array...
        len=name.length();
        char temp[len+1];
        strcpy(temp,name.c_str());
        //calculating hash value...
        for(int i=0;i<len;i++){
            sum=sum+temp[i];
        }
        return (sum%n);
    }
    void searchContact(string name){
        int check;
        check=hashing(name,num);

        if(phoneBook[check].next==NULL){        //if there is no collision seen in the current block..
            if(phoneBook[check].key==name){
                cout<<"Name: "<<phoneBook[check].key<<endl;
                cout<<"Phone number: "<<phoneBook[check].value<<endl;
            }
            else{
                cout<<"Not found"<<endl;
            }
        }

        else{                                   //if collision is seen in the current block...
            hashTable *temp=&(phoneBook[check]);
            while(temp!=NULL){
                if(temp->key==name){
                    cout<<"Name: "<<temp->key<<endl;
                    cout<<"Phone number: "<<temp->value<<endl;
                    break;
                }
                else
                    temp=temp->next;
            }
            if(temp==NULL)
                cout<<"Not found"<<endl;
        }
    }
    ~Contacts(){
        delete []phoneBook;
    }
};
int main(){
    string name;
    int n;
    Contacts d1;
    d1.ins();
    cout<<"Enter number of names you want to search: ";
    cin>>n;
    cout<<"Enter names: "<<endl<<endl;
    for(int i=1;i<=n;i++){
        cin>>name;
        d1.searchContact(name);
        cout<<endl;
    }
}
\$\endgroup\$
8
\$\begingroup\$

Separate responsibilities

Key concepts are not separated well. The functionality of the hash table and user interaction are all mixed up and spread out across the various functions of the program.

I propose a different program organization where the responsibilities are separated better:

  • Create a class for the hash table, with functions put(key, value) and get(key). This class encapsulates all details of the functionality of a hash table, such as chaining elements in case of collisions. Users of this class don't know how that's implemented, all they know is that if they call put(key, value) then they will be able to get that value back by calling get(key).

  • Create a class Contacts, with public functions add(name, number) and search(name). This class won't do anything interesting. It will have a hash table, and it will simply delegate add to the hash table's put and search to the hash table's get. It may seem almost pointless, but it's not, because it provides a user-friendly interface. It doesn't know how the hash table works internally, and that's great. The responsibility of Contacts is to store contacts in some way. Today it's a hash table in memory, tomorrow it might be a database. The hash table implementation is an independent component that is usable in other programs, not only this one.

  • Create a main function that handles all user interaction. An interactive menu could be interesting, to let users add contacts and search contacts. The interactive commands read input from stdin and call the naturally named methods of an instance of Contacts. The main function doesn't know or care how Contacts works, that it uses a hash table or a database as a storage, and if the hash table handles collisions or not. Those are implementation details that are encapsulated in Contacts and in the hash table. This is also the only place in the program that prints messages, and that's great.

Readability

This writing style is a bit hard to read because the symbols are tightly packed:

for(int i=0;i<len;i++){

I recommend this more breezy style instead, putting spaces around operators and before ( and after ) and ;:

for (int i = 0; i < len; i++) {

Similarly, instead of this:

cout<<"Phone number: "<<phoneBook[check].value<<endl;

This would be easier to read, again, with spaces around the operator <<:

cout << "Phone number: " << phoneBook[check].value << endl;

I would apply the same style to all statements of the program.


This is considered error-prone:

else
    temp=temp->next;

It's recommended to put braces around block statements:

else {
    temp = temp->next;
}

(I also added spaces around the = operator.)

Other minor things

using namespace std; is considered bad practice.

Instead of sum=sum+temp[i]; it's more natural to write sum += temp[i];.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you @janos :) i am currently learning java and my intention, after completing java course ,is of implementing data structures that I've implemented again but this time in java. What I have learnt from this answer is that focusing on applying OOP paradigm in the RIGHT way is as much important as focusing on learning its concepts, and that comes from practice. Thank you again. \$\endgroup\$ – sazharsha Aug 5 '18 at 19:35
4
\$\begingroup\$

Headers

Since you're using std::int64_t, you need to add

#include <cstdint>

You may be getting away without it on your current compiler, if the definition is included as a side-effect of your existing includes, but it's not guaranteed to work on other compilers (including future versions of what you're using now!).

Similarly, for std::string, you need

#include <string>

Know your standard library

I'm inferring since you say "I am implementing data structures concept by myself" that you want to write your own hash table implementation, rather than using the provided std::unordered_map. But there are other areas where you would benefit from using Standard Library functions.

Look at this function:

int hashing(std::string name,int n){
    int len,sum=0;
    //converting string into char array...
    len=name.length();
    char temp[len+1];
    std::strcpy(temp,name.c_str());
    //calculating hash value...
    for(int i=0;i<len;i++){
        sum=sum+temp[i];
    }
    return (sum%n);
}

Firstly, there's no need to copy into a plain char array (and how we do this is non-standard, as C++ doesn't have variable-length arrays) - we could simply access the C++ string directly:

int hashing(const std::string& name, int n)
{
    int sum = 0;
    for (size_t i = 0;  i < name.length();  ++i) {
        sum += name[i];
    }
    return(sum%n);

Or, more succinctly, using range-based for:

int hashing(const std::string& name, int n)
{
    int sum = 0;
    for (char c: name) {
        sum += c;
    }
    return(sum%n);
}

We can reduce what we write further, by using std::accumulate (from the <numeric> standard header):

int hashing(const std::string& name, int n)
{
    return std::accumulate(name.begin(), name.end(), 0) % n;
}

Having said all that, one thing you should be learning about data structures is that there are better hash functions to minimise collisions from personal names.

Don't use integers for phone numbers

Perhaps phone numbers in your country don't begin with one or more zeros. But they certainly do in mine (and 0 or 00 makes a big difference). You might also need extension numbers, or a pause during dialling. And I don't think any country has positive and negative phone numbers. So despite their name, phone "numbers" are not like arithmetic numbers - use a string representation instead.

Always check for errors when reading input

We need to be careful when we write things such as

std::cin >> name >> phoneNumber;

Before we can use name or phoneNumber, we need to test whether they were successfully assigned (the >> operator doesn't throw exceptions - we need to test for ourselves). Input streams have a handy conversion to boolean that makes this test easy:

if (std::cin >> name >> phoneNumber) {
    // use name and phoneNumber
    // ...
} else {
    std::cerr << "Reading failed" << std::endl;
    // and some recovery action
    // ...
}
\$\endgroup\$
  • \$\begingroup\$ Thank you toby. What i’ve recently learned from these answers is that coming up with a solution is not a big deal (i used to think of it when i started programming) but improving your logics and techniques for better solutions is what matters. This will take time :) thank you again :) \$\endgroup\$ – sazharsha Aug 17 '18 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.