libUTL++
utl::Hashtable Class Reference

Chained hashing collection. More...

#include <Hashtable.h>

Inheritance diagram for utl::Hashtable:

Public Member Functions

 Hashtable (size_t size, uint_t maxLF=90, bool owner=true, bool multiSet=false, const HashFunction *hfunc=nullptr)
 Constructor. More...
 
 Hashtable (bool owner, bool multiSet=false, const HashFunction *hfunc=nullptr)
 Constructor. More...
 
virtual void steal (Object &rhs)
 "Steal" the internal representation from another instance. More...
 
virtual void vclone (const Object &rhs)
 Make an exact copy of another instance. More...
 
virtual size_t innerAllocatedSize () const
 Get the "inner" allocated size. More...
 
Misc. Modification
void setHashFunction (const HashFunction *hashfn)
 Set the hash function. More...
 
void reserve (size_t newSize)
 Grow the hash-table to a size large enough to contain the given number of objects. More...
 
Searching
virtual Objectfind (const Object &key) const
 Find an object matching a given key. More...
 
iterator findIt (const Object &key) const
 
iterator findIt (const Object &key)
 
void findIt (const Object &key, BidIt &it) const
 
virtual void findIt (const Object &key, BidIt &it)
 Find an object matching a given key. More...
 
Adding Objects
bool add (const Object &object)
 
virtual bool add (const Object *object)
 Add an object to the collection. More...
 
void add (const Collection &collection)
 
ObjectaddOrFind (const Object &object)
 
virtual ObjectaddOrFind (const Object *object)
 Add the given object, or find a matching object already contained. More...
 
bool addOrUpdate (const Object &object)
 
virtual bool addOrUpdate (const Object *object)
 Add or update the given object. More...
 
Removing Objects
virtual void clear ()
 Clear the collection by removing all objects. More...
 
void excise ()
 Same as clear(), but in addition the pointer array is deleted. More...
 
bool remove (const Object *key)
 
virtual bool remove (const Object &key)
 Remove the object matching the given key. More...
 
virtual void removeIt (BidIt &it)
 Remove the object the given iterator points to. More...
 
Iterators
iterator begin () const
 
iterator begin ()
 
virtual BidItbeginNew () const
 Return a const iterator pointing to the beginning of the collection. More...
 
virtual BidItbeginNew ()
 Return an iterator pointing to the beginning of the collection. More...
 
iterator end () const
 
iterator end ()
 
virtual BidItendNew () const
 Return a const iterator pointing to the end of the collection. More...
 
virtual BidItendNew ()
 Return an iterator pointing to the end of the collection. More...
 
- Public Member Functions inherited from utl::Collection
void assertOwner ()
 Assert ownership of contained objects. More...
 
virtual void copy (const Object &rhs)
 Copy another instance. More...
 
virtual void dump (Stream &os, uint_t level=uint_t_max) const
 Dump a human-readable representation of self to the given output stream. More...
 
virtual void serialize (Stream &stream, uint_t io, uint_t mode=ser_default)
 Serialize to or from a stream. More...
 
void serialize (const RunTimeClass *rtc, Stream &stream, uint_t io, uint_t mode=ser_default)
 Serialize to/from the given stream. More...
 
virtual bool update (const Object *object)
 Update the given object. More...
 
bool isOwner () const
 Get the owner flag. More...
 
void setOwner (bool owner)
 Set the owner flag. More...
 
const Orderingordering () const
 Get the ordering. More...
 
Orderingordering ()
 Get the ordering. More...
 
void setOrdering (const Ordering &ordering, uint_t algorithm=sort_quickSort)
 Set the ordering, and optionally sort the collection to reflect the new ordering. More...
 
virtual void setOrdering (Ordering *ordering, uint_t algorithm=sort_quickSort)
 Set the ordering, and optionally sort the collection to reflect the new ordering. More...
 
bool empty () const
 Determine whether the collection is empty. More...
 
bool isMultiSet () const
 Get the multiSet flag. More...
 
void setMultiSet (bool multiSet)
 Set the multiSet flag. More...
 
bool isMarked () const
 Get marked flag. More...
 
void setMarked (bool marked=true)
 Set marked flag. More...
 
size_t items () const
 Get the number of contained objects. More...
 
size_t size () const
 Get the number of contained objects. More...
 
bool add (const Object &object)
 Add an object to the collection. More...
 
void add (const Collection &collection)
 Add another collection's objects. More...
 
virtual BidItaddIt (const Object *object)
 Add an object to the collection. More...
 
