Data structures: Hash Table

Хэш-таблица - один из вариантов ассоциативного массива.

Работает достаточно просто: по значению ключа рассчитывается хэш-код. Хэш-код в данном случае является индексом массива. Таким образом в идеале доступ к значению занимает время, равное O(1). В идеале, потому что редко бывает так, чтобы одному хэш-коду соответствовал один ключ. И в "реальной жизни" доступ занимает время равное O(k), где k - количество ключей соответствующих одному хэш-коду.
Реализация хэш-таблицы. В данном коде поддерживаются только строковые и целочисленные ключи. При желании можно прикрутить многие другие. 

#ifndef HASH_TABLE
#define HASH_TABLE

// for int keys

int hash_func(int alphabet_length,  int key)
{
 
 int result=0;

 char *str;

 str=new char[8];

 memset(str,'\0',8);
 itoa(key, str,10); 
 
  
 for (int i=0; i<strlen(str); i++)
 {
  int ld=strlen(str)-(i+1);
  result=result+(std::pow((double)alphabet_length, ld)*((int)str[i]));  
 };
  
 return std::abs(result);
};

// for string keys

int hash_func(int alphabet_length,  char* key)
{
 
 int result=0;

  
 for (int i=0; i<strlen(key); i++)
 {
  int ld=strlen(key)-(i+1);
  result=result+(std::pow((double)alphabet_length, ld)*((int)key[i]));  
 };
  
 return std::abs(result);
};

//chaining method

template<typename KeyType, typename ItemType>

struct hash_table_entry
{
 KeyType Key;
 ItemType Item;

 hash_table_entry *Next;

 hash_table_entry()
 {
  Next=NULL;
 }; 
};

template<typename KeyType, typename ItemType>
// only int and char* key types are supported

struct hash_table
{
 hash_table_entry<KeyType,ItemType> **records;
 
 int alphabet_length;
 int TABLE_SIZE;

 hash_table(int table_size)
 {
  TABLE_SIZE=table_size;
  alphabet_length=26;

  records=new hash_table_entry<KeyType, ItemType>*[table_size];
    
  for (int i=0; i<table_size; i++)
  {
   records[i]=0;
  };
 };
 
 hash_table(int table_size, int alphabet)
 {
  
     TABLE_SIZE=table_size;
  alphabet_length=alphabet;

  records=new hash_table_entry<KeyType, ItemType>*[table_size];
    
  for (int i=0; i<table_size; i++)
  {
   records[i]=0;
  };
 
 };
 
 ~hash_table()
 {
  delete[] records;
 };

 void add_new_item(KeyType key, ItemType item)
 {
  hash_table_entry<KeyType,ItemType> *k;
      
  int hash_code=hash_func(alphabet_length, key) % TABLE_SIZE;
  
  k=records[hash_code];

  
         if (k==NULL)
          {
               k=new hash_table_entry<KeyType,ItemType>();
              
      k->Key=key;
      k->Item=item;
              
      records[hash_code]=k;
          }
          else
          {
               while(k->Next!=NULL)
               {
                   k=k->Next;
               };
    
               k=(k->Next=new hash_table_entry<KeyType,ItemType>());
      k->Key=key;
      k->Item=item;
           };
 };

 void delete_item(KeyType key)
 {
  hash_table_entry<KeyType,ItemType> *k,*tmp;
      
  int hash_code=hash_func(alphabet_length, key) % TABLE_SIZE;
  
  k=records[hash_code];

  if(k!=NULL)
  {
   if (k->Key==key)
   {
    tmp=k->Next;
    k=NULL;
    records[hash_code]=tmp; 
   }
   else if(k->Next!=NULL)
   {
      while (k->Next->Key!=key)
    {
     k=k->Next;
    };
   
    tmp=k->Next->Next;
    k->Next=NULL;
    k->Next=tmp;
   };
  };
 };
 
 ItemType get_entry(KeyType key)
 {
  int hash_code=hash_func(alphabet_length, key) % TABLE_SIZE;
  hash_table_entry<KeyType,ItemType> *k=records[hash_code];
   
  while (k!=NULL)
  {
   if (k->Key==key)
   {
    return k->Item;
   }
   else
   {
    k=k->Next;
   };
  };

  return NULL;
 };

 void print_table()
 {
  for (int i=0; i<TABLE_SIZE; i++)
  {
   
   hash_table_entry<KeyType, ItemType> *tmp=new hash_table_entry<KeyType,ItemType>();

   tmp=records[i];
   
   std::cout << "index: " << i;

   while (tmp!=NULL)
   {
    std::cout <<" key: " << tmp->Key << " item: " << tmp->Item << std::endl;
    
    tmp=tmp->Next;
   };
   
  std::cout << std::endl;
  
  };
 };
};

// open addressing method

template <typename KeyType, typename ItemType>

struct table_entry_open
{
 KeyType Key;
 ItemType Item;
 
 table_entry_open()
 {
  Key=NULL;
  Item=NULL;
 };

 bool IsNull()
 {
  return (Key==NULL?true:false);
 };

 void Reset() // Erase entry and set to NULL values
 {
  Key=NULL;
  Item=NULL;
 };
};

template <typename KeyType, typename ItemType>

struct hash_table_open
{ 
 int TABLE_SIZE;
 int DOUBLE_SIZE;
 int alphabet_length;

 table_entry_open<KeyType,ItemType> *records;

 hash_table_open(int table_size=0, int alph_len=26)
 {
  DOUBLE_SIZE=table_size*2;

  records=new table_entry_open<KeyType,ItemType>[DOUBLE_SIZE]; 
  TABLE_SIZE=table_size; 
  alphabet_length=alph_len;
 };

 void add_item(KeyType key, ItemType item)
 {
  int hash_code=hash_func(alphabet_length, key) % DOUBLE_SIZE;     
  
  while(!records[hash_code].IsNull())
  {
   hash_code++;
  }

  records[hash_code].Key=key;
  records[hash_code].Item=item;
 };

 void delete_item(KeyType key)
 {
  int hash_code=hash_func(alphabet_length, key) % DOUBLE_SIZE;     
  
  while(!records[hash_code].IsNull())
  {
   if (records[hash_code].Key==key)
   {
    records[hash_code].Reset();
    break;
   };

   hash_code++;

   if(hash_code==DOUBLE_SIZE)
   {
    return;
   };
  };
  
  // recreate table order for saving integrity

  while(!records[hash_code+1].IsNull())
  {
   KeyType tmp_key=records[hash_code+1].Key;
   ItemType tmp_item=records[hash_code+1].Item;
   
   records[hash_code+1].Reset(); 
   
   add_item(tmp_key,tmp_item);

   hash_code++;
  };
 };

 ItemType get_value(KeyType key)
 {
  int hash_code=hash_func(alphabet_length,key) % DOUBLE_SIZE;

  while (!records[hash_code].IsNull())
  {
   if(records[hash_code].Key==key) return records[hash_code].Item;
   hash_code++;
  };

  return NULL;
 };

 void print_table()
 {
  for (int i=0; i<DOUBLE_SIZE; i++)
  {
   if (!records[i].IsNull())
   {
    std::cout << "Hash code: " << i << " Key: " << records[i].Key << " Item: " << records[i].Item << std::endl;
   }
   else
   {
    std::cout << "NULL " << "NULL " << std::endl;
   };
  };
 };
};
#endif