织梦CMS - 轻松建站从此开始!

罗索

C++ Program to Implement Hash Tables

jackyhwei 发布于 2021-06-26 16:05 点击:次 
Hash function is used by hash table to compute an index into an array in which an element will be inserted or searched.
TAG: hashtable  

A hash table is a data structure which is used to store key-value pairs. Hash function is used by hash table to compute an index into an array in which an element will be inserted or searched.

This is a C++ program to Implement Hash Tables.

Algorithm

  1. Begin 
  2.    Initialize the table size T_S to some integer value. 
  3.    Create a structure hashTableEntry to declare key k and value v. 
  4.    Create a class hashMapTable: 
  5.    Create a constructor hashMapTable to create the table. 
  6.    Create a hashFunc() function which return key mod T_S. 
  7.    Create a function Insert() to insert element at a key. 
  8.    Create a function SearchKey() to search element at a key. 
  9.    Create a function Remove() to remove element at a key. 
  10.    Call a destructor hashMapTable to destroy the objects created by the constructor. 
  11.    In main, perform switch operation and enter input as per choice. 
  12.    To insert key and values, call insert(). 
  13.    To search element, call SearchKey(). 
  14.    To remove element, call Remove(). 
  15. End. 

Example Code

  1. #include<iostream> 
  2. #include<cstdlib> 
  3. #include<string> 
  4. #include<cstdio> 
  5. using namespace std; 
  6. const int T_S = 200
  7. class HashTableEntry { 
  8.    public: 
  9.       int k; 
  10.       int v; 
  11.       HashTableEntry(int k, int v) { 
  12.          this->kk= k; 
  13.          this->vv = v; 
  14.       } 
  15. }; 
  16. class HashMapTable { 
  17.    private: 
  18.       HashTableEntry **t; 
  19.    public: 
  20.       HashMapTable() { 
  21.          t = new HashTableEntry * [T_S]; 
  22.          for (int i = 0; i< T_S; i++) { 
  23.             t[i] = NULL; 
  24.          } 
  25.       } 
  26.       int HashFunc(int k) { 
  27.          return k % T_S; 
  28.       } 
  29.       void Insert(int k, int v) { 
  30.          int h = HashFunc(k); 
  31.          while (t[h] != NULL && t[h]->k != k) { 
  32.             h = HashFunc(h + 1); 
  33.          } 
  34.          if (t[h] != NULL) 
  35.             delete t[h]; 
  36.          t[h] = new HashTableEntry(k, v); 
  37.       } 
  38.       int SearchKey(int k) { 
  39.          int h = HashFunc(k); 
  40.          while (t[h] != NULL && t[h]->k != k) { 
  41.             h = HashFunc(h + 1); 
  42.          } 
  43.          if (t[h] == NULL) 
  44.             return -1; 
  45.          else 
  46.             return t[h]->v; 
  47.       } 
  48.       void Remove(int k) { 
  49.          int h = HashFunc(k); 
  50.          while (t[h] != NULL) { 
  51.             if (t[h]->k == k) 
  52.                break; 
  53.             h = HashFunc(h + 1); 
  54.          } 
  55.          if (t[h] == NULL) { 
  56.             cout<<"No Element found at key "<<k<<endl
  57.             return; 
  58.          } else { 
  59.             delete t[h]; 
  60.          } 
  61.          cout<<"Element Deleted"<<endl
  62.       } 
  63.       ~HashMapTable() { 
  64.          for (int i = 0; i < T_S; i++) { 
  65.             if (t[i] != NULL) 
  66.                delete t[i]; 
  67.                delete[] t; 
  68.          } 
  69.       } 
  70. }; 
  71. int main() { 
  72.    HashMapTable hash; 
  73.    int k, v; 
  74.    int c; 
  75.    while (1) { 
  76.       cout<<"1.Insert element into the table"<<endl
  77.       cout<<"2.Search element from the key"<<endl
  78.       cout<<"3.Delete element at a key"<<endl
  79.       cout<<"4.Exit"<<endl
  80.       cout<<"Enter your choice: "; 
  81.       cin>>c; 
  82.       switch(c) { 
  83.          case 1: 
  84.             cout<<"Enter element to be inserted: "; 
  85.             cin>>v; 
  86.             cout<<"Enter key at which element to be inserted: "; 
  87.             cin>>k; 
  88.             hash.Insert(k, v); 
  89.          break; 
  90.          case 2: 
  91.             cout<<"Enter key of the element to be searched: "; 
  92.             cin>>k; 
  93.             if (hash.SearchKey(k) == -1) { 
  94.                cout<<"No element found at key "<<k<<endl
  95.                continue; 
  96.             } else { 
  97.                cout<<"Element at key "<<k<<" : "; 
  98.                cout<<hash.SearchKey(k)<<endl
  99.             } 
  100.          break; 
  101.          case 3: 
  102.             cout<<"Enter key of the element to be deleted: "; 
  103.             cin>>k; 
  104.             hash.Remove(k); 
  105.          break; 
  106.          case 4: 
  107.             exit(1); 
  108.          default: 
  109.             cout<<"\nEnter correct option\n"; 
  110.       } 
  111.    } 
  112.    return 0; 

Output

  1. 1.Insert element into the table 
  2. 2.Search element from the key 
  3. 3.Delete element at a key 
  4. 4.Exit 
  5. Enter your choice: 1 
  6. Enter element to be inserted: 1 
  7. Enter key at which element to be inserted: 1 
  8. 1.Insert element into the table 
  9. 2.Search element from the key 
  10. 3.Delete element at a key 
  11. 4.Exit 
  12. Enter your choice: 1 
  13. Enter element to be inserted: 2 
  14. Enter key at which element to be inserted: 2 
  15. 1.Insert element into the table 
  16. 2.Search element from the key 
  17. 3.Delete element at a key 
  18. 4.Exit 
  19. Enter your choice: 1 
  20. Enter element to be inserted: 4 
  21. Enter key at which element to be inserted: 5 
  22. 1.Insert element into the table 
  23. 2.Search element from the key 
  24. 3.Delete element at a key 
  25. 4.Exit 
  26. Enter your choice: 1 
  27. Enter element to be inserted: 7 
  28. Enter key at which element to be inserted: 6 
  29. 1.Insert element into the table 
  30. 2.Search element from the key 
  31. 3.Delete element at a key 
  32. 4.Exit 
  33. Enter your choice: 2 
  34. Enter key of the element to be searched: 7 
  35. No element found at key 7 
  36. 1.Insert element into the table 
  37. 2.Search element from the key 
  38. 3.Delete element at a key 
  39. 4.Exit 
  40. Enter your choice: 2 
  41. Enter key of the element to be searched: 6 
  42. Element at key 6 : 7 
  43. 1.Insert element into the table 
  44. 2.Search element from the key 
  45. 3.Delete element at a key 
  46. 4.Exit 
  47. Enter your choice: 3 
  48. Enter key of the element to be deleted: 1 
  49. Element Deleted 
  50. 1.Insert element into the table 
  51. 2.Search element from the key 
  52. 3.Delete element at a key 
  53. 4.Exit 
  54. Enter your choice: 4 
(Karthikeya Boyini)
本站文章除注明转载外,均为本站原创或编译欢迎任何形式的转载,但请务必注明出处,尊重他人劳动,同学习共成长。转载请注明:文章转载自:罗索实验室 [http://www.rosoo.net/a/202106/17840.html]
本文出处:tutorialspoint 作者:Karthikeya Boyini 原文
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
相关文章
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
栏目列表
将本文分享到微信
织梦二维码生成器
推荐内容