README.md (4788B)
1 # hashmap.c 2 3 [Hash map](https://en.wikipedia.org/wiki/Hash_table) implementation in C. 4 5 ## Features 6 7 - [Open addressing](https://en.wikipedia.org/wiki/Hash_table#Open_addressing) using [Robin Hood](https://en.wikipedia.org/wiki/Hash_table#Robin_Hood_hashing) hashing 8 - Generic interface with support for variable sized items. 9 - Built-in [SipHash](https://en.wikipedia.org/wiki/SipHash) or [MurmurHash3](https://en.wikipedia.org/wiki/MurmurHash) and allows for alternative algorithms. 10 - ANSI C (C99) 11 - Supports custom allocators 12 - Pretty darn good performance. 🚀 13 14 ## Example 15 16 ```c 17 #include <stdio.h> 18 #include <string.h> 19 #include "hashmap.h" 20 21 struct user { 22 char *name; 23 int age; 24 }; 25 26 int user_compare(const void *a, const void *b, void *udata) { 27 const struct user *ua = a; 28 const struct user *ub = b; 29 return strcmp(ua->name, ub->name); 30 } 31 32 bool user_iter(const void *item, void *udata) { 33 const struct user *user = item; 34 printf("%s (age=%d)\n", user->name, user->age); 35 return true; 36 } 37 38 uint64_t user_hash(const void *item, uint64_t seed0, uint64_t seed1) { 39 const struct user *user = item; 40 return hashmap_sip(user->name, strlen(user->name), seed0, seed1); 41 } 42 43 int main() { 44 // create a new hash map where each item is a `struct user`. The second 45 // argument is the initial capacity. The third and fourth arguments are 46 // optional seeds that are passed to the following hash function. 47 struct hashmap *map = hashmap_new(sizeof(struct user), 0, 0, 0, 48 user_hash, user_compare, NULL, NULL); 49 50 // Here we'll load some users into the hash map. Each set operation 51 // performs a copy of the data that is pointed to in the second argument. 52 hashmap_set(map, &(struct user){ .name="Dale", .age=44 }); 53 hashmap_set(map, &(struct user){ .name="Roger", .age=68 }); 54 hashmap_set(map, &(struct user){ .name="Jane", .age=47 }); 55 56 struct user *user; 57 58 printf("\n-- get some users --\n"); 59 user = hashmap_get(map, &(struct user){ .name="Jane" }); 60 printf("%s age=%d\n", user->name, user->age); 61 62 user = hashmap_get(map, &(struct user){ .name="Roger" }); 63 printf("%s age=%d\n", user->name, user->age); 64 65 user = hashmap_get(map, &(struct user){ .name="Dale" }); 66 printf("%s age=%d\n", user->name, user->age); 67 68 user = hashmap_get(map, &(struct user){ .name="Tom" }); 69 printf("%s\n", user?"exists":"not exists"); 70 71 printf("\n-- iterate over all users (hashmap_scan) --\n"); 72 hashmap_scan(map, user_iter, NULL); 73 74 printf("\n-- iterate over all users (hashmap_iter) --\n"); 75 size_t iter = 0; 76 void *item; 77 while (hashmap_iter(map, &iter, &item)) { 78 const struct user *user = item; 79 printf("%s (age=%d)\n", user->name, user->age); 80 } 81 82 hashmap_free(map); 83 } 84 85 // output: 86 // -- get some users -- 87 // Jane age=47 88 // Roger age=68 89 // Dale age=44 90 // not exists 91 // 92 // -- iterate over all users (hashmap_scan) -- 93 // Dale (age=44) 94 // Roger (age=68) 95 // Jane (age=47) 96 // 97 // -- iterate over all users (hashmap_iter) -- 98 // Dale (age=44) 99 // Roger (age=68) 100 // Jane (age=47) 101 102 ``` 103 104 ## Functions 105 106 ### Basic 107 108 ```sh 109 hashmap_new # allocate a new hash map 110 hashmap_free # free the hash map 111 hashmap_count # returns the number of items in the hash map 112 hashmap_set # insert or replace an existing item and return the previous 113 hashmap_get # get an existing item 114 hashmap_delete # delete and return an item 115 hashmap_clear # clear the hash map 116 ``` 117 118 ### Iteration 119 120 ```sh 121 hashmap_iter # loop based iteration over all items in hash map 122 hashmap_scan # callback based iteration over all items in hash map 123 ``` 124 125 ### Hash helpers 126 127 ```sh 128 hashmap_sip # returns hash value for data using SipHash-2-4 129 hashmap_murmur # returns hash value for data using MurmurHash3 130 ``` 131 132 ## Testing and benchmarks 133 134 ```sh 135 $ cc -DHASHMAP_TEST hashmap.c && ./a.out # run tests 136 $ cc -DHASHMAP_TEST -O3 hashmap.c && BENCH=1 ./a.out # run benchmarks 137 ``` 138 139 The following benchmarks were run on my 2019 Macbook Pro (2.4 GHz 8-Core Intel Core i9) using gcc-9. 140 The items are simple 4-byte ints. 141 The hash function is MurmurHash3. 142 Testing with 5,000,000 items. 143 The `(cap)` results are hashmaps that are created with an inital capacity of 5,000,000. 144 145 ``` 146 set 5000000 ops in 0.708 secs, 142 ns/op, 7057960 op/sec, 26.84 bytes/op 147 get 5000000 ops in 0.303 secs, 61 ns/op, 16492723 op/sec 148 delete 5000000 ops in 0.486 secs, 97 ns/op, 10280873 op/sec 149 set (cap) 5000000 ops in 0.429 secs, 86 ns/op, 11641660 op/sec 150 get (cap) 5000000 ops in 0.303 secs, 61 ns/op, 16490493 op/sec 151 delete (cap) 5000000 ops in 0.410 secs, 82 ns/op, 12200091 op/sec 152 ``` 153 154 ## License 155 156 hashmap.c source code is available under the MIT License.