Skip to content

Commit 629dbd7

Browse files
wesllheywesllhey
authored
Merge pull request TheAlgorithms#527 from wesllhey/master
hash set data structure
2 parents ac13ada + 0db64d5 commit 629dbd7

File tree

4 files changed

+178
-0
lines changed

4 files changed

+178
-0
lines changed

‎data_structures/hash_set/Makefile

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
CC = gcc
2+
CFLAGS = -g -Wall
3+
4+
all: main
5+
6+
main: main.o hash_set.o
7+
$(CC) $(CFLAGS) $^ -o $@
8+
9+
hash_set.o: hash_set.c
10+
$(CC) $(CFLAGS) -c $^
11+
12+
clean:
13+
rm *.o main

‎data_structures/hash_set/hash_set.c

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
#include <stdio.h>
2+
#include <stdlib.h>
3+
4+
#include "hash_set.h"
5+
6+
extern hash_set_t *init_hash_set()
7+
{
8+
hash_set_t *set = (hash_set_t *)malloc(sizeof(hash_set_t));
9+
set->keys = calloc(DEFAULT_HASH_SET_CAPACITY, sizeof(void **));
10+
set->values = calloc(DEFAULT_HASH_SET_CAPACITY, sizeof(void **));
11+
set->length = 0;
12+
set->capacity = DEFAULT_HASH_SET_CAPACITY;
13+
14+
return set;
15+
}
16+
17+
unsigned add(hash_set_t *set, void *value)
18+
{
19+
return put(set, hash(value), value);
20+
}
21+
22+
unsigned put(hash_set_t *set, long long hash, void *value)
23+
{
24+
if (contains_hash(set, hash)) {
25+
if (set->keys[retrieve_index_from_hash(hash, set->capacity)] == value) {
26+
return 0;
27+
}
28+
29+
// collision
30+
resize(set);
31+
32+
return put(set, hash, value);
33+
}
34+
35+
set->keys[retrieve_index_from_hash(hash, set->capacity)] = value;
36+
set->values[set->length++] = value;
37+
38+
return 1;
39+
}
40+
41+
int contains(hash_set_t *set, void *value)
42+
{
43+
return set->keys[retrieve_index_from_hash(hash(value), set->capacity)] == value ? 1 : 0;
44+
}
45+
46+
int contains_hash(hash_set_t *set, long long hash)
47+
{
48+
return set->keys[retrieve_index_from_hash(hash, set->capacity)] ? 1 : 0;
49+
}
50+
51+
void delete(hash_set_t *set, void *value) {
52+
set->keys[retrieve_index_from_hash(hash(value), set->capacity)] = NULL;
53+
}
54+
55+
56+
// adler_32 hash
57+
long long hash(void *value)
58+
{
59+
char *str = value;
60+
61+
int a = 1;
62+
int b = 0;
63+
const int MODADLER = 65521;
64+
65+
for (int i = 0; str[i] != '\0'; i++) {
66+
a = (a + str[i]) % MODADLER;
67+
b = (b + a) % MODADLER;
68+
}
69+
70+
return (b << 16) | a;
71+
}
72+
73+
unsigned retrieve_index_from_hash(const long long hash, const unsigned capacity)
74+
{
75+
return (capacity - 1) & (hash ^ (hash >> 12));
76+
}
77+
78+
void resize(hash_set_t *set)
79+
{
80+
void **keys_resized = calloc((set->capacity <<= 1), sizeof(void **));
81+
82+
for (int i = 0; i < set->length; i++) {
83+
keys_resized[retrieve_index_from_hash(hash(set->values[i]), set->capacity)] = set->values[i];
84+
}
85+
86+
free(set->keys);
87+
88+
set->keys = keys_resized;
89+
90+
void **new_values = (void **)realloc(set->values, set->capacity * sizeof(void **));
91+
set->values = new_values;
92+
}

‎data_structures/hash_set/hash_set.h

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#ifndef __HASH_SET__
2+
#define __HASH_SET__
3+
4+
#define DEFAULT_HASH_SET_CAPACITY 1 << 10
5+
6+
typedef struct {
7+
unsigned capacity;
8+
unsigned length;
9+
void **values;
10+
void **keys;
11+
} hash_set_t;
12+
13+
extern hash_set_t *init_hash_set();
14+
15+
extern unsigned add(hash_set_t *set, void *value);
16+
17+
unsigned put(hash_set_t *set, long long hash, void *value);
18+
19+
extern int contains(hash_set_t *set, void *value);
20+
21+
int contains_hash(hash_set_t *set, long long hash);
22+
23+
extern void delete(hash_set_t *set, void *value);
24+
25+
extern long long hash(void *value);
26+
27+
extern unsigned retrieve_index_from_hash(const long long hash, const unsigned capacity);
28+
29+
extern void resize(hash_set_t *set);
30+
31+
#endif

‎data_structures/hash_set/main.c

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
#include <stdio.h>
2+
3+
#include "hash_set.h"
4+
5+
int main()
6+
{
7+
hash_set_t *set = init_hash_set();
8+
9+
int v1 = 10, v2 = 20, v3 = 30, v4 = 40, v5 = 50, v6 = 60, v7 = 70;
10+
11+
printf("Value %d was add ? %d\n", v1, add(set, &v1));
12+
printf("Value %d was add ? %d\n", v1, add(set, &v1));
13+
printf("contains %d ? %d\n", v1, contains(set, &v1));
14+
15+
printf("Value %d was add ? %d\n", v2, add(set, &v2));
16+
printf("Value %d was add ? %d\n", v2, add(set, &v2));
17+
printf("contains %d ? %d\n", v2, contains(set, &v2));
18+
19+
printf("Value %d was add ? %d\n", v3, add(set, &v3));
20+
printf("Value %d is add ? %d\n", v3, add(set, &v3));
21+
printf("contains %d ? %d\n", v3, contains(set, &v3));
22+
23+
printf("Value %d was add ? %d\n", v4, add(set, &v4));
24+
printf("Value %d was add ? %d\n", v4, add(set, &v4));
25+
printf("contains %d ? %d\n", v4, contains(set, &v4));
26+
27+
printf("Value %d was add ? %d\n", v5, add(set, &v5));
28+
printf("Value %d was add ? %d\n", v5, add(set, &v5));
29+
printf("contains %d ? %d\n", v5, contains(set, &v5));
30+
31+
printf("Value %d is add ? %d\n", v6, add(set, &v6));
32+
printf("Value %d is add ? %d\n", v6, add(set, &v6));
33+
printf("contains %d ? %d\n", v6, contains(set, &v6));
34+
35+
printf("contains %d ? %d\n", v7, contains(set, &v7));
36+
37+
delete(set, &v6);
38+
39+
printf("contains %d ? %d\n", v6, contains(set, &v6));
40+
41+
return 0;
42+
}

0 commit comments

Comments
 (0)