ObjectaddOrFind (const Object &object)
 Add the given object, or find a matching object already contained. More...
 
bool addOrUpdate (const Object &object)
 Add or update the given object. More...
 
CollectioncopyItems (const Collection *src, const Predicate *pred=nullptr, bool predVal=true)
 Copy objects from another collection. More...
 
CollectioncopyItems (const ListNode *src, const Predicate *pred=nullptr, bool predVal=true)
 Copy objects from a double-linked list. More...
 
CollectioncopyItems (const SlistNode *src, const Predicate *pred=nullptr, bool predVal=true)
 Copy objects from a single-linked list. More...
 
CollectionstealItems (Collection *src)
 "Steal" items from another collection. More...
 
Collectionoperator+= (const Object &rhs)
 Add an object to the collection. More...
 
Collectionoperator+= (const Object *rhs)
 Add an object to the collection. More...
 
Collectionoperator+= (const Collection &rhs)
 Add another collection's objects. More...
 
Collectionoperator-= (const Object &rhs)
 Remove an object from the collection. More...
 
void dump (Stream &os, uint_t level, bool key, bool printClassName, uint_t indent, const char *separator) const
 Dump contained objects to a stream. More...
 
virtual String toString () const
 Obtain a string representation by invoking Object::toString() on all contained objects.
 
String toString (bool key) const
 Obtain a string representation by invoking Object::toString() on all contained objects (or their keys). More...
 
String toString (const char *sep, bool key=false) const
 Obtain a string represenation by invoking Object::toString() on all contained objects (or their keys). More...
 
String toString (const String &sep, bool key=false) const
 Obtain a string represenation of the collection by invoking Object::toString() on all contained objects (or their keys). More...
 
iterator begin () const
 Return a const iterator pointing to the first object in the collection. More...
 
iterator begin ()
 Return an iterator pointing to the first object in the collection. More...
 
virtual BidItcreateIt () const
 Create a const iterator. More...
 
virtual BidItcreateIt ()
 Create an iterator. More...
 
iterator end () const
 Return a const iterator pointing to the end of the collection. More...
 
iterator end ()
 Return an iterator pointing to the end of the collection. More...
 
bool contains (const Object *key) const
 Determine whether the collection contains an object matching the given key. More...
 
bool contains (const Object &key) const
 Determine whether the collection contains an object matching the given key. More...
 
size_t count (const Predicate *pred=nullptr, bool predVal=true) const
 Count contained objects. More...
 
Objectfind (const Object *key) const
 Find an object matching a given key. More...
 
void findIt (const Object &key, BidIt &it) const
 Find an object matching a given key. More...
 
Objectfirst () const
 Return the first object (nullptr if empty). More...
 
bool has (const Object *key) const
 See contains(). More...
 
bool has (const Object &key) const
 See contains(). More...
 
Objectlast () const
 Get the last object (nullptr if empty). More...
 
bool remove (const Object *key)
 Remove the object matching the given key. More...
 
Objecttake (BidIt &it)
 Remove the object the given iterator points to, but do not delete the object even if the collection owns its objects. More...
 
Objectoperator[] (const Object *object)
 add-or-find access operator (returns Object*). More...
 
Objectoperator() (const Object *object)
 add-or-find access operator (returns Object&). More...
 
- Public Member Functions inherited from utl::Object
void clear ()
 Revert to initial state. More...
 
virtual int compare (const Object &rhs) const
 Compare with another object. More...
 
void dumpWithClassName (Stream &os, uint_t indent=4, uint_t level=uint_t_max) const
 Front-end for dump() that prints the object's class name. More...
 
virtual const ObjectgetKey () const
 Get the key for this object. More...
 
bool hasKey () const
 Determine whether or not the object has a key. More...
 
virtual const ObjectgetProxiedObject () const
 Get the proxied object (= self if none). More...
 
virtual ObjectgetProxiedObject ()
 Get the proxied object (= self if none). More...
 
virtual size_t hash (size_t size) const
 Get the hash code for the object. More...
 
bool _isA (const RunTimeClass *runTimeClass) const
 Determine whether self's class is a descendent of the given class. More...
 
 operator String () const
 Conversion to String. More...
 
size_t allocatedSize () const
 Get the total allocated size of this object. More...
 
virtual void addOwnedIt (const class FwdIt *it) const
 Notify self that it owns the given iterator. More...
 
virtual void removeOwnedIt (const class FwdIt *it) const
 Notify self that the given owned iterator has been destroyed. More...
 
