C++ implements an instance of the hash table

  • 2020-05-27 06:50:20
  • OfStack

C++ implements an instance of the hash table

The hash function of the hash table adopts the division hash function, the multiplication hash function, the universal hash function, and each slot is realized by using the ordered one-way linked list.

Implementation code:

LinkNode.h




#include<iostream> 
using namespace std; 
class Link; 
class LinkNode 
{ 
private: 
  int key; 
  LinkNode* next; 
  friend Link; 
public: 
  LinkNode():key(-1),next(NULL){} 
  LinkNode(int num):key(num),next(NULL){} 
  int Getkey() 
  { 
    return key; 
  } 
 
}; 

Link.h


#include"LinkNode.h" 
class Hash; 
class Link 
{ 
private: 
  friend Hash; 
  LinkNode* head; 
  int length; 
public: 
  Link():head(NULL),length(0) 
  {} 
  Link(LinkNode* node):head(node) 
  { 
    length+=1; 
  } 
  ~Link() 
  { 
    MakeEmpty(); 
  } 
  void MakeEmpty() 
  { 
    if(head==NULL) 
      return ; 
    LinkNode* p=head; 
    while(p) 
    { 
      head=head->next; 
      delete p; 
      p=head; 
    } 
  } 
  int GetLength() 
  { 
    return length; 
  } 
  void Insert(int num) 
  { 
    length++; 
    LinkNode* p=new LinkNode(num); 
    if(head==NULL) 
    { 
      head=p; 
      return ; 
    } 
    LinkNode* q=head,*t=head->next; 
    if(q->key>num) 
    { 
      head=p; 
      head->next=q; 
      return ; 
    } 
    while(t) 
    { 
      if(t->key>=num) 
      { 
        q->next=p; 
        p->next=t; 
        return ; 
      } 
      else 
      { 
        q=t; 
        t=t->next; 
      } 
    } 
    q->next=p; 
  } 
  bool Delete(int num) 
  { 
    if(head==NULL) 
    { 
      cout<<"the link is empty!"<<endl; 
      return 0; 
    } 
    LinkNode* p=head,*t=head->next; 
    if(p->key==num) 
    { 
      head=head->next; 
      delete p; 
      length--; 
      return 1; 
    } 
    while(t) 
    { 
      if(t->key==num) 
      { 
        p->next=t->next; 
        delete t; 
        length--; 
        return 1; 
      } 
      else if(t->key<num) 
      { 
        p=t; 
        t=t->next; 
      } 
    } 
    return 0; 
  } 
  int Search(int num) 
  { 
    LinkNode* p=head; 
    while(p) 
    { 
      if(p->key==num) 
      { 
        return num; 
      } 
      else if(p->key<num) 
      { 
        p=p->next; 
      } 
      else 
      { 
        return 0; 
      } 
    } 
    return 0; 
  } 
  bool IsEmpty() 
  { 
    if(head==NULL) 
    { 
      return 1; 
    } 
    else 
      return 0; 
  } 
  void Print(int num) 
  { 
    if(head==NULL) 
    { 
      cout<<"the"<<num<<"th link is null!"<<endl; 
    } 
    LinkNode* p=head; 
    while(p) 
    { 
      cout<<p->key<<" "; 
      p=p->next; 
    } 
    cout<<endl; 
  } 
}; 

Hash.h

Each element in the Hash table stores one linked list


#include"Link.h" 
class Hash 
{ 
private: 
  Link*Table; 
public: 
  Hash(int num):Table(new Link [num]){} 
  ~Hash() 
  { 
    delete [] Table; 
  } 
  // Division hash  
  int H1(int num,int m) 
  { 
    return num%m; 
  } 
  // Multiplication hash  
  int H2(int num,float A,int m) 
  { 
    float fnum=(float)num; 
    float re=((fnum*A)-(int)(fnum*A))*m; 
    return (int)re; 
  } 
  // The whole domain hash  
  int H3(int num,int p,int m) 
  { 
    int a,b; 
    a=rand()%p; 
    b=rand()%p; 
    return ((a*num+b)%p)%m; 
  } 
  void Insert(int num,int n) 
  { 
    int key; 
     
    if(n==1) 
    { 
      key=H1(num,17); 
    } 
    else if(n==2) 
    { 
      key=H2(num,0.618033,17); 
    } 
    else 
    { 
      key=H3(num,701,17); 
    } 
    Table[key].Insert(num); 
  } 
  bool Delete(int num,int n) 
  { 
    int key;   
    if(n==1) 
    { 
      key=H1(num,17); 
    } 
    else if(n==2) 
    { 
      key=H2(num,0.618033,17); 
    } 
    else 
    { 
      key=H3(num,701,17); 
    } 
    return Table[key].Delete(num); 
  } 
  int Search(int num,int n) 
  { 
    int key; 
     
    if(n==1) 
    { 
      key=H1(num,17); 
    } 
    else if(n==2) 
    { 
      key=H2(num,0.618033,17); 
    } 
    else 
    { 
      key=H3(num,701,17); 
    } 
      if(Table[key].Search(num)!=0) 
      { 
        return key+1; 
      } 
      else 
        return -1; 
  } 
  void Print(int num) 
  { 
    int i; 
    for(i=0;i<num;i++) 
    { 
      if(Table[i].IsEmpty()) 
        continue; 
      Table[i].Print(i); 
    } 
  } 
}; 

main.h


#include"Hash.h" 
int main() 
{ 
  Hash hash(1000),ha(100),sh(100); 
  int a[15]={15,6,9,4,7,32,569,419,78,125,635,46,456,16,457}; 
  int i; 
  for(i=0;i<15;i++) 
  { 
    hash.Insert(a[i],1); 
  } 
   
  for(i=0;i<15;i++) 
  { 
    ha.Insert(a[i],2); 
  } 
  cout<<endl; 
  for(i=0;i<15;i++) 
  { 
    sh.Insert(a[i],3); 
  } 
  hash.Print(1000); 
  cout<<endl; 
  ha.Print(100); 
  cout<<endl; 
  sh.Print(100); 
  cout<<endl; 
  cout<<hash.Search(46,1)<<endl; 
  if(hash.Delete(125,1)) 
  { 
    cout<<hash.Search(125,1)<<endl; 
  } 
} 


The above is C++ implementation of the hash table example, if you have any questions please leave a message or to the site community exchange discussion, thank you for reading, hope to help you, thank you for your support of the site!


Related articles: