Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

PLearn::Hash< KeyType, DataType > Class Template Reference

#include <Hash.h>

Inheritance diagram for PLearn::Hash< KeyType, DataType >:

Inheritance graph
[legend]
Collaboration diagram for PLearn::Hash< KeyType, DataType >:

Collaboration graph
[legend]
List of all members.

Public Member Functions

bool add (const KeyType &, const DataType &)
 returns false if table is full

void addAndResize (const KeyType &, const DataType &)
 add() and resize() if resizeTime()

bool element (const KeyType &)
bool del (const KeyType &)
unsigned int hashAddress (const KeyType &)
 returns Hash_UNUSED_TAG (-1) if not in table

DataType * operator[] (unsigned int addr) const
 !<

KeyType * operator() (unsigned int addr) const
 !<

HashKeyDataPair< KeyType,
DataType > ** 		getTable () const
unsigned int size () const
 !<

unsigned int cardinal () const
 !<

void flush ()
 cleans the table without resizing it

void initializeTable (unsigned int size)
 !<

bool full () const
 is the table full?

bool resizeTime () const
 is it time to resize the table?

void resize (int newsize=-1)
 resizes the table to maintain a good sparseness (default=-1 quadruples the table size)

void cleanup ()
 cleanup the table to maintain efficiency

unsigned int probes () const
 returns the number of probe generate by last query

void diagnostics (unsigned int &clusters, unsigned int &maxCluster) const
 Hash (unsigned int size=10000, bool static_allocation=false)
 !<

 ~Hash ()

Public Attributes

bool isStatic
 static or dynamic memory allocation


Private Member Functions

unsigned int hashKey (const KeyType &) const
 computes the primary hash function on the string (length=0 says to look for in bytes to determine length)

void computePace ()
 computes the magic number used by the secondary hash function

unsigned int pgcd (unsigned int, unsigned int) const
unsigned int find (const KeyType &)
 returns either an empty slot or the slot with the key in it

unsigned int findGap (const KeyType &)
 returns the first empty slot it finds

 Hash (const Hash &obj)
 The copy constructor is not yet defined...

void operator= (const Hash &obj)
 not permitted...


Private Attributes

HashKeyDataPair< KeyType,
DataType > ** 		table
 a pointer to a table of <key,data>

unsigned int tableSize
 total number of slots

unsigned int elements
 number of used slots

unsigned int pace
 used by the secondary hash function

unsigned int jumps
 number of probes in last operation

bool static_tables_initialized
 true when the tables are initialized

KeyType * key_table
DataType * data_table
HashKeyDataPair< KeyType,
DataType > * 		hash_table
unsigned int next_free_slot
 the next free slot in the 3 tables

template<class KeyType, class DataType>
class PLearn::Hash< KeyType, DataType >

Constructor & Destructor Documentation

template<class KeyType, class DataType>
PLearn::Hash< KeyType, DataType >::Hash (  unsigned int  size = 10000,
bool  static_allocation = false
) 
 

!<

Creates the table with size entries

allocates a table of 0s

Definition at line 550 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::computePace(), and PLearn::Hash< KeyType, DataType >::table.

template<class KeyType, class DataType>
PLearn::Hash< KeyType, DataType >::~Hash (   ) 
 

Definition at line 567 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::data_table, PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash< KeyType, DataType >::hash_table, PLearn::Hash< KeyType, DataType >::isStatic, PLearn::Hash< KeyType, DataType >::key_table, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

template<class KeyType, class DataType>
PLearn::Hash< KeyType, DataType >::Hash (  const Hash< KeyType, DataType > &  obj  )  [inline, private]
 

The copy constructor is not yet defined...

Definition at line 147 of file Hash.h.

Member Function Documentation

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::add (  const KeyType &  key,
const DataType &  data
) 
 

returns false if table is full

Return False only if the table is full. Use resizeTime() to determine if the table should be resized

