Пример реализации хэш-таблицы с открытым хэшированием

hash_table_open_impl.cpp

#include "hash_table.hpp"

#include <cassert>

#include <cstring>

structHashTable

{

structElement

{

intm_key;

intm_value;

Element* m_pNext;

};

intm_tableSize;

intm_numElements;

Element** m_pData;

};

// Функция создания новой хэш-таблицы

HashTable* HashTableCreate ( int_initialSize )

{

HashTable * ht = newHashTable;

ht->m_tableSize = _initialSize;

ht->m_numElements = 0;

ht->m_pData = newHashTable::Element*[ ht->m_tableSize ];

memset( ht->m_pData, 0, sizeof( HashTable::Element* ) * ht->m_tableSize );

returnht;

}

// Функция уничтожения хэш-таблицы

voidHashTableDestroy ( HashTable* _pHT )

{

HashTableClear( * _pHT );

delete[] _pHT->m_pData;

delete_pHT;

}

// Функция очистки хэш-таблицы

voidHashTableClear ( HashTable & _ht )

{

_ht.m_numElements = 0;

for( inti = 0; i < _ht.m_tableSize; i++ )

{

HashTable::Element* element = _ht.m_pData[ i ];

while( element )

{

HashTable::Element* temp = element->m_pNext;

deleteelement;

element = temp;

}

_ht.m_pData[ i ] = nullptr;

}

}

// Функция получения количества хранимых пар ключ-значение

intHashTableNumElements ( constHashTable & _ht )

{

return_ht.m_numElements;

}

// Функция вычисления хэш-кода для ключа - для чисел может быть такой тривиальной.

// Для других типов ключей в подобной функции следует реализовать подходящую логику.

unsigned intHashCode ( int _key )

{

unsigned inthashCode = _key;

returnhashCode;

}

// Функция создания нового элемента хэш-таблицы

HashTable::Element* HashTableMakeElement ( int_key, int_value, HashTable::Element* _next )

{

HashTable::Element* newElement = newHashTable::Element;

newElement->m_key = _key;

newElement->m_value = _value;

newElement->m_pNext = _next;

returnnewElement;

}

// Функция вставки новой пары ключ-значение в хэш-таблицу

voidHashTableInsert ( HashTable & _ht, int_key, int_value )

{

unsigned inthashCode = HashCode( _key );

intbucketNr = hashCode % _ht.m_tableSize;

HashTable::Element* element = _ht.m_pData[ bucketNr ];

if( !element )

{

_ht.m_pData[ bucketNr ] = HashTableMakeElement( _key, _value, nullptr );

_ht.m_numElements++;

}

Else

{

HashTable::Element* prevElement = nullptr;

while( element )

{

if( element->m_key == _key )

{

element->m_value = _value;

return;

}

else if( element->m_key > _key )

{

HashTable::Element* newElement = HashTableMakeElement( _key, _value, element );

if( prevElement )

prevElement->m_pNext = newElement;

Else

_ht.m_pData[ bucketNr ] = newElement;

_ht.m_numElements++;

return;

}

else if( !element->m_pNext )

{

_ht.m_numElements++;

element->m_pNext = HashTableMakeElement( _key, _value, nullptr);

return;

}

prevElement = element;

element = element->m_pNext;

}

}

}

// Функция получения значения из хэш-таблицы по ключу

intHashTableGet ( constHashTable & _ht, int_key )

{

unsigned inthashCode = HashCode( _key );

intbucketNr = hashCode % _ht.m_tableSize;

constHashTable::Element* element = _ht.m_pData[ bucketNr ];

while( element )

{

if( element->m_key == _key )

returnelement->m_value;

else if( element->m_key > _key )

break;

element = element->m_pNext;

}

return-1;

}

// Функция удаления пары ключ-значение из хэш-таблицы по ключу

voidHashTableRemoveKey ( HashTable & _ht, int_key )

{

unsigned inthashCode = HashCode( _key );

intbucketNr = hashCode % _ht.m_tableSize;

HashTable::Element* element = _ht.m_pData[ bucketNr ];

HashTable::Element* prevElement = nullptr;

while( element )

{

if( element->m_key == _key )

{

if( prevElement )

prevElement->m_pNext = element->m_pNext;

Else

_ht.m_pData[ bucketNr ] = element->m_pNext;

deleteelement;

_ht.m_numElements--;

return;

}

else if( element->m_key > _key )

break;

prevElement = element;

element = element->m_pNext;

}

}