hash-table/hash_table.cpp at master · ihiiro/hash-table · GitHub

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155


/*

    The table size is fixed and assumes no resizing is necessary.
    Open addressing is used, which means collision is resolved via
    a type of probing, linear probing is used with a fixed length of 1.

    Hash function used: FNV-1a 64bit variant.

 */

#include <stdint.h>
#include <sys/types.h>
#include <cstring>

#ifndef FNV_PRIME
 #define FNV_PRIME 1099511628211UL
#endif

#ifndef FNV_OFFSET_BASIS
 #define FNV_OFFSET_BASIS 14695981039346656037UL
#endif

#ifndef PROBE_LENGTH
 #define PROBE_LENGTH 1
#endif

/*

  the fixed capacity.
  note that with a non fixed capacity you should
  resize the table whenever the load factor approaches
  around half the capacity to prevent operations from
  degenerating into linear performance.

*/
#ifndef M
 #define M 200
#endif

typedef struct {
    const u_char *key;
    const u_char *value;
} bucket;

typedef struct {
    bucket *buckets;
    // uint64_t n; /* # of filled buckets */
} ht;


uint64_t FNV_1A_HASH ( const u_char *k )
{

    uint64_t hash = FNV_OFFSET_BASIS;
    for ( ; *k ; k++ )
    {

        hash ^= *k;
        hash *= FNV_PRIME;

    }

    return hash;

}

uint64_t hash ( const u_char *k )
{

    return FNV_1A_HASH ( k ) % M ;

}

void insert ( ht *HT , const u_char *key , const u_char *value )
{

    uint64_t index = hash ( key );

    /* linear probing with a fixed length */
    while ( 1 )
    {

        if ( index == M )
        {

            index = 0;
            continue;

        }
        if ( HT->buckets [ index ].key == NULL )
        {

            HT->buckets [ index ].key = key;
            HT->buckets [ index ].value = value;
            return;

        }

        index += PROBE_LENGTH;

    }

}

bucket *get ( ht *HT , const u_char *key )
{

    uint64_t index = hash ( key );

    while ( 1 )
    {

        if ( HT->buckets [ index ].key == NULL )
            return NULL;
        if ( index == M )
        {

            index = 0;
            continue;

        }
        if ( key and HT->buckets [ index ].key and
            std::strcmp ( (char *)key , (char *)HT->buckets [ index ].key  ) == 0 )
            return &HT->buckets [ index ];

        index += PROBE_LENGTH;

    }

}


#include <iostream>

int main ( int argc, char **argv )
{
    ht *hash_table = new ht;
    hash_table->buckets = new bucket [ M ];
    // hash_table->n = 0;
    std::memset ( hash_table->buckets , 0 , M );

    u_char *key = (u_char *)"Content-stuff";
    u_char *value = (u_char *)"stuff stuff";
    insert ( hash_table , key , value);

    std::cout << get ( hash_table , key )->key << "\n";
    std::cout << get ( hash_table , key )->value << "\n";


    return 0;

}