Lines Matching defs:hash
1 /* Dictionary object implementation using a hash table */
144 Major subtleties ahead: Most hash schemes depend on having a "good" hash
146 important hash functions (for ints) are very regular in common
149 >>>[hash(i) for i in range(4)]
159 hash table makes a good collision resolution strategy crucial. Taking only
160 the last i bits of the hash code is also vulnerable: for example, consider
162 their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
163 of every hash code are all 0: they *all* map to the same table index.
182 actually *good* in the common cases where hash keys are consecutive. In an
192 extremely unlikely hash codes will follow a 5*j+1 recurrence by accident,
193 and certain that consecutive hash codes do not.
195 The other half of the strategy is to get the other bits of the hash code
197 full hash code, and changing the recurrence to:
203 Now the probe sequence depends (eventually) on every bit in the hash code,
213 small so that the high bits of the hash code continue to affect the probe
215 the high-order hash bits have an effect on early iterations. 5 was "the
223 efficient way to get the high bits of the hash code into play. This scheme
289 return _PyASCIIObject_CAST(o)->hash;
495 printf("key=%p hash=%lx value=%p\n", ep->me_key, ep->me_hash, ep->me_value);
548 Py_hash_t hash = unicode_get_hash(key);
549 CHECK(entry->me_hash == hash);
562 Py_hash_t hash = unicode_get_hash(key);
563 CHECK(hash != -1);
844 /* Search index of hash table from offset of entry table */
846 lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
849 size_t perturb = (size_t)hash;
850 size_t i = (size_t)hash & mask;
868 unicodekeys_lookup_generic(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
872 size_t perturb = hash;
873 size_t i = (size_t)hash & mask;
884 if (unicode_get_hash(ep->me_key) == hash) {
914 unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
918 size_t perturb = hash;
919 size_t i = (size_t)hash & mask;
928 (unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
943 (unicode_get_hash(ep->me_key) == hash && unicode_eq(ep->me_key, key))) {
958 dictkeys_generic_lookup(PyDictObject *mp, PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
962 size_t perturb = hash;
963 size_t i = (size_t)hash & mask;
973 if (ep->me_hash == hash) {
1014 Py_hash_t hash = unicode_get_hash(key);
1015 if (hash == -1) {
1016 hash = PyUnicode_Type.tp_hash(key);
1017 if (hash == -1) {
1022 return unicodekeys_lookup_unicode(dk, key, hash);
1031 The initial probe index is computed as hash mod the table size. Subsequent
1034 All arithmetic on hash should ignore overflow.
1041 _Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
1053 ix = unicodekeys_lookup_unicode(dk, key, hash);
1056 ix = unicodekeys_lookup_generic(mp, dk, key, hash);
1075 ix = dictkeys_generic_lookup(mp, dk, key, hash);
1160 /* Internal function to find slot for an item from its hash
1165 find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
1170 size_t i = hash & mask;
1172 for (size_t perturb = hash; ix >= 0;) {
1190 Py_hash_t hash = unicode_get_hash(name);
1191 if (hash == -1) {
1192 hash = PyUnicode_Type.tp_hash(name);
1193 if (hash == -1) {
1198 Py_ssize_t ix = unicodekeys_lookup_unicode(keys, name, hash);
1206 Py_ssize_t hashpos = find_empty_slot(keys, hash);
1226 insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
1236 Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
1252 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
1273 ep->me_hash = hash;
1318 insert_to_emptydict(PyDictObject *mp, PyObject *key, Py_hash_t hash,
1336 size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1);
1346 ep->me_hash = hash;
1364 Py_hash_t hash = ep->me_hash;
1365 size_t i = hash & mask;
1366 for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
1379 Py_hash_t hash = unicode_get_hash(ep->me_key);
1380 assert(hash != -1);
1381 size_t i = hash & mask;
1382 for (size_t perturb = hash; dictkeys_get_index(keys, i) != DKIX_EMPTY;) {
1642 * (suppressed) occurred while computing the key's hash, or that some error
1656 Py_hash_t hash;
1657 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1658 hash = PyObject_Hash(key);
1659 if (hash == -1) {
1678 ix = _Py_dict_lookup(mp, key, hash, &value);
1733 Py_hash_t hash = unicode_get_hash(key);
1734 if (hash == -1) {
1735 hash = PyObject_Hash(key);
1736 if (hash == -1) {
1741 return _Py_dict_lookup(mp, key, hash, value);
1744 /* Same as PyDict_GetItemWithError() but with hash supplied by caller.
1749 _PyDict_GetItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
1760 ix = _Py_dict_lookup(mp, key, hash, &value);
1773 Py_hash_t hash;
1781 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1)
1783 hash = PyObject_Hash(key);
1784 if (hash == -1) {
1789 ix = _Py_dict_lookup(mp, key, hash, &value);
1798 Py_hash_t hash = kv->ob_type->tp_hash(kv);
1799 if (hash == -1) {
1802 return _PyDict_GetItem_KnownHash(dp, kv, hash);
1812 Py_hash_t hash = unicode_get_hash(kv);
1813 assert (hash != -1); /* interned strings have their hash value initialised */
1814 return _PyDict_GetItem_KnownHash(dp, kv, hash);
1837 * key hash failed, key comparison failed, ...). Return NULL if the key doesn't
1844 Py_hash_t hash;
1847 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1848 hash = PyObject_Hash(key);
1849 if (hash == -1)
1854 ix = _Py_dict_lookup(globals, key, hash, &value);
1861 ix = _Py_dict_lookup(builtins, key, hash, &value);
1873 Py_hash_t hash;
1874 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1875 hash = PyObject_Hash(key);
1876 if (hash == -1) {
1883 return insert_to_emptydict(mp, key, hash, value);
1886 return insertdict(mp, key, hash, value);
1911 Py_hash_t hash)
1921 assert(hash != -1);
1927 return insert_to_emptydict(mp, key, hash, value);
1930 return insertdict(mp, key, hash, value);
1950 delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
1955 Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
1995 Py_hash_t hash;
1997 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
1998 hash = PyObject_Hash(key);
1999 if (hash == -1)
2003 return _PyDict_DelItem_KnownHash(op, key, hash);
2007 _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
2018 assert(hash != -1);
2020 ix = _Py_dict_lookup(mp, key, hash, &old_value);
2028 return delitem_common(mp, hash, ix, old_value);
2041 Py_hash_t hash;
2050 hash = PyObject_Hash(key);
2051 if (hash == -1)
2054 ix = _Py_dict_lookup(mp, key, hash, &old_value);
2066 hashpos = lookdict_index(mp->ma_keys, hash, ix);
2113 /* Internal version of PyDict_Next that returns a hash value in addition
2125 Py_hash_t hash;
2139 hash = unicode_get_hash(key);
2155 hash = unicode_get_hash(entry_ptr->me_key);
2167 hash = entry_ptr->me_hash;
2177 *phash = hash;
2207 _PyDict_Pop_KnownHash(PyObject *dict, PyObject *key, Py_hash_t hash, PyObject *deflt)
2224 ix = _Py_dict_lookup(mp, key, hash, &old_value);
2237 delitem_common(mp, hash, ix, old_value);
2246 Py_hash_t hash;
2256 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
2257 hash = PyObject_Hash(key);
2258 if (hash == -1)
2261 return _PyDict_Pop_KnownHash(dict, key, hash, deflt);
2283 Py_hash_t hash;
2291 while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) {
2294 if (insertdict(mp, key, hash, value)) {
2305 Py_hash_t hash;
2312 while (_PySet_NextEntry(iterable, &pos, &key, &hash)) {
2315 if (insertdict(mp, key, hash, value)) {
2492 Py_hash_t hash;
2495 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
2496 hash = PyObject_Hash(key);
2497 if (hash == -1)
2500 ix = _Py_dict_lookup(mp, key, hash, &value);
2887 Py_hash_t hash;
2890 while (_PyDict_Next((PyObject*)other, &pos, &key, &value, &hash)) {
2897 err = insertdict(mp, key, hash, value);
2900 err = _PyDict_Contains_KnownHash(a, key, hash);
2904 err = insertdict(mp, key, hash, value);
3162 Py_hash_t hash;
3169 hash = unicode_get_hash(key);
3179 hash = ep->me_hash;
3189 /* reuse the known hash value */
3190 _Py_dict_lookup(b, key, hash, &bval);
3247 Py_hash_t hash;
3251 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3252 hash = PyObject_Hash(key);
3253 if (hash == -1)
3256 ix = _Py_dict_lookup(mp, key, hash, &value);
3279 Py_hash_t hash;
3282 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3283 hash = PyObject_Hash(key);
3284 if (hash == -1)
3287 ix = _Py_dict_lookup(self, key, hash, &val);
3302 Py_hash_t hash;
3309 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3310 hash = PyObject_Hash(key);
3311 if (hash == -1)
3318 if (insert_to_emptydict(mp, key, hash, defaultobj) < 0) {
3330 Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &value);
3342 Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
3362 ep->me_hash = hash;
3485 Py_hash_t hash;
3495 hash = unicode_get_hash(key);
3509 hash = ep0[i].me_hash;
3516 j = lookdict_index(self->ma_keys, hash, i);
3693 Py_hash_t hash;
3698 if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
3699 hash = PyObject_Hash(key);
3700 if (hash == -1)
3703 ix = _Py_dict_lookup(mp, key, hash, &value);
3709 /* Internal version of PyDict_Contains used when the hash value is already known */
3711 _PyDict_Contains_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
3717 ix = _Py_dict_lookup(mp, key, hash, &value);
4918 Py_hash_t hash;
4920 while (_PyDict_Next(d2, &pos, &key, &val2, &hash)) {
4923 val1 = _PyDict_GetItem_KnownHash(temp_dict, key, hash);
4941 if (_PyDict_DelItem_KnownHash(temp_dict, key, hash) < 0) {