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

hash_table_closed_impl.cpp

#include "hash_table.hpp"

#include <cassert>

struct HashTable

{

structElement

{

intm_key;

intm_value;

enum{ NOT_OCCUPIED, OCCUPIED, DELETED } m_status;

};

intm_tableSize;

intm_numOccupied;

Element* m_pData;

};

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

HashTable* HashTableCreate ( int_initialSize )

{

HashTable * pNewHT = newHashTable;

pNewHT->m_tableSize = _initialSize;

pNewHT->m_pData = newHashTable::Element[ pNewHT->m_tableSize ];

HashTableClear( * pNewHT );

returnpNewHT;

}

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

voidHashTableDestroy ( HashTable* _pHT )

{

delete[] _pHT->m_pData;

delete_pHT;

}

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

voidHashTableClear ( HashTable & _ht )

{

_ht.m_numOccupied = 0;

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

_ht.m_pData[ i ].m_status = HashTable::Element::NOT_OCCUPIED;

}

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

intHashTableNumElements ( constHashTable & _ht )

{

return_ht.m_numOccupied;

}

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

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

unsigned intHashCode ( int_key )

{

unsigned inthashCode = _key;

returnhashCode;

}

// Вспомогательная функция для вставки пары ключ-значение в конкретную ячейку хэш-таблицы

boolHashTableTryInsertElement ( HashTable & _ht, int_bucketNr, int_key, int_value )

{

if( _ht.m_pData[ _bucketNr ].m_status != HashTable::Element::OCCUPIED )

{

_ht.m_pData[ _bucketNr ].m_status = HashTable::Element::OCCUPIED;

_ht.m_pData[ _bucketNr ].m_key = _key;

_ht.m_pData[ _bucketNr ].m_value = _value;

_ht.m_numOccupied++;

return true;

}

else if( _ht.m_pData[ _bucketNr ].m_key == _key )

{

_ht.m_pData[ _bucketNr ].m_value = _value;

return true;

}

Else

return false;

}

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

voidHashTableDoubleSize ( HashTable & _ht )

{

intoldSize = _ht.m_tableSize;

_ht.m_tableSize <<= 1;

HashTable::Element* oldData = _ht.m_pData;

_ht.m_pData = newHashTable::Element[ _ht.m_tableSize ];

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

_ht.m_pData[ i ].m_status = HashTable::Element::NOT_OCCUPIED;

_ht.m_numOccupied = 0;

for( inti = 0; i < oldSize; i++ )

if( oldData[ i ].m_status == HashTable::Element::OCCUPIED )

HashTableInsert( _ht, oldData[ i ].m_key, oldData[ i ].m_value );

delete[] oldData;

}

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

void HashTableInsert ( HashTable & _ht, int_key, int_value )

{

if( ( _ht.m_numOccupied << 1 ) >= _ht.m_tableSize )

HashTableDoubleSize( _ht );

unsigned inthashCode = HashCode( _key );

intbucketNr = hashCode % _ht.m_tableSize;

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

if( HashTableTryInsertElement( _ht, i, _key, _value ) )

return;

for( inti = 0; i < bucketNr; i++ )

if( HashTableTryInsertElement( _ht, i, _key, _value ) )

return;

}

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

intHashTableGet ( constHashTable & _ht, int_key )

{

unsigned inthashCode = HashCode( _key );

intbucketNr = hashCode % _ht.m_tableSize;

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

if( _ht.m_pData[ i ].m_status == HashTable::Element::NOT_OCCUPIED )

break;

else if ( _ht.m_pData[ i ].m_status == HashTable::Element::OCCUPIED &&

_ht.m_pData[ i ].m_key == _key )

return_ht.m_pData[ i ].m_value;

for( inti = 0; i < bucketNr; i++ )

if( _ht.m_pData[ i ].m_status == HashTable::Element::NOT_OCCUPIED )

break;

else if( _ht.m_pData[ i ].m_status == HashTable::Element::OCCUPIED &&

_ht.m_pData[ i ].m_key == _key )

return_ht.m_pData[ i ].m_value;

return-1;

}

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

voidHashTableRemoveKey ( HashTable & _ht, int_key )

{

unsigned inthashCode = HashCode( _key );

intbucketNr = hashCode % _ht.m_tableSize;

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

if( _ht.m_pData[ i ].m_status == HashTable::Element::OCCUPIED &&

_ht.m_pData[ i ].m_key == _key )

{

_ht.m_pData[ i ].m_status = HashTable::Element::DELETED;

--_ht.m_numOccupied;

return;

}

for( inti = 0; i < bucketNr; i++ )

if( _ht.m_pData[ i ].m_status == HashTable::Element::OCCUPIED &&

_ht.m_pData[ i ].m_key == _key )

{

_ht.m_pData[ i ].m_status = HashTable::Element::DELETED;

--_ht.m_numOccupied;

return;

}

assert( !"key not found" );

}