jluebbert (owner)

Revisions

gist: 214698 Download_button fork
public
Public Clone URL: git://gist.github.com/214698.git
Embed All Files: show embed
C++ #
raw 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
#include <string>
#include <sstream>
using namespace std;
 
#define DAYS_IN_YEAR 360	// In order to simplify the program
#define DAYS 30				// use 30 days in each month.
#define MONTHS 12			// This still gives a rough estimate on how
// well the hashing functions work.
 
int hash1(int month, int day);
int hash2(int month, int day);
string formatDate(int month, int day);
 
int main()
{
    // for hash1
    string year1[DAYS_IN_YEAR];
    // for hash2
    string year2[DAYS_IN_YEAR];
    int numOfDays = 0;
    int collisions1 = DAYS_IN_YEAR;
    int collisions2 = DAYS_IN_YEAR;
 
    // clear both arrays
    for ( int i = 0; i < DAYS_IN_YEAR; i++ )
        year1[i] = year2[i] = "";
 
    for ( int i = 1; i <= MONTHS; i++ ) {
        for ( int j = 1; j <= DAYS; j++ ) {
            year1[ hash1(i, j) ] = formatDate(i, j);
            year2[ hash2(i, j) ] = formatDate(i, j);
        }
    }
 
    // total collisions for hash1
    for ( int i = 0; i < DAYS_IN_YEAR; i++ ) {
        if ( year1[i] != "" )
            numOfDays += 1;
    }
    collisions1 -= numOfDays;
 
    numOfDays = 0;
 
    // total collisions for hash2
    for ( int i = 0; i < DAYS_IN_YEAR; i++ ) {
        if ( year2[i] != "" )
            numOfDays += 1;
    }
    collisions2 -= numOfDays;
 
    //for ( int i = 0; i < DAYS_IN_YEAR; i++ ) {
    //	cout << "index: " << i << '\t' << year1[i] << endl;
 
    cout << "hash1" << '\t' << "hash2" << endl
        << "-------" << '\t' << "-------" << endl
        << collisions1 << '\t' << collisions2 << endl;
 
    return 0;
}
 
int hash1(int month, int day)
{
    return ( ( month + (3 * day) ) % 101 );
}
 
int hash2(int month, int day)
{
    return ( ( day + ( 3 * month ) ) % 101 );
}
 
string formatDate(int month, int day)
{
    stringstream ss;
    ss << month << "/" << day;
    return ( ss.str() );
}