Associative arrays/Creation/C: Difference between revisions
Content added Content deleted
m (Delete {{collection}}, because it dumps the page into a phantom category. There seems no requirement to put {{collection}} in this type of page.) |
(Add simple simple way to create hash tables in C) |
||
Line 3: | Line 3: | ||
* Back to [[Associative arrays/Creation]]. |
* Back to [[Associative arrays/Creation]]. |
||
* Back to [[Associative arrays/Iteration]]. |
* Back to [[Associative arrays/Iteration]]. |
||
==From Scratch== |
|||
A hash table can be implemented with the following. Because of this example's simplicity, it comes with some restrictions on use and capabilities: It can't be resized automatically, if you try to insert values than its capacity it will freeze, the hashing function is very simple, etc. All are fixable with additional logic or using a library: |
|||
<lang c>typedef struct { |
|||
int size; |
|||
void **keys; |
|||
void **values; |
|||
} Hash; |
|||
Hash *hash_new (int size) { |
|||
Hash *hash = calloc(1, sizeof (Hash)); |
|||
hash->size = size; |
|||
hash->keys = calloc(size, sizeof (void *)); |
|||
hash->values = calloc(size, sizeof (void *)); |
|||
return hash; |
|||
} |
|||
void hash_free (Hash *hash) { |
|||
free(hash->keys); |
|||
free(hash->values); |
|||
free(hash); |
|||
} |
|||
int hash_index (Hash *hash, void *key) { |
|||
int index = (int) key % hash->size; |
|||
while (hash->keys[index] && hash->keys[index] != key) |
|||
index = (index + 1) % hash->size; |
|||
return index; |
|||
} |
|||
void hash_insert (Hash *hash, void *key, void *value) { |
|||
int index = hash_index(hash, key); |
|||
hash->keys[index] = key; |
|||
hash->values[index] = value; |
|||
} |
|||
void *hash_lookup (Hash *hash, void *key) { |
|||
int index = hash_index(hash, key); |
|||
return hash->values[index]; |
|||
} |
|||
int main () { |
|||
Hash *hash = hash_new(15); |
|||
hash_insert(hash, "hello", "world"); |
|||
hash_insert(hash, "a", "b"); |
|||
printf("hello => %s\n", hash_lookup(hash, "hello")); |
|||
printf("herp => %s\n", hash_lookup(hash, "herp")); |
|||
printf("a => %s\n", hash_lookup(hash, "a")); |
|||
return 0; |
|||
}</lang> |
|||
==Libraries== |
==Libraries== |