مقدمه في ال Hash Table

بسم الله الرحمن الرحيم

الـHash Table تعد من أهم وأسرع هياكل البيانات على الإطلاق ، وكثير من التطبيقات تستخدم مثل هذه البنيه مثل Spell Checker أو Symbol Table في المترجمات ، حيث تضمن لنا هذه البنيه الوصول السريع جدا لأي بيانات نريدها مهما كان حجم تلك البيانات ، بالاضافه الى ادخال البيانات أيضا يتم في سرعه كبيره .. زمن التنفيذ لها هي O(1) وبالتالى تعد من أسرع هياكل البيانات على الإطلاق (مثلها مثل المصفوفه) ،، اضافه الى ميزه السرعه هناك ميزه جيده بها وهي أنها سهله التطبيق حيث أننا سنطبق هذه البنيه من خلال مصفوفه عاديه أو vector.

بالرغم من ميزات هذه البنيه ، الا أنها يجب أن تستخدم في الأوقات المناسبه وقد لا تصلح لكل حاله ،، لأن الHash Table أولا يتم تطبيقه باستخدام المصفوفه Array والتي يصعب توسيعها (لكننا سنتجاوز هذه المشكله لأننا سنستخدم vector) ، ثانيا وهو الأهم أن أداء هذه البنيه يقل تدريجيا كلما أمتلئت المصفوفه table ، لذلك من البدايه يجب أن نحدد حجم البيانات التي سوف توضع في هذه المصفوفه ونقوم بحجز مساحه مناسبه لهذا الحجم ..ثالثا باستخدام الHash Table لا يمكن زياره جميع العناصر في المصفوفه (بمعنى أصح لا توجد فائده من هذه العمليه Visiting لأن البيانات مخزنه في أماكن عشوائيه بلا ترتيب) ، وبالتالى لا يمكنك مثلا اجراء عمليه ايجاد القيمه الأكبر في هذه البنيه Find MaX ، وفي حال أردت أن تستخدم بنيه توفر لك هذه الميزه فإن الBinary Tree بكل تأكيد هي الأنسب في هذه الحاله .

الHash Table يفضل أن تستخدم في حال كانت البيانات التي تتعامل معها ثابته ولا تتغير ، وتريد الوصول لها في كل مره بشكل سريع ، مثلا البرامج التي تستخدم القاموس Dictionary يمكن أن تقرأ هذه القاموس وتضعه في بنيه Hash Table في الذاكره وقت تشغيل البرنامج.

أحد أهم المفاهيم في الHash Table والHashing بشكل عام هو كيف يمكن تحويل مجموعه من المفاتيح الى مواقع معينه Index في المصفوفه ، في أبسط الأحوال لا تكون هناك أي عمليه تحويل ويكون المفتاح هو نفسه مباشره الموقع Index في المصفوفه ، لكن هناك حالات أخرى كثيره لا يكون هناك مفتاح من أساسه وبالتالى عمليه التحويل من أي قيمه الى موقع index سوف تتم باستخدام الداله المعروفه بالHash Function .

نبدأ بأبسط حاله ممكنه وهي استخدام المفتاح كموقع index ، ولنفرض أنك تريد برمجه نظام لشركه صغيره تحتوي على 1000 عميل وكل سجل عميل يتطلب حوالى 1000 بايت ، بالتالى المجموع الكلي للبيانات هي 1 Megabyte وبكل تأكيد يمكن تحميل هذه القاعده الى الذاكره مباشره وقت تشغيل البرنامج ،،

أسهل حل ممكن وأسرع حل أيضا هو عمل مصفوفه من السجلات تتكون من 1000 خانه ،، وفي حال أردنا أن نستعلم عن العميل محمد صاحب الرقم 300 فكل ما في الأمر :

Record mohmmed = dataBaseArray[300];

Record ahmed = new Record;
dataBaseArray[count++] = ahmed;

في مثل هذه الحاله أو أي حاله مشابه لها وهو وجود مفتاح معين لكل سجل فيمكن أن نستخدم هذا المفتاح كموقع في المصفوفه Keys Are Index Numbers وبالتالى الوصول لأي موقع سيكون أسرع ما يكون على الإطلاق Big-o (1) .

