hash_table Class


Class Documentation

By using or copying this Software, Licensee agrees to abide by the intellectual property laws, and all other applicable laws of the U.S., and the terms of this license. Template based bucket hashing class. Hashes on input string. The template <Type> defines the type of the constructed bucket for each entry. Requirements on <Type>: void set_key(char *key): initializes text key in <Type> int test_key(char *key): returns strcmp(key,x) where x is internal pointer to text string <Type> constructor assumed to require no arguments Defines functions: hash_look(key): look up "key" in the hash table dump(): dump the entries in the hash table (assumes that << is defined for the instantiated <Type>.


Class Declaration

 
  
 class hash_table { 
      
 public: 
      
     Type *hash_look() {return NULL;}; 
      
     Type *hash_look(char *text) { 
 	int key; 
 	int i; 
 	Type *wk; 
 	 
 	key = 0; 
 	for (i = 0; i<strlen(text); i++) { 
 	    key = ((key << 1 ) + text[i]) % ht_size; 
 	}; 
 	 
 	for (wk=ht[key].first(); 
 	     wk!=NULL && wk->test_key(text); 
 	     wk=ht[key].successor(wk)) {}; 
 	 
 	if (wk == NULL) { 
 	    wk = new Type(); 
 	    wk->set_key(text); 
 	    ht[key].append(wk); 
 	}; 
 	 
 	return wk; 
     }; 
      
      
      
     void dump() { 
 	int i; 
 	Type *wk; 
 	for (i=0; i<ht_size; i++) { 
 	    if (ht[i].num_elements() != 0) { 
 		cout << "ht[" << i << "] ="; 
 		for (wk=ht[i].first(); wk!=NULL; wk=ht[i].successor(wk)) { 
 		    cout << " "; 
 //		    cout << wk; 
 		}; 
 		cout << "\n"; 
 	    }; 
 	};       
     }; 
      
      
     hash_table(int table_size = 4093) : ht_size(table_size) { 
 //	int i; 
 //	for (i=0; i<ht_size; i++) {ht[i] = new dl_list<Type>}; 
 	ht = new dl_list<Type>[ht_size]; 
     }; 
      
     virtual ~hash_table() { 
 //	delete [] ht; 
     }; 
      
 private: 
     const int ht_size; 
     dl_list<Type> *ht; 
      
 }; 
 


Back to Main.
MTL Systems, Inc.