Word list and hashers to test. More...

Collaboration diagram for ns3::Hash::Example::Dictionary:

Public Member Functions
	Dictionary ()
	Constructor. More...

void	Add (Collider c)
	Add a Collider containing a hash function. More...

void	Add (const std::string phrase)
	Add a string to the dictionary. More...

void	Report () const
	Print the collisions for each Collider. More...

void	ReportExpectedCollisions () const
	Report the expected number of collisions. More...

void	Time ()
	Report the execution time of each hash across the entire Dictionary. More...

void	TimeOne (const int hindex)
	Time and report the execution of one hash across the entire Dictionary. More...

Private Attributes
std::vector< Collider >	m_hashes
	List of hash Colliders. More...

unsigned long	m_nphrases
	Number of strings hashed. More...

std::vector< std::string >	m_words
	List of unique words. More...

Detailed Description

Word list and hashers to test.

Definition at line 194 of file hash-example.cc.

Constructor & Destructor Documentation

ns3::Hash::Example::Dictionary::Dictionary ( )

inline

Constructor.

Definition at line 197 of file hash-example.cc.

References m_words.

Member Function Documentation

void ns3::Hash::Example::Dictionary::Add ( Collider c )

inline

Add a Collider containing a hash function.

Definition at line 204 of file hash-example.cc.

References m_hashes.

Referenced by main(), and ns3::Hash::Example::DictFiles::ReadInto().

Here is the caller graph for this function:

void ns3::Hash::Example::Dictionary::Add ( const std::string phrase )

inline

Add a string to the dictionary.

Parameters

[in] phrase the string to add

Definition at line 214 of file hash-example.cc.

References m_hashes, m_nphrases, and m_words.

void ns3::Hash::Example::Dictionary::Report ( ) const

inline

Print the collisions for each Collider.

Definition at line 296 of file hash-example.cc.

References m_hashes, and ReportExpectedCollisions().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

void ns3::Hash::Example::Dictionary::ReportExpectedCollisions ( ) const

inline

Report the expected number of collisions.

See, e.g., http://www.math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf

$E(collisions) = n - k + k (1 - 1/k)^n$

where n is the number of entries in the table, and k is the number of buckets.

This form is numerically unstable for low collision rates. Expanding for large $ k $ we get

$\begin{eqnarray*} E(c) &=& \frac{1}{k} {n \choose 2} - \frac{1}{{{k^2}}} {n \choose 3} + \frac{1}{{{k^3}}} {n \choose 4} - \ldots \\ &=& \frac{1}{k} {n \choose 2} \left[ {1 - \frac{{n - 2}}{{3k}} + \frac{{\left( {n - 2} \right) \left( {n - 3} \right)}}{{12{k^2}}} - \ldots } \right] \\ &=& \frac{1}{k} {n \choose 2} \left\{ {1 - \frac{{n - 2}}{{3k}} \left[ {1 + \frac{{n - 3}}{{4k}} - \ldots } \right]} \right\} \end{eqnarray*}$