لكن بالطبع في الكثير من الأحيان لن تجد لديك أي مفتاح وستجد قيم مختلفه (نص string مثلا) وهنا سوف تكون مهتمك هو إيجاد أي وسيله لكي تحول هذا النص الى موقع Index .نأخذ مثال صغير على قاموس يحتوي على 50000 كلمه ، ونريد أيجاد أسرع طريقه يمكن من خلالها ايجاد كلمه معينه . في البدايه سنقوم بعمل مصفوفه من 50000 خانه ،، الأن مثلا نريد أن نبحث أو ندخل الكلمه person ، السؤال هنا كيف يمكن أن نجد الموقع المناسب index لهذه الكلمه؟

الحل الأول والأسهل اطلاقا هو تحويل كل حرف الى رقم ومن ثم جمع هذه الأرقام (Add the Digits) ، ومن ثم تمثل لي مجموع هذه الأرقام الموقع في المصفوفه index (سوف نعطي الحرف a القيمه 1 وb القيمه 2 وهكذا ..اضافه الى حرف المسافه space سوف نعطيه مثلا القيمه 0 ، وبالتالى مجموعه الحروف هنا 27).

مثلا الكلمه cats سوف نقوم بتحويلها بهذ الطريقه وينتج لدينا :

3 + 1 + 20 + 19 = 43

0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 1

26 + 26 + 26 + 26 + 26 + 26 + 26 + 26 + 26 + 26 = 260

3*27^3 + 1*27^2 + 20*27^1 + 19*27^0 = 60,337

على ما يبدوا أن هذا الحل سوف يولد لكل كلمه ممكنه موقع فريد ، ننظر الى الكلمه zzzzzzzzzz وفقط نحسب الz الأخيره وهي 26*27^9 وهذا الرقم فقط أكثر من 7,000,000,000,000 !! للأسف مشكله هذه الطريقه أنها تولد خانات لأي كلمه ممكنه مثلا aaaaa,aaaaaa,aaaaaa وهكذا سينتج الكثير من الكلمات غير صحيحه من الأساس .



الحل الأول ولَد القليل من المواقع أقل من ما نحتاجه ، والحل الثاني ولد أكثر من ما نحتاجه بكثيير ،، ما العمل ؟

Hashing
نحن بحاجه الى طريقه نستطيع من خلالها تحويل هذا الرقم الضخم الى رقم صغير مناسب يكون كindex في المصفوفه ،، السؤال هنا كم خانه نحن بحاجه اليها من الأساس ؟ بما أن القاموس يتكون من 50000 كلمه فنحن بحاجه الى عدد كافي من الخانات ،، لكن كما ذكرت من البدايه وسيتضح السبب فيما بعد يجب أن يكون الحجم الممتلئ من الhash table حوالى النصف أو 2/3 على الأكثر ، لذلك نقوم بحجز عدد كافي وليكن 100000 خانه ..

الأن نريد أن نحول الرقم الضخم الكبير 7,000,000,000,000 الى رقم صغير في حدود ال100000 ، وهذه هي الفكره الأساسيه من وراء الhashing ، وسوف نستخدم المعامل modulo باقي القسمه % لضمان وقوع أي رقم مهما كان في مجال معين ،،

arrayIndex = hugeNumber % arraySize;

نقوم بتطبيق بسيط داله تقوم بحساب الهاش للstring المرر لها :

int hashString (const string& str) {
        int hashValue = 0;
        int power = 1;
        
        for (int i=str.length()-1; i>=0; --i) {
                int letter = str[i] - 96;               // get char code , assume char in small letter
                hashValue += power*letter;              
                power *= 27;                                    // next power
        }
        
        return hashValue % size;
}

var4*n^4 + var3*n^3 + var2*n^2 + var1*n^1 + var0*n^0

(((var4*n + var3)*n + var2)*n + var1)*n + var0

int hashString2 (const string& str) {
        int hashValue = 0;
        
        for (int i=0; i<str.length(); i++){
                int letter = str[i] - 96;
                hashValue = ( hashValue*27 + letter) % size;
        }
        
        return hashValue;
}

على العموم لا تفرح كثيرا ، فأي داله hash كما تبين الصوره السابقه ستقوم بوضع أكثر من رقم في نفس الموقع وهذه المشكله تسمى التصادم Collisions وهذا هو الثمن الذي ستدفعه من جراء عمليه الhashing .ويستحيل بالطبع عمل perfect hashing وذلك بجعل كل كلمه في القاموس في موقع فريد ، لكن الذي نأمله هو عدم وجود كلمات كثيره في كل موقع .