bool operator< (const Object &rhs) const
 Less-than operator. More...
 
bool operator<= (const Object &rhs) const
 Less-than-or-equal-to operator. More...
 
bool operator> (const Object &rhs) const
 Greater-than operator. More...
 
bool operator>= (const Object &rhs) const
 Greater-than-or-equal-to operator. More...
 
bool operator== (const Object &rhs) const
 Equal-to operator. More...
 
bool operator!= (const Object &rhs) const
 Unequal-to operator. More...
 
void serializeIn (Stream &is, uint_t mode=ser_default)
 Serialize from an input stream. More...
 
void serializeOut (Stream &os, uint_t mode=ser_default) const
 Serialize to an output stream. More...
 
void serializeOutBoxed (Stream &os, uint_t mode=ser_default) const
 Serialize a boxed object to an output stream. More...
 

Additional Inherited Members

- Static Public Member Functions inherited from utl::Object
static ObjectserializeInNullable (Stream &is, uint_t mode=ser_default)
 Serialize a nullptr-able object from an input stream. More...
 
static void serializeOutNullable (const Object *object, Stream &os, uint_t mode=ser_default)
 Serialize a nullptr-able object to an output stream. More...
 
static void serializeNullable (Object *&object, Stream &stream, uint_t io, uint_t mode=ser_default)
 Serialize a nullptr-able object to or from a stream. More...
 
static ObjectserializeInBoxed (Stream &is, uint_t mode=ser_default)
 Serialize a boxed object from an input stream. More...
 
static void serializeBoxed (Object *&object, Stream &stream, uint_t io, uint_t mode=ser_default)
 Serialize a boxed object to or from a stream. More...
 
- Protected Member Functions inherited from utl::FlagsMI
 FlagsMI ()
 Constructor. More...
 
virtual ~FlagsMI ()
 Destructor. More...
 
void copyFlags (const FlagsMI &rhs)
 Copy the given flags. More...
 
void copyFlags (const FlagsMI &rhs, uint_t lsb, uint_t msb)
 Copy (some of) the given flags. More...
 
void copyFlags (uint64_t flags, uint_t lsb, uint_t msb)
 Copy (some of) the given flags. More...
 
bool getFlag (uint_t flagNum) const
 Get a user-defined flag. More...
 
void setFlag (uint_t flagNum, bool val)
 Set a user-defined flag. More...
 
uint64_t getFlagsNumber (uint64_t mask, uint64_t shift=0)
 Get a multi-bit value in the flags data (which is stored as one 64-bit integer). More...
 
void setFlagsNumber (uint64_t mask, uint64_t shift, uint64_t num)
 Set a multi-bit value in the flags data (which is stored as one 64-bit integer). More...
 
uint64_t getFlags () const
 Get the flags. More...
 
void setFlags (uint64_t flags)
 Set the flags. More...
 

Detailed Description

Chained hashing collection.

Hashtable doesn't inherit from SortedCollection because objects in a hashtable aren't organized based on any ordering of search keys. The hash function is supposed to bring us straight to the object we're looking for, or at least to a very small group of objects that have the same hash. If utl::Collection::isMultiSet() is false, then add(const utl::Object*) won't permit you to add two objects that compare as equal, or whose keys compare as equal (if they have keys - see utl::Object::getKey()). Comparison of objects is also done by utl::Hashtable::find().

When multiple objects hash to the same location, they are put into a linked list (but only then).

You can either provide a hash function (in the constructor or by calling setHashFunction()), or you can ensure Object::hash() is defined for the contained objects or their keys (see Object::getKey()).

Advantages

  • add(const utl::Object*), find(), remove() are practically O(1) if:
  • – the hash function gives a fairly uniform distribution
  • – the hash table isn't allowed to grow too full
  • performance degrades in near-linear fashion as load factor is increased
  • low memory usage (probably ~1.4 pointers per contained object on average)

Disadvantages

  • contained objects are not sorted
Author
Adam McKee

Definition at line 92 of file Hashtable.h.

Constructor & Destructor Documentation

◆ Hashtable() [1/2]

utl::Hashtable::Hashtable ( size_t  size,
uint_t  maxLF = 90,
bool  owner = true,
bool  multiSet = false,
const HashFunction hfunc = nullptr 
)
inline

Constructor.

Parameters
sizeinitial size of hash-table
maxLF(optional : 90) maximum load factor
owner(optional : true) owner flag
multiSet(optional : false) multiSet flag
hfunc(optional) hash function

