diff options
author | antirez <antirez@gmail.com> | 2019-08-02 20:13:16 +0200 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2019-08-02 20:13:21 +0200 |
commit | a368209b1d92987462e4f359b59443a2cad9ef7d (patch) | |
tree | ef9b3a62a99109b84f238be04b559179035bf1d1 | |
parent | 583933e2d6b4c2721554ab77c33a9c0bc7672fa6 (diff) | |
download | redis-a368209b1d92987462e4f359b59443a2cad9ef7d.tar.gz |
tracking_collisions.c: initial skeleton.
... of a program to just test the hashing functions collisions on a 24
bit output with strings that are very likely Redis key names, and names
of a kind that are particularly prone to collisions.
-rw-r--r-- | utils/tracking_collisions.c | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/utils/tracking_collisions.c b/utils/tracking_collisions.c new file mode 100644 index 000000000..b996452e7 --- /dev/null +++ b/utils/tracking_collisions.c @@ -0,0 +1,40 @@ +/* This is a small program used in order to understand the collison rate + * of CRC64 (ISO version) VS other stronger hashing functions in the context + * of hashing keys for the Redis "tracking" feature (client side caching + * assisted by the server). + * + * The program attempts to hash keys with common names in the form of + * + * prefix:<counter> + * + * And counts the resulting collisons generated in the 24 bits of output + * needed for the tracking feature invalidation table (16 millions + entries) + * + * -------------------------------------------------------------------------- + * + * Copyright (C) 2019 Salvatore Sanfilippo + * This code is released under the BSD 2 clause license. + */ + +#include <stdlib.h> +#include <stdint.h> +#include <string.h> +#include <stdio.h> + +#define TABLE_SIZE (1<<24) +int Table[TABLE_SIZE]; + +/* Test the hashing function provided as callback and return the + * number of collisions found. */ +unsigned long testHashingFunction(uint64_t (*hash)(char *, size_t)) { + unsigned long collisions = 0; + memset(Table,0,sizeof(Table)); + char *prefixes[] = {"object", "message", "user", NULL}; + return collisions; +} + +int main(void) { + printf("SHA1 : %lu\n", testHashingFunction(sha1Hash)); + printf("CRC64: %lu\n", testHashingFunction(crc64Hash)); + return 0; +} |