الصوره التاليه توضح عمليه التصادم ، حيث يحتوي الhash table على الكلمه demystify ، ونريد اضافه الكلمه الجديده melioration وبعد عمل hash لها تبين أن لها نفس الindex للكلمه demystify .



كيف سندخل هذه الكلمه الجديده للجدول ؟ بمعنى أصح كيف يمكن أن نحل التصادم هذا ؟ هناك طريقتين في الحل وسنتحدث عنهم في هذه المقاله ان شاء الله ،، الطريقه الأولى وتسمى open adderssing تبدأ بالبحث من ذلك الموقع (المحجوز)عن أي خانه تاليه تكون فارغه وندخل فيها الكلمه الجديده ، لذلك ذكرنا قبل قليل أن حجم الhast table يجب أن يكون كبير أكبر من حجم البيانات الحقيقي ،،

الطريقه الثانيه وتسمى separate chaining وهي بجعل خانات المصفوفه تؤشر الى linked list of words أي كل خانه في المصفوفه لديه قائمه مرتطبه به ، وفي حال وجد تصادم في الموقع 10 نقوم بادخال هذه الكلمه في أخر القائمه في الموقع 10 .

الطريقه الأولى open addressing كما ذكرنا تعمل بالبحث من الموقع الحالى عن أي خانه فارغه لكي تضيف الكلمه الجديده ، وهناك 3 طرق أيضا لهذه العمليه وكل منها تحتلف في كيفيه ايجاد الخانه الفارغه التاليه ، فالطريقه الأولى Linear Probing تقوم بالبحث خانه خانه بدءا من الخانه التي حصل فيها التصادم ، أما الطريقه الثانيه quadratic probing تقوم بزياده خطوه البحث بشكل متصاعد يكون عباره عن مضاعفات كل خانه بالشكل :1 4 9 25 وهكذا ،، الطريقه الثالثه double hashing وهي الأفضل تقريبا ، حيث تقوم باعاده حساب الhash مره أخرى (بداله أخرى) لكي يتم ايجاد الموقع الجديد للكلمه ،، ستتضح الأمور مع الأمثله الأن .

Linear Probing
في حال حدث التصادم في الخانه i ، نقوم بالبحث من الخانه i+1 عن أي خانه فارغه لكي ندخل فيها هذه القيمه الجديده ،، هذه العمليه قد تسبب مشكله ما ، مثلا الكلمه الجديده حصل لها تصادم وأضفناها في الموقع i+1 ، وجائت كلمه جديده أخرى وحصل تصادم في نفس الموقع i سوف تضاف في الخانه i+2 .. لنفرض جائت كلمه جديده وكان لها hash جديد لكنه للأسف كان يساوي i+2 وبالتالى يحدث تصادم ، وهكذا سيكبر عدد التصادمات وتضاف القيم بشكل متسلسل ، هذه المشكله تعرف بClustering



وهكذا كل ما تمتلئ المصوفه كل ما زاد الClustering ، لذلك من البدايه ذكرنا يجب أن تكون حجمها كبير حتى نتلافي هذه المشاكل .

نقوم الأن بتطبيق Linear Probe Hash Table ، وحاليا للتبسيط المصفوفه سوف تكون من Data وهو كلاس يحتوي على int :

// Linear Probe Hash Table

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

class Data {
        private:
                int value;
                
        public :
                Data(int d):value(d) { }
                void setData (int d) { value = d   ; }
                int getData () const { return value; }
};

class LinearHashTable {
        private:
                vector<Data*> hashTable;
                int size;       
                
        public :
                LinearHashTable (int size);
                        //
                void insert  (int key);
                Data* remove (int key);
                Data* find   (int key);
                        //
                friend ostream& operator << (ostream& ostr , const LinearHashTable& tbl);
                
        private :
                int hashFunction (int key);
};

LinearHashTable :: LinearHashTable (int size) {
        hashTable.resize(size);
        this->size = size;
                //
        for (int i=0; i<size; i++)
                hashTable[i] = NULL;
}

void LinearHashTable :: insert  (int key) {
        Data* data = new Data(key);
        int hash = hashFunction(key);
        
        while (hashTable[hash] != NULL && hashTable[hash]->getData() != -1) {
                hash++;
                hash %= size;
        }
        
        hashTable[hash] = data;
}