if already element delete it

< no slot found (bummer!)

< no slot found (bummer!)

Definition at line 286 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::data_table, PLearn::Hash< KeyType, DataType >::elements, PLearn::Hash< KeyType, DataType >::findGap(), PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::hash_table, PLearn::Hash< KeyType, DataType >::isStatic, PLearn::Hash< KeyType, DataType >::key_table, PLearn::Hash< KeyType, DataType >::next_free_slot, PLERROR, PLearn::Hash< KeyType, DataType >::static_tables_initialized, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::SimpleDB< KeyType, QueryResult >::indexColumn(), and PLearn::Hash< KeyType, DataType >::resize().

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::addAndResize (  const KeyType &  key,
const DataType &  data
) 
 

add() and resize() if resizeTime()

call add() and resize() if resizeTime()

Definition at line 325 of file Hash.h.

References PLearn::add(), resize(), and PLearn::Hash< KeyType, DataType >::resizeTime().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::cardinal (   )  const
 

!<

returns the number of used slots.

Definition at line 394 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::elements.

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::cleanup (   ) 
 

cleanup the table to maintain efficiency

Cleans the table after some "deletes"

< dont deallocate t's table

Definition at line 458 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::elements, PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::computePace (   )  [private]
 

computes the magic number used by the secondary hash function

The pace is the secondary hash function. rather than doing a straight forward linear probing, we do a pseudorandomized probing

Definition at line 222 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::pgcd(), and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::Hash< KeyType, DataType >::Hash().

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::del (  const KeyType &  key  ) 
 

deletes the entry, but leaves a marker so that probes continue to work properly

Definition at line 337 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::elements, PLearn::find(), PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::isStatic, and PLearn::Hash< KeyType, DataType >::table.

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::diagnostics (  unsigned int &  clusters,
unsigned int &  maxCluster
)  const
 

Parameters:
clusters  ...and average cluster size is cardinal()/clusters

Definition at line 607 of file Hash.h.

References __max, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::element (  const KeyType &  key  ) 
 

returns true if the string is in the table, false otherwise

Definition at line 358 of file Hash.h.

References PLearn::find(), PLearn::Hash_DELETED_SLOT, and PLearn::Hash< KeyType, DataType >::table.

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::find (  const KeyType &  key  )  [private]
 

returns either an empty slot or the slot with the key in it

find will stop either on an empty slot or on a slot that contains the searched string.

