Lines Matching refs:hash
34 hash of K, let's say it's 19830128, or in binary:
38 Now let's partition this bit representation of the hash into blocks of
48 For example, storing the key K with hash 19830128, results in the following
80 To rehash: for a K/V pair, the hash of K encodes where in the tree V will
83 To optimize memory footprint and handle hash collisions, our implementation
191 key/value. When there's a hash collision, say for k1/v1 and k2/v2
192 we have `hash(k1)==hash(k2)`. Then our collision node will be:
345 uint32_t shift, int32_t hash,
350 uint32_t shift, int32_t hash,
356 uint32_t shift, int32_t hash,
369 hamt_node_collision_new(int32_t hash, Py_ssize_t size);
402 Py_hash_t hash = PyObject_Hash(o);
405 return hash;
407 if (hash == -1) {
412 /* While it's somewhat suboptimal to reduce Python's 64 bit hash to
413 32 bits via XOR, it seems that the resulting hash function
423 Important: do not change this hash reducing function. There are many
429 int32_t xored = (int32_t)(hash & 0xffffffffl) ^ (int32_t)(hash >> 32);
435 hamt_mask(int32_t hash, uint32_t shift)
437 return (((uint32_t)hash >> shift) & 0x01f);
441 hamt_bitpos(int32_t hash, uint32_t shift)
443 return (uint32_t)1 << hamt_mask(hash, shift);
633 If key1 hash is equal to the hash of key2, a Collision node
688 uint32_t shift, int32_t hash,
700 uint32_t bit = hamt_bitpos(hash, shift);
711 `(shift, hash)` pair we can determine:
730 that have the same (hash, shift) pair. */
736 shift + 5, hash, key, val, added_leaf);
757 key in this collection that matches our hash for this shift. */
792 hash,
811 /* There was no key before with the same (shift,hash). */
831 uint32_t jdx = hamt_mask(hash, shift);
855 empty, shift + 5, hash, key, val, added_leaf);
956 uint32_t shift, int32_t hash,
960 uint32_t bit = hamt_bitpos(hash, shift);
980 shift + 5, hash, key, &sub_node);
1096 uint32_t shift, int32_t hash,
1101 uint32_t bit = hamt_bitpos(hash, shift);
1123 /* There are a few keys that have the same hash at the current shift
1127 shift + 5, hash, key, val);
1260 hamt_node_collision_new(int32_t hash, Py_ssize_t size)
1281 node->c_hash = hash;
1317 uint32_t shift, int32_t hash,
1323 if (hash == self->c_hash) {
1324 /* The hash of the 'key' we are adding matches the hash of
1401 /* The hash of the new key is different from the hash that
1421 new_node, shift, hash, key, val, added_leaf);
1435 uint32_t shift, int32_t hash,
1439 if (hash != self->c_hash) {
1493 node->b_bitmap = hamt_bitpos(hash, shift);
1529 uint32_t shift, int32_t hash,
1678 uint32_t shift, int32_t hash,
1688 uint32_t idx = hamt_mask(hash, shift);
1695 /* There's no child node for the given hash. Create a new
1710 shift + 5, hash, key, val, added_leaf);
1735 /* There's a child node for the given hash.
1738 node, shift + 5, hash, key, val, added_leaf);
1762 uint32_t shift, int32_t hash,
1766 uint32_t idx = hamt_mask(hash, shift);
1776 shift + 5, hash, key, &sub_node);
1920 uint32_t shift, int32_t hash,
1926 uint32_t idx = hamt_mask(hash, shift);
1935 return hamt_node_find(node, shift + 5, hash, key, val);
2022 uint32_t shift, int32_t hash,
2025 /* Set key/value to the 'node' starting with the given shift/hash.
2039 shift, hash, key, val, added_leaf);
2044 shift, hash, key, val, added_leaf);
2050 shift, hash, key, val, added_leaf);
2056 uint32_t shift, int32_t hash,
2063 shift, hash, key,
2069 shift, hash, key,
2076 shift, hash, key,
2083 uint32_t shift, int32_t hash,
2086 /* Find the key in the node starting with the given shift/hash.
2102 shift, hash, key, val);
2108 shift, hash, key, val);
2114 shift, hash, key, val);