Data* LinearHashTable :: remove (int key){
        int hash = hashFunction(key);
        
        while ( hashTable[hash] != NULL  ){
                if ( hashTable[hash]->getData() == key ) {
                        Data* tmp = hashTable[hash];
                        delete hashTable[hash];
                        hashTable[hash] = new Data(-1);
                        return tmp;
                }
                
                hash++;
                hash %= size;
        }
        
        return NULL;
}

Data* LinearHashTable :: find (int key){
        int hash = hashFunction(key);
        
        while ( hashTable[hash] != NULL) {
                if ( hashTable[hash]->getData() == key)
                        return hashTable[hash];
                else {
                        hash++;
                        hash %= size;
                }
        }
        
        return NULL;
}

int LinearHashTable :: hashFunction(int key) {
        return key % size;
}

ostream& operator << (ostream& ostr , const LinearHashTable& tbl ) {
        cout << "Content: ";
        for (int i=0; i<tbl.size; i++){
                if ( tbl.hashTable[i] != NULL )
                        cout << tbl.hashTable[i]->getData() << " ";
                else
                        cout << "** ";
        }
        
        cout << endl;
        return (ostr);
}

int menu () {
        cout << "[1] insert value " << endl
                 << "[2] find value " << endl
                 << "[3] remove value " << endl
                 << "[4] display table" << endl 
                 << "[5] exit "                 << endl
                 << "  >> ";
        
        int choice;
        cin >> choice;
        return choice;
}

int main (int argc , char* argv[]) {
        cout << "Enter Size of hash : ";
        int size , key;
        cin >> size;
                //
        LinearHashTable hashTable(size);
                //
        time_t aTime;
        srand( static_cast<unsigned>(time(&aTime)));
        for (int i=0; i<size/2; i++)
                hashTable.insert( rand() % (10*size) );         
                //
        bool state = true;
        while ( state ) {
                switch (menu()) {
                        case 1 :
                                cout << "Enter key to insert: ";
                                cin >> key;
                                hashTable.insert(key);
                                break;
                        
                        case 2:
                                cout << "Enter key to find: ";
                                cin >> key;
                                if ( hashTable.find(key) != NULL )
                                        cout << "Found key " << key << endl;
                                else
                                        cout << "cannot found " << key << endl;
                                break;
                                
                        case 3:
                                cout << "Enter key to remove : ";
                                cin >> key;
                                if ( hashTable.remove(key) != NULL )
                                        cout << "remove key " << key << endl;
                                else
                                        cout << "cannot found " << key << endl;
                                break;
                                
                        case 4:
                                cout << hashTable << endl;
                                break;
                                
                        case 5 :
                                state = false;
                                break;
                }
        }
        
        return (0);
}

x+1, x+4, x+9, x+16, x+2

stepSize = constant - (key % constant);

// Double Hash Table

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

class Data {
        private:
                int value;
                
        public :
                Data(int d):value(d) { }
                void setData (int d) { value = d   ; }
                int getData () const { return value; }
};

class DoubleHashTable {
        private:
                vector<Data*> hashTable;
                int size;       
                
        public :
                DoubleHashTable (int size);
                        //
                void insert  (int key);
                Data* remove (int key);
                Data* find   (int key);
                        //
                friend ostream& operator << (ostream& ostr , const DoubleHashTable& tbl);
                
        private :
                int hashFunction (int key);
                int hashFunction2(int key);
};

DoubleHashTable :: DoubleHashTable (int size) {
        hashTable.resize(size);
        this->size = size;
                //
        for (int i=0; i<size; i++)
                hashTable[i] = NULL;
}

void DoubleHashTable :: insert  (int key) {
        Data* data = new Data(key);
        int hash = hashFunction(key);
        int step = hashFunction2(key);
        
        while (hashTable[hash] != NULL && hashTable[hash]->getData() != -1) {
                hash += step;
                hash %= size;
        }
        
        hashTable[hash] = data;
}

Data* DoubleHashTable :: remove (int key){
        int hash = hashFunction(key);
        int step = hashFunction2(key);
        
        while ( hashTable[hash] != NULL  ){
                if ( hashTable[hash]->getData() == key ) {
                        Data* tmp = hashTable[hash];
                        delete hashTable[hash];
                        hashTable[hash] = new Data(-1);
                        return tmp;
                }
                
                hash += step;
                hash %= size;
        }
        
        return NULL;
}