while ( (table[h]>Hash_DELETED_SLOT) && //!< FIX ABOVE PROBLEM

PROBLEME GRAVE ICI: si key->h mais h est occupe, donc key-> jump to h' ensuite si table[h] a ete delete un find(key) donnera h (qui contient "Hash_DELETED_SLOT") plutot que h'

Definition at line 236 of file Hash.h.

References PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::hashKey(), PLearn::Hash< KeyType, DataType >::jumps, PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::findGap (  const KeyType &  key  )  [private]
 

returns the first empty slot it finds

find will stop either on an empty slot or on a slot that contains the searched string.

Definition at line 264 of file Hash.h.

References PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::hashKey(), PLearn::Hash< KeyType, DataType >::jumps, PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::Hash< KeyType, DataType >::add().

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::flush (   ) 
 

cleans the table without resizing it

Erases all strings, but does not destroy the table itself

Definition at line 509 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::elements, PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::isStatic, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::SimpleDB< KeyType, QueryResult >::indexColumn(), PLearn::Hash< KeyType, DataType >::resize(), and PLearn::Hash< KeyType, DataType >::~Hash().

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::full (   )  const
 

is the table full?

Tells you if you should resize the table now.

Definition at line 417 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::elements, and PLearn::Hash< KeyType, DataType >::tableSize.

template<class KeyType, class DataType>
HashKeyDataPair<KeyType,DataType>** PLearn::Hash< KeyType, DataType >::getTable (   )  const [inline]
 

Definition at line 123 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::table.

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::hashAddress (  const KeyType &  key  ) 
 

returns Hash_UNUSED_TAG (-1) if not in table

Gives the address in the table of the string (possibly Hash_UNUSED_TAG if there is no such string in the table)

Definition at line 371 of file Hash.h.

References PLearn::find(), PLearn::Hash_DELETED_SLOT, PLearn::Hash_UNUSED_TAG, and PLearn::Hash< KeyType, DataType >::table.

Referenced by PLearn::SimpleDB< KeyType, QueryResult >::findEqualIndexed(), and PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::hashKey (  const KeyType &  key  )  const [private]
 

computes the primary hash function on the string (length=0 says to look for in bytes to determine length)

Computes the remainder (mod AMagicNumber) of the key

Definition at line 186 of file Hash.h.

References PLearn::Hash_NOMBRES_MAGIQUES, PLearn::Hash< KeyType, DataType >::hashKey(), and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::Hash< KeyType, DataType >::find(), PLearn::Hash< KeyType, DataType >::findGap(), and PLearn::Hash< KeyType, DataType >::hashKey().

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::initializeTable (  unsigned int  size  ) 
 

!<

Creates the static table with size entries

Definition at line 529 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::data_table, PLearn::Hash< KeyType, DataType >::hash_table, PLearn::Hash< KeyType, DataType >::isStatic, PLearn::Hash< KeyType, DataType >::key_table, PLERROR, PLWARNING, and PLearn::Hash< KeyType, DataType >::static_tables_initialized.

template<class KeyType, class DataType>
KeyType * PLearn::Hash< KeyType, DataType >::operator() (  unsigned int  addr  )  const
 

!<

Arguments to () is hashAddress

Definition at line 494 of file Hash.h.

References PLearn::Hash_DELETED_SLOT, and PLearn::Hash< KeyType, DataType >::table.

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::operator= (  const Hash< KeyType, DataType > &  obj  )  [inline, private]
 

not permitted...

Definition at line 148 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::operator=().

Referenced by PLearn::Hash< KeyType, DataType >::operator=().

template<class KeyType, class DataType>
DataType * PLearn::Hash< KeyType, DataType >::operator[] (  unsigned int  addr  )  const
 

!<

Arguments to [] is hashAddress

Definition at line 482 of file Hash.h.

References PLearn::Hash_DELETED_SLOT, and PLearn::Hash< KeyType, DataType >::table.

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::pgcd (  unsigned  int,
unsigned  int
)  const [private]
 

Definition at line 204 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::computePace().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::probes (   )  const
 

returns the number of probe generate by last query

Definition at line 595 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::jumps.

template<class KeyType, class DataType>
void PLearn::Hash< KeyType, DataType >::resize (  int  newsize = -1  ) 
 

resizes the table to maintain a good sparseness (default=-1 quadruples the table size)

Resizes the table by producing an enlarged copy (not in situ rehashing)

< dont deallocate t's table

Definition at line 429 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::elements, PLearn::endl(), PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash_DELETED_SLOT, PLearn::Hash< KeyType, DataType >::pace, PLearn::Hash< KeyType, DataType >::table, and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::SimpleDB< KeyType, QueryResult >::indexColumn().

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::resizeTime (   )  const
 

is it time to resize the table?

Tells you if you should resize the table now.

Definition at line 406 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::elements, and PLearn::Hash< KeyType, DataType >::tableSize.

Referenced by PLearn::Hash< KeyType, DataType >::addAndResize().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::size (   )  const
 

!<

returns the total number of slots

Definition at line 385 of file Hash.h.

References PLearn::Hash< KeyType, DataType >::tableSize.

Member Data Documentation

template<class KeyType, class DataType>
DataType* PLearn::Hash< KeyType, DataType >::data_table [private]
 

Definition at line 107 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::initializeTable(), and PLearn::Hash< KeyType, DataType >::~Hash().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::elements [private]
 

number of used slots

Definition at line 93 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::cardinal(), PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::Hash< KeyType, DataType >::del(), PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash< KeyType, DataType >::full(), PLearn::Hash< KeyType, DataType >::resize(), and PLearn::Hash< KeyType, DataType >::resizeTime().

template<class KeyType, class DataType>
HashKeyDataPair<KeyType,DataType>* PLearn::Hash< KeyType, DataType >::hash_table [private]
 

Definition at line 108 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::initializeTable(), and PLearn::Hash< KeyType, DataType >::~Hash().

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::isStatic
 

static or dynamic memory allocation

Definition at line 112 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::del(), PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash< KeyType, DataType >::initializeTable(), and PLearn::Hash< KeyType, DataType >::~Hash().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::jumps [private]
 

number of probes in last operation

Definition at line 95 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::find(), PLearn::Hash< KeyType, DataType >::findGap(), and PLearn::Hash< KeyType, DataType >::probes().

template<class KeyType, class DataType>
KeyType* PLearn::Hash< KeyType, DataType >::key_table [private]
 

Definition at line 106 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::initializeTable(), and PLearn::Hash< KeyType, DataType >::~Hash().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::next_free_slot [private]
 

the next free slot in the 3 tables

Definition at line 109 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::pace [private]
 

used by the secondary hash function

Definition at line 94 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::Hash< KeyType, DataType >::computePace(), PLearn::Hash< KeyType, DataType >::find(), PLearn::Hash< KeyType, DataType >::findGap(), and PLearn::Hash< KeyType, DataType >::resize().

template<class KeyType, class DataType>
bool PLearn::Hash< KeyType, DataType >::static_tables_initialized [private]
 

true when the tables are initialized

Definition at line 105 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), and PLearn::Hash< KeyType, DataType >::initializeTable().