Definition at line 109 of file Hashtable.h.

References utl::init().

◆ Hashtable() [2/2]

utl::Hashtable::Hashtable ( bool  owner,
bool  multiSet = false,
const HashFunction hfunc = nullptr 
)
inline

Constructor.

Parameters
ownerowner flag
multiSetmultiSet flag
hfunc(optional) hash function

Definition at line 124 of file Hashtable.h.

References utl::init().

Member Function Documentation

◆ steal()

virtual void utl::Hashtable::steal ( Object rhs)
virtual

"Steal" the internal representation from another instance.

The default implementation just calls vclone(), so you have to override this if you want a "move" capability.

Reimplemented from utl::Collection.

◆ vclone()

virtual void utl::Hashtable::vclone ( const Object rhs)
virtual

Make an exact copy of another instance.

The default implementation just calls copy(), so you have to override this if you want different behavior for copy construction and cloning.

Reimplemented from utl::Collection.

◆ innerAllocatedSize()

virtual size_t utl::Hashtable::innerAllocatedSize ( ) const
virtual

Get the "inner" allocated size.

Reimplemented from utl::Collection.

◆ setHashFunction()

void utl::Hashtable::setHashFunction ( const HashFunction hashfn)
inline

Set the hash function.

Definition at line 139 of file Hashtable.h.

References ASSERTD, const_cast_this, utl::deInit(), IFDEBUG, utl::init(), utl::ListNode::set(), and utl::FwdIt::setConst().

◆ reserve()

void utl::Hashtable::reserve ( size_t  newSize)

Grow the hash-table to a size large enough to contain the given number of objects.

◆ find()

virtual Object* utl::Hashtable::find ( const Object key) const
virtual

Find an object matching a given key.

Returns
found object (nullptr if none)
Parameters
keysearch key

Reimplemented from utl::Collection.

◆ findIt()

virtual void utl::Hashtable::findIt ( const Object key,
BidIt it 
)
virtual

Find an object matching a given key.

Parameters
keysearch key
itresult iterator (= end() if no object found)

Reimplemented from utl::Collection.

◆ add()

virtual bool utl::Hashtable::add ( const Object object)
virtual

Add an object to the collection.

Returns
true if successful, false otherwise
Parameters
objectobject to add

Implements utl::Collection.

◆ addOrFind()

virtual Object* utl::Hashtable::addOrFind ( const Object object)
virtual

Add the given object, or find a matching object already contained.

Returns
found object (or provided object, if it was added)

Reimplemented from utl::Collection.

◆ addOrUpdate()

virtual bool utl::Hashtable::addOrUpdate ( const Object object)
virtual

Add or update the given object.

If the object already exists, it will be updated, otherwise it will be added.

Returns
true if object was replaced, false if it was newly added
Parameters
objectobject to add or update

Reimplemented from utl::Collection.

◆ clear()

virtual void utl::Hashtable::clear ( )
virtual

Clear the collection by removing all objects.

Implements utl::Collection.

◆ excise()

void utl::Hashtable::excise ( )

Same as clear(), but in addition the pointer array is deleted.

Call this method instead of clear() when you want to minimize memory usage as much as possible.

◆ remove()

virtual bool utl::Hashtable::remove ( const Object key)
virtual

Remove the object matching the given key.

Returns
true if object found and removed, false otherwise
Parameters
keysearch key

Reimplemented from utl::Collection.

◆ removeIt()

virtual void utl::Hashtable::removeIt ( BidIt it)
virtual

Remove the object the given iterator points to.

The iterator will be updated so that it points to the removed object's successor.

Parameters
ititerator specifying object to be removed

Reimplemented from utl::Collection.

◆ beginNew() [1/2]

virtual BidIt* utl::Hashtable::beginNew ( ) const
virtual

Return a const iterator pointing to the beginning of the collection.

Implements utl::Collection.

◆ beginNew() [2/2]

virtual BidIt* utl::Hashtable::beginNew ( )
virtual

Return an iterator pointing to the beginning of the collection.

Implements utl::Collection.

◆ endNew() [1/2]

virtual BidIt* utl::Hashtable::endNew ( ) const
virtual

Return a const iterator pointing to the end of the collection.

Implements utl::Collection.

◆ endNew() [2/2]

virtual BidIt* utl::Hashtable::endNew ( )
virtual

Return an iterator pointing to the end of the collection.

Implements utl::Collection.


The documentation for this class was generated from the following files: