about.md- allocator.h.md
- array_list.h.md
- buffer.h.md
- collection.h.md
- collections.md
- compare.h.md
- features.md
- hash_key.h.md
- hash_map.h.md
- install.md
- iterator.h.md
- json.h.md
- kv_list.h.md
- license.md
- linked_list.h.md
- list.h.md
- map.h.md
- memory.md
- mempool.h.md
- parsers.md
- printf.h.md
- properties.h.md
- streams.h.md
- string.h.md
- strings.md
- test.h.md
- tree.h.md
- utils.md
1 # Hash Function
2
3 UCX implements the MurmurHash2 algorithm for computing hashes that are primarily used for [CxMap](map.h.md).
4 But it can be used for arbitrary custom scenarios, too.
5
6 ## Overview
7 ```C
8 #include <cx/hash_key.h>
9
10 void cx_hash_murmur(CxHashKey *key);
11
12 uint32_t cx_hash_u32(uint32_t x);
13 uint64_t cx_hash_u64(uint64_t x);
14
15 CxHashKey cx_hash_key(const void *obj, size_t len);
16 CxHashKey cx_hash_key_str(const char *str);
17 CxHashKey cx_hash_key_ustr(const unsigned char *str);
18 CxHashKey cx_hash_key_bytes(const unsigned char *bytes, size_t len);
19 CxHashKey cx_hash_key_cxstr(cxstring str);
20 CxHashKey cx_hash_key_u32(uint32_t x);
21 CxHashKey cx_hash_key_u64(uint64_t x);
22
23 int cx_hash_key_cmp(const CxHashKey *left, const CxHashKey *right);
24 ```
25
26 ## Description
27
28 The primary function for creating a `CxHashKey` structure from non-integers is `cx_hash_key()`.
29 The other functions effectively do the same, but
30
31 * `cx_hash_key_bytes()` is strongly typed if you want to avoid passing `void*`
32 * `cx_hash_key_str()` conveniently takes a C string and computes the length
33 * `cx_hash_key_ustr()` same as before, but for `unsigned char*`
34 * `cx_hash_key_cxstr()` conveniently takes a [UCX string](string.h.md)
35
36 In all cases, the hash will be available in the `hash` field of the returned structure.
37
38 > Usually you will never need to call any of the other functions directly.
39 > You can always create a `CxHashKey` structure by using the `CX_HASH_KEY()` macro
40 > (when the length of the key is implicitly clear) or by using the `cx_hash_key()` function.
41 > {style="note"}
42
43 > UCX assigns the hash value `1574210520` to the `NULL` pointer.
44 > This is a careful choice that is not standard MurmurHash2 and an extension to support `NULL` pointers.
45
46 Hashes from integers are created more efficiently by mixing up the bits to produce a good statistical distribution.
47 The function `cx_hash_u32()` and `cx_hash_u64()` are provided for this purpose and provide collision-free hashes.
48 The corresponding functions `cx_hash_key_u32()` and `cx_hash_key_u64()` can be used to create `CxHashKey` structures with those hashes.
49
50 > Since integer hashes are collision-free, there is no need to store any `data` in the `CxHashKey` structure.
51
52 If you want to create a hash completely manually,
53 you can initialize the `data` and `len` members of `CxHashKey`
54 and call `cx_hash_murmur()`.
55 It is _not_ recommended to do so.
56
57 Example that is equivalent to `CxHashKey key = cx_hash_str(mystring)`
58 ```C
59 CxHashKey key;
60 key.data = mystring;
61 key.len = strlen(mystring);
62 cx_hash_murmur(&key);
63 ```
64
65 Hash keys are compared with `cx_hash_key_cmp()`.
66
67 <seealso>
68 <category ref="apidoc">
69 <a href="https://ucx.sourceforge.io/api/hash__key_8h.html">hash_key.h</a>
70 </category>
71 </seealso>