template<class KeyType, class DataType>
HashKeyDataPair<KeyType,DataType>** PLearn::Hash< KeyType, DataType >::table [private]
 

a pointer to a table of <key,data>

Definition at line 91 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::Hash< KeyType, DataType >::del(), PLearn::Hash< KeyType, DataType >::diagnostics(), PLearn::Hash< KeyType, DataType >::element(), PLearn::Hash< KeyType, DataType >::find(), PLearn::Hash< KeyType, DataType >::findGap(), PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash< KeyType, DataType >::getTable(), PLearn::Hash< KeyType, DataType >::Hash(), PLearn::Hash< KeyType, DataType >::hashAddress(), PLearn::Hash< KeyType, DataType >::operator()(), PLearn::Hash< KeyType, DataType >::operator[](), PLearn::Hash< KeyType, DataType >::resize(), and PLearn::Hash< KeyType, DataType >::~Hash().

template<class KeyType, class DataType>
unsigned int PLearn::Hash< KeyType, DataType >::tableSize [private]
 

total number of slots

Definition at line 92 of file Hash.h.

Referenced by PLearn::Hash< KeyType, DataType >::add(), PLearn::Hash< KeyType, DataType >::cleanup(), PLearn::Hash< KeyType, DataType >::computePace(), PLearn::Hash< KeyType, DataType >::diagnostics(), PLearn::Hash< KeyType, DataType >::find(), PLearn::Hash< KeyType, DataType >::findGap(), PLearn::Hash< KeyType, DataType >::flush(), PLearn::Hash< KeyType, DataType >::full(), PLearn::Hash< KeyType, DataType >::hashKey(), PLearn::Hash< KeyType, DataType >::resize(), PLearn::Hash< KeyType, DataType >::resizeTime(), PLearn::Hash< KeyType, DataType >::size(), and PLearn::Hash< KeyType, DataType >::~Hash().

The documentation for this class was generated from the following file:
Generated on Tue Aug 17 16:23:50 2004 for PLearn by doxygen 1.3.7