A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
ns3::Hash::Example::Dictionary Class Reference

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< Colliderm_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]phrasethe 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*}

For simplicity, we'll use the first two terms of the second form.

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

References m_nphrases.

Referenced by Report().

+ Here is the caller graph for this function:

void ns3::Hash::Example::Dictionary::Time ( )
inline

Report the execution time of each hash across the entire Dictionary.

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

References m_hashes, and TimeOne().

Referenced by main().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::Hash::Example::Dictionary::TimeOne ( const int  hindex)
inline

Time and report the execution of one hash across the entire Dictionary.

Parameters
[in]hindexindex of the hash Collider to use

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

References ns3::Hasher::clear(), ns3::Hasher::GetHash32(), m_hashes, m_nphrases, m_words, visualizer.core::start(), and visualizer.higcontainer::w.

Referenced by Time().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

std::vector<Collider> ns3::Hash::Example::Dictionary::m_hashes
private

List of hash Colliders.

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

Referenced by Add(), Report(), Time(), and TimeOne().

unsigned long ns3::Hash::Example::Dictionary::m_nphrases
private

Number of strings hashed.

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

Referenced by Add(), ReportExpectedCollisions(), and TimeOne().

std::vector<std::string> ns3::Hash::Example::Dictionary::m_words
private

List of unique words.

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

Referenced by Add(), Dictionary(), and TimeOne().


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