Data* DoubleHashTable :: find (int key){
        int hash = hashFunction(key);
        int step = hashFunction2(key);
        
        while ( hashTable[hash] != NULL) {
                if ( hashTable[hash]->getData() == key)
                        return hashTable[hash];
                else {
                        hash += step;
                        hash %= size;
                }
        }
        
        return NULL;
}

int DoubleHashTable :: hashFunction(int key) {
        return key % size;
}

int DoubleHashTable :: hashFunction2(int key) {
        return 5 - key%5;
}

ostream& operator << (ostream& ostr , const DoubleHashTable& tbl ) {
        cout << "Content: ";
        for (int i=0; i<tbl.size; i++){
                if ( tbl.hashTable[i] != NULL )
                        cout << tbl.hashTable[i]->getData() << " ";
                else
                        cout << "** ";
        }
        
        cout << endl;
        return (ostr);
}

int menu () {
        cout << "[1] insert value " << endl
                 << "[2] find value " << endl
                 << "[3] remove value " << endl
                 << "[4] display table" << endl 
                 << "[5] exit "                 << endl
                 << "  >> ";
        
        int choice;
        cin >> choice;
        return choice;
}

int main (int argc , char* argv[]) {
        cout << "Enter Size of hash : ";
        int size , key;
        cin >> size;
                //
        DoubleHashTable hashTable(size);
                //
        time_t aTime;
        srand( static_cast<unsigned>(time(&aTime)));
        for (int i=0; i<size/2; i++)
                hashTable.insert( rand() % (2*size) );          
                //
        bool state = true;
        while ( state ) {
                switch (menu()) {
                        case 1 :
                                cout << "Enter key to insert: ";
                                cin >> key;
                                hashTable.insert(key);
                                break;
                        
                        case 2:
                                cout << "Enter key to find: ";
                                cin >> key;
                                if ( hashTable.find(key) != NULL )
                                        cout << "Found key " << key << endl;
                                else
                                        cout << "cannot found " << key << endl;
                                break;
                                
                        case 3:
                                cout << "Enter key to remove : ";
                                cin >> key;
                                if ( hashTable.remove(key) != NULL )
                                        cout << "remove key " << key << endl;
                                else
                                        cout << "cannot found " << key << endl;
                                break;
                                
                        case 4:
                                cout << hashTable << endl;
                                break;
                                
                        case 5 :
                                state = false;
                                break;
                }
        }
        
        return (0);
}

الى الان تعرضنا الى طرق open addressing لحل مشكله الCollissions ، وسنعرض الأن الحل الأخر وربما الأفضل لحل مشكله التصادم وهو Separate chaining.

Separate chaining
هنا سوف تكون لدينا مصفوفه ولكن كل خانه منها تؤشر الى قائمه مرتبطه linked list ، وبالتالى بعد عمل hash لأي كلمه ومعرفه الindex سنقوم بادخال هذه الكلمه في القائمه الموجوده في الindex ، وفي حال حدث التصادم سوف نضيف الكلمه أيضا في هذه القائمه ، وبالتالى سنكون أنهينا عمليه البحث عند حدوث التصادم ،



الLoad Factors هنا لا يهم اطلاقا ، وليس كما كان عندما كنا نستخدم أحد طرق الـopen addressing حيث يجب أن تكون عدد الخانات الممتلئه فيها على الأكثر2/3 ، أما في الSeparate chaining فلا مشكله وحتى اذا كانت المصفوفه ممتلئه كليا لأن أي خانه تحتوي على العديد من القيم (في القائمه) ،، لذلك نستخدم هذه الطريقه خصوصا في حال كنا لا نعلم عدد العناصر التي يجب وضعها في المصفوفه قبل البدء في البرنامج لأن الأمتلاء هنا لا يمثل مشكله ،،

تطبيق بسيط لل HashTable باستخدام Separate Chaining :

//separate chaining
#include <iostream>
#include <vector>
using namespace std;

class Data {
        private:
                int value;
                Data* next;
                
        public :
                Data(int d):value(d),next(NULL) { }
                        //
                void setData (int d) { value = d   ; }
                int getData () const { return value; }
                        //
                void setNext (Data* d) { next = d; }
                Data* getNext () const { return next; }
};

