A Discrete-Event Network Simulator
API
Public Member Functions | Private Attributes | List of all members
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 Collider &collider)
 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 269 of file hash-example.cc.

Constructor & Destructor Documentation

◆ Dictionary()

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

Constructor.

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

References m_words.

Member Function Documentation

◆ Add() [1/2]

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

Add a Collider containing a hash function.

Parameters
[in]cThe Collider to add.

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

References m_hashes.

Referenced by ns3::Hash::Example::DictFiles::ReadInto().

+ Here is the caller graph for this function:

◆ Add() [2/2]

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 294 of file hash-example.cc.

References m_hashes, m_nphrases, and m_words.

◆ Report()

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

Print the collisions for each Collider.

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

References m_hashes, and ReportExpectedCollisions().

+ Here is the call graph for this function:

◆ ReportExpectedCollisions()

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} \binom{n}{2} - \frac{1}{{{k^2}}} \binom{n}{3} + \frac{1}{{{k^3}}} \binom{n}{4} - \ldots \\ &=& \frac{1}{k} \binom{n}{2} \left[ {1 - \frac{{n - 2}}{{3k}} + \frac{{\left( {n - 2} \right) \left( {n - 3} \right)}}{{12{k^2}}} - \ldots } \right] \\ &=& \frac{1}{k} \binom{n}{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 351 of file hash-example.cc.

References m_nphrases.

Referenced by Report().

+ Here is the caller graph for this function:

◆ Time()

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

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

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

References m_hashes, and TimeOne().

+ Here is the call graph for this function:

◆ TimeOne()

void ns3::Hash::Example::Dictionary::TimeOne ( const Collider &  collider)
inline

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

Parameters
[in]colliderThe hash Collider to use.

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

References ns3::Hasher::clear(), ns3::Hasher::GetHash32(), ns3::Hash::Example::Collider::GetName(), ns3::Hash::Example::Collider::m_hash, m_nphrases, m_words, and visualizer.core::start().

Referenced by Time().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

Member Data Documentation

◆ m_hashes

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

List of hash Colliders.

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

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

◆ m_nphrases

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

Number of strings hashed.

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

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

◆ m_words

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

List of unique words.

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

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

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