|
|
|
JHashtable
#include "JHashtable.h"
template <class KeyType, class ObjType>
JHashtable<KeyType,ObjType>::JHashtable( UINT initialCapacity, float loadFactor )
{
if ( loadFactor <= 0.0 )
{
cerr << "Bad Argument for loadFactor" << endl;
exit(1);
}
m_count = 0;
m_tableSize = initialCapacity;
m_loadFactor = loadFactor;
m_threshold = (UINT)(initialCapacity * loadFactor);
//initialize and set to null
//==========================
m_table = new JHashtableEntry*[m_tableSize];
memset( m_table, 0, sizeof(JHashtableEntry*) * m_tableSize );
//nullify the user hash function pointer
UserHash = NULL;
}
template <class KeyType, class ObjType>
JHashtable<KeyType,ObjType>::~JHashtable( )
{
clear();
delete [] m_table;
}
template <class KeyType, class ObjType>
bool
JHashtable<KeyType,ObjType>::contains( const ObjType& value ) const
{
JHashtableEntry** tab = m_table;
for( UINT i = 0; i < m_tableSize; i++ )
{
for( JHashtableEntry* e = tab[i]; e != NULL; e = e->next )
{
if ( e->value == value )
return true;
}
}
return false;
}
template <class KeyType, class ObjType>
bool
JHashtable<KeyType,ObjType>::containsKey( const KeyType& key ) const
{
return FindEntryByKey( key ) == NULL;
}
template <class KeyType, class ObjType>
const ObjType&
JHashtable<KeyType,ObjType>::get( const KeyType& key )
{
JHashtableEntry* entry = FindEntryByKey( key );
if ( entry != NULL )
return entry->value;
return NULL_ITEM; //if not found
}
template <class KeyType, class ObjType>
void
JHashtable<KeyType,ObjType>::rehash()
{
UINT oldTableSize = m_tableSize;
JHashtableEntry** oldTable = m_table;
UINT newTableSize = nextPrime( 2 * oldTableSize );
JHashtableEntry** newTable = new JHashtableEntry*[newTableSize];
memset( newTable, 0, sizeof(JHashtableEntry*) * newTableSize );
m_threshold = (UINT)(newTableSize * m_loadFactor);
m_table = newTable;
//copy all the entries from the old to the new table
for( i = 0; i < oldTableSize; i++ )
{
for( JHashtableEntry* old = oldTable[i]; old != NULL; )
{
JHashtableEntry* e = old;
old = old->next;
UINT index = e->hash % newTableSize;
e->next = newTable[index];
newTable[index] = e;
}
}
m_tableSize = newTableSize;
delete [] oldTable;
}
template <class KeyType, class ObjType>
ObjType
JHashtable<KeyType,ObjType>::put( const KeyType& key, const ObjType& value )
{
//Makes sure the key is not already in the hashtable
//replace item if found
JHashtableEntry* e = FindEntryByKey( key );
if ( e != NULL )
{
ObjType old = e->value;
e->value = value;
return old;
}
//Rehash the table if the threshold is exceeded
if ( m_count >= m_threshold )
{
rehash();
return put( key, value );
}
//Creates the new entry here
e = new JHashtableEntry();
e->hash = hash;
e->key = key;
e->value = value;
JHashtableEntry* row = GetHashRow( key );
e->next = row;
*row = e;
m_count++;
return NULL_ITEM;
}
template <class KeyType, class ObjType>
ObjType
JHashtable<KeyType,ObjType>::remove( const KeyType& key )
{
JHashtableEntry* hashRow = GetHashRow( key );
for( JHashtableEntry* e = hashRow, *prev = NULL; e != NULL; prev = e, e = e->next)
{
if ( e->hash == hash && e->key == key )
{
if ( prev != NULL )
prev->next = e->next;
else
tab[index] = tab[index]->next;
ObjType theReturn = e->value;
delete e;
m_count--; //decrement counter
return theReturn;
}
}
return NULL_ITEM;
}
template <class KeyType, class ObjType>
void
JHashtable<KeyType,ObjType>::clear()
{
JHashtableEntry** tab = m_table;
for(UINT i = 0; i < m_tableSize; i++ )
{
JHashtableEntry* e = tab[i];
while( e != NULL )
{
JHashtableEntry* tmp = e;
e = e->next;
delete tmp;
}
tab[i] = NULL;
}
//reset the counter
m_count = 0;
}
template <class KeyType, class ObjType>
UINT
JHashtable<KeyType,ObjType>::nextPrime( UINT start )
{
if( start % 2 == 0 )
start++;
UINT i;
for( ; ; start += 2 )
{
for( i = 3; i * i <= start; i += 2 )
if( start % i == 0 )
break;
if( i * i > start )
return start;
}
}
template <class KeyType, class ObjType>
typename JHashtable<KeyType,ObjType>::JHashtableEntry*
JHashtable<KeyType,ObjType>::FindEntryByKey( const KeyType& key )
{
JHashtable<KeyType,ObjType>::JHashtableEntry* hashRow = GetHashRow( key );
for( JHashtableEntry* e = hashRow; e != NULL; e = e->next )
{
if ( e->hash == hash && e->key == key )
return e->value;
}
return NULL;
}
template <class KeyType, class ObjType>
typename JHashtable<KeyType,ObjType>::JHashtableEntry*
JHashtable<KeyType,ObjType>::GetHashRow( const KeyType& key )
{
JHashtable<KeyType,ObjType>::JHashtableEntry** tab = m_table;
UINT hash = (*UserHash)(key);
UINT index = hash % m_tableSize;
return tab[index];
}
|
|
|