class SortedLinkedList {
        private:
                Data* first;
                
        public :
                SortedLinkedList();
                        //
                void insert (int key);
                void remove (int key);
                Data* find  (int key);
                        //
                friend ostream& operator << (ostream& ostr , const SortedLinkedList& list);
};

SortedLinkedList :: SortedLinkedList (){
        first = NULL;
}

void SortedLinkedList :: insert (int key){
        Data* data = new Data(key);
                //
        Data* prev = NULL;
        Data* current = first;
        
        while ( current != NULL && key > current->getData()) {
                prev = current;
                current = current->getNext();
        }
        
        if ( prev == NULL )
                first = data;
        else
                prev->setNext(data);
                
        data->setNext(current);
}

void SortedLinkedList :: remove (int key) {
        Data* data = new Data(key);
                //
        Data* prev = NULL;
        Data* current = first;
        
        while ( current != NULL && key != current->getData()) {
                prev = current;
                current = current->getNext();
        }
        
        if ( prev == NULL)
                first = first->getNext();
        else
                prev->setNext(current->getNext());
}

Data* SortedLinkedList :: find (int key) {
        Data* current = first;
        
        while ( current != NULL && current->getData() <= key) {
                if ( current->getData() == key )
                        return current;
                current = current->getNext();
        }
        
        return NULL;
}

ostream& operator << (ostream& ostr , const SortedLinkedList& list) {
        ostr << "Content: ";
        Data* current = list.first;
        
        while ( current != NULL ) {
                ostr << current->getData() << " ";
                current = current->getNext();
        }
        
        ostr << endl;
        return ostr;
}


class HashTable {
        private:
                vector<SortedLinkedList*> hashTable;
                int size;       
                
        public :
                HashTable (int size);
                        //
                void insert  (int key);
                void remove (int key);
                Data* find   (int key);
                        //
                friend ostream& operator << (ostream& ostr , const HashTable& tbl);
                
        private :
                int hashFunction (int key);
};

HashTable :: HashTable (int size) {
        hashTable.resize(size);
        this->size = size;
                //
        for (int i=0; i<size; i++)
                hashTable[i] = new SortedLinkedList;
}

void HashTable :: insert  (int key) {
        int hash = hashFunction(key);
        hashTable[hash]->insert(key); 
}

void HashTable :: remove (int key){
        int hash = hashFunction(key);
        hashTable[hash]->remove(key); 
}

Data* HashTable :: find (int key){
        int hash = hashFunction(key);
        return hashTable[hash]->find(key);  
}

int HashTable :: hashFunction(int key) {
        return key % size;
}

ostream& operator << (ostream& ostr , const HashTable& tbl ) {
        
        for (int i=0; i<tbl.size; i++){
                if ( tbl.hashTable[i] != NULL )
                        cout << i << " : " << *tbl.hashTable[i] << " ";
                else
                        cout << "** ";
        }
        
        cout << endl;
        return (ostr);
}

int menu () {
        cout << "[1] insert value " << endl
                 << "[2] find value " << endl
                 << "[3] remove value " << endl
                 << "[4] display table" << endl 
                 << "[5] exit "                 << endl
                 << "  >> ";
        
        int choice;
        cin >> choice;
        return choice;
}

int main (int argc , char* argv[]) {
        cout << "Enter Size of hash : ";
        int size , key;
        cin >> size;
                //
        HashTable hashTable(size);
                //
        time_t aTime;
        srand( static_cast<unsigned>(time(&aTime)));
        for (int i=0; i<size/2; i++)
                hashTable.insert( rand() % (100*size) );                
                //
        bool state = true;
        while ( state ) {
                switch (menu()) {
                        case 1 :
                                cout << "Enter key to insert: ";
                                cin >> key;
                                hashTable.insert(key);
                                break;
                        
                        case 2:
                                cout << "Enter key to find: ";
                                cin >> key;
                                if ( hashTable.find(key) != NULL )
                                        cout << "Found key " << key << endl;
                                else
                                        cout << "cannot found " << key << endl;
                                break;
                                
                        case 3:
                                cout << "Enter key to remove : ";
                                cin >> key;
                                hashTable.remove(key);
                                break;
                                
                        case 4:
                                cout << hashTable << endl;
                                break;
                                
                        case 5 :
                                state = false;
                                break;
                }
        }
        
        return (0);
}