library: libCore #include "THashTable.h"

# THashTable

class description - source file - inheritance tree (.pdf)

## class THashTable : public TCollection

| Inheritance Chart:
`TObject`
| <- | `TCollection`
| <- | `THashTable` |

        private:

          Int_t GetHashValue(const TObject* obj) const
          Int_t GetHashValue(TString& s) const
          Int_t GetHashValue(const char* str) const

        public:

                             THashTable(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0)
                     virtual ~THashTable()
                virtual void Add(TObject* obj)
                virtual void AddAll(const TCollection* col)
                     Float_t AverageCollisions() const
              static TClass* Class()
                virtual void Clear(Option_t* option = "")
                       Int_t Collisions(const char* name) const
                       Int_t Collisions(TObject* obj) const
                virtual void Delete(Option_t* option = "")
            virtual TObject* FindObject(const char* name) const
            virtual TObject* FindObject(const TObject* obj) const
                      TList* GetListForObject(const char* name) const
                      TList* GetListForObject(const TObject* obj) const
           virtual TObject** GetObjectRef(const TObject* obj) const
                       Int_t GetRehashLevel() const
               virtual Int_t GetSize() const
             virtual TClass* IsA() const
          virtual TIterator* MakeIterator(Bool_t dir = kIterForward) const
                        void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE)
            virtual TObject* Remove(TObject* obj)
                    TObject* RemoveSlow(TObject* obj)
                        void SetRehashLevel(Int_t rehash)
                virtual void ShowMembers(TMemberInspector& insp, char* parent)
                virtual void Streamer(TBuffer& b)
                        void StreamerNVirtual(TBuffer& b)

### Data Members

        private:

          TList** fCont         Hash table (table of lists)
            Int_t fEntries      Number of objects in table
            Int_t fUsedSlots    Number of used slots
            Int_t fRehashLevel  Average collision rate which triggers rehash

## Class Description

     THashTable

     THashTable implements a hash table to store TObject's. The hash
     value is calculated using the value returned by the TObject's
     Hash() function. Each class inheriting from TObject can override
     Hash() as it sees fit.
     THashTable does not preserve the insertion order of the objects.
     If the insertion order is important AND fast retrieval is needed
     use THashList instead.

/* */

THashTable(Int_t capacity, Int_t rehashlevel)

     Create a THashTable object. Capacity is the initial hashtable capacity
     (i.e. number of slots), by default kInitHashTableCapacity = 17, and
     rehashlevel is the value at which a rehash will be triggered. I.e. when
     the average size of the linked lists at a slot becomes longer than
     rehashlevel then the hashtable will be resized and refilled to reduce
     the collision rate to about 1. The higher the collision rate, i.e. the
     longer the linked lists, the longer lookup will take. If rehashlevel=0
     the table will NOT automatically be rehashed. Use Rehash() for manual
     rehashing.

~THashTable()

     Delete a hashtable. Objects are not deleted unless the THashTable is the
     owner (set via SetOwner()).

void Add(TObject *obj)

     Add object to the hash table. Its position in the table will be
     determined by the value returned by its Hash() function.

void AddAll(const TCollection *col)

     Add all objects from collection col to this collection.
     Implemented for more efficient rehashing.

void Clear(Option_t *option)

     Remove all objects from the table. Does not delete the objects
     unless the THashTable is the owner (set via SetOwner()).

Int_t Collisions(const char *name) const

     Returns the number of collisions for an object with a certain name
     (i.e. number of objects in same slot in the hash table, i.e. length
     of linked list).

Int_t Collisions(TObject *obj) const

     Returns the number of collisions for an object (i.e. number of objects
     in same slot in the hash table, i.e. length of linked list).

void Delete(Option_t *)

     Remove all objects from the table AND delete all heap based objects.

TObject* FindObject(const char *name) const

     Find object using its name. Uses the hash value returned by the
     TString::Hash() after converting name to a TString.

TObject* FindObject(const TObject *obj) const

     Find object using its hash value (returned by its Hash() member).

TList* GetListForObject(const char *name) const

     Return the TList corresponding to object's name based hash value.
     One can iterate this list "manually" to find, e.g. objects with
     the same name.

TList* GetListForObject(const TObject *obj) const

     Return the TList corresponding to object's hash value.
     One can iterate this list "manually" to find, e.g. identical
     objects.

TObject** GetObjectRef(const TObject *obj) const

     Return address of pointer to obj

TIterator* MakeIterator(Bool_t dir) const

     Returns a hash table iterator.

void Rehash(Int_t newCapacity, Bool_t checkObjValidity)

     Rehash the hashtable. If the collision rate becomes too high (i.e.
     the average size of the linked lists become too long) then lookup
     efficiency decreases since relatively long lists have to be searched
     every time. To improve performance rehash the hashtable. This resizes
     the table to newCapacity slots and refills the table. Use
     AverageCollisions() to check if you need to rehash. Set checkObjValidity
     to kFALSE if you know that all objects in the table are still valid
     (i.e. have not been deleted from the system in the meanwhile).

TObject* Remove(TObject *obj)

     Remove object from the hashtable.

TObject* RemoveSlow(TObject *obj)

     Remove object from the hashtable without using the hash value.

### Inline Functions

                  Int_t GetHashValue(const TObject* obj) const
                  Int_t GetHashValue(TString& s) const
                  Int_t GetHashValue(const char* str) const
                Float_t AverageCollisions() const
                  Int_t GetRehashLevel() const
                  Int_t GetSize() const
                   void SetRehashLevel(Int_t rehash)
                TClass* Class()
                TClass* IsA() const
                   void ShowMembers(TMemberInspector& insp, char* parent)
                   void Streamer(TBuffer& b)
                   void StreamerNVirtual(TBuffer& b)

Author: Fons Rademakers 27/09/95
Last update: root/cont:$Name: $:$Id: THashTable.cxx,v 1.10 2005/03/24 07:13:35 brun Exp $
Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *