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

Public Member Functions
	Dictionary ()

void	Add (Collider c)

void	Add (const std::string phrase)

void	Report () const

void	ReportExpectedCollisions () const

void	Time ()

void	TimeOne (const int hindex)

Private Attributes
std::vector< Collider >	m_hashes

unsigned long	m_nphrases

std::vector< std::string >	m_words

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*}$