HashVector Class Reference

#include <HashVector.h>

Inheritance diagram for HashVector:

List of all members.

Public Member Functions
	HashVector (int MvsS=MVS_NORMAL, int HashBits=10)
virtual	~HashVector ()
	Free all the data associated with this hash vector.
uint	Length ()
	Return the number of elements in this vector.
uint	Buckets ()
	Get number of buckets used.
virtual void	FreeItem (Some Item) const
	Virtual function which frees a vector element.
void	DeleteAll ()
	Delete all elements.
virtual HashKey_t	GetKey (Some Item) const
	Extract the sort key from a item.
virtual int	Compare (HashKey_t Key1, HashKey_t Key2) const
	Compare two array elements in given Mode.
void	Insert (Some Item)
	Insert element 'Item' into the hash vector.
void	Delete (Some Item)
	Delete element 'Item' from the hash vector.
Some	GetByKey (HashKey_t Key) const
	Find a hash vector element by search key; returns 0 if not found.
void	IncRef ()
	--- Expose the hidden Base interface ---///
Iterator	Begin () const
	Get an iterator pointing to the start of hash vector.
Iterator	End () const
	Get an iterator pointing to the end of hash vector.
Iterator	FindKey (HashKey_t Key) const
	Like GetByKey but return an iterator.
Public Attributes
HashResult_t(*	Hash )(HashKey_t Key)
	This is a pointer to the hash function.
Protected Member Functions
void	lhbDestroy (LargeHashBucket *lhb)
	Destroy the large hash bucket, and free all elements.
void	lhbInsertSorted (LargeHashBucket *lhb, Some Item)
	Insert a element into the large hash bucket so that bucket remains sorted.
int	lhbFind (LargeHashBucket *lhb, HashKey_t Key) const
	Find a element in a large hash bucket by key and return its index.
Some	lhbGetByKey (LargeHashBucket *lhb, HashKey_t Key) const
	Same but return the element itself.
	HashVector (HashVector *other)
	Copy this hash vector (without reallocating pointers!).
void	SetBuckets (int iBuckets)
void	_Insert (Some Item)
Static Protected Member Functions
static HashResult_t	DefaultHash (HashKey_t Key)
	Default hash function.
Protected Attributes
HashResult_t	HashMask
	The bitmask to AND with the hash result.
int	MemVsSpeed
	Memory-vs-speed coefficient.
Classes
class	Iterator
struct	LargeHashBucket

---

Detailed Description

A hash vector is somehow similar to Vector, but uses hash tables to store data, thus greatly decreasing search times. For big arrays (> 5000 elements) the search time is faster than with binary trees for the regular vector, although you should keep in mind that nothing comes for free: you get speed in exchange for memory usage. Usually a HashVector will take about 1.5-2x as much memory as a Vector of the same size would.

---

Constructor & Destructor Documentation

HashVector::HashVector	(	int	MvsS = MVS_NORMAL,
		int	HashBits = 10
	)

Initialize the hash vector so that it initially contains the requested number of buckets.

• MvsS Memory usage vs Speed. You can somewhat modify the behaviour of the hash vector by setting this to a value different that default. If it is MVS_FAST, the lookups will be faster but the vector will take more memory; if it is MVS_SMALL, the vector will take less memory but will be slightly slower (still much faster than regular Vector).
• HashBits This parameter defines how much bits to use from the hash function. Basically this defines how much buckets there are initially: 2^HashBits. The larger you expect the amount of items, the larger numbers you should use here. The default value is good for hash tables of around 4000 elements; the optimal value can be approximatively computed as log2(n/HASHVECT_BUCKET_SIZE), and it depends of the quality of the used hash function.

---

Member Function Documentation

void HashVector::_Insert

(

Some

Item

)

[protected]

Slightly faster Insert without sanity checks.

void HashVector::SetBuckets

(

int

iBuckets

)

[protected]

Resize the hash vector so that it uses so much buckets. The hash vector really adjusts its size automatically, so there's no need to call this function.

• iBuckets Number of buckets used. MUST BE A POWER OF TWO.

---

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

• My Documents/Visual Studio 2005/Projects/swgemu/src/shared/HashVector.h
• My Documents/Visual Studio 2005/Projects/swgemu/src/shared/HashVector.cpp

---