diff options
| author | R David Murray <rdmurray@bitdance.com> | 2016-07-10 16:40:03 (GMT) |
|---|---|---|
| committer | R David Murray <rdmurray@bitdance.com> | 2016-07-10 16:40:03 (GMT) |
| commit | ce85acff3a28cd4c3ded487bfbc8c8ac5462d4e4 (patch) | |
| tree | f90dbc4447dfecbdd45a8adb1bac886bdd3fbbbd /Objects | |
| parent | 20bd3b070a38d3a1897e41e9dd1a6ad97cea9785 (diff) | |
| parent | 537ad7ad9fdefa44fdfd7f5cbee198ad381deb60 (diff) | |
| download | cpython-ce85acff3a28cd4c3ded487bfbc8c8ac5462d4e4.zip cpython-ce85acff3a28cd4c3ded487bfbc8c8ac5462d4e4.tar.gz cpython-ce85acff3a28cd4c3ded487bfbc8c8ac5462d4e4.tar.bz2 | |
Merge: #20647: Update dictobject.c comments to account for randomized string hashes.
Diffstat (limited to 'Objects')
| -rw-r--r-- | Objects/dictobject.c | 13 |
1 files changed, 5 insertions, 8 deletions
diff --git a/Objects/dictobject.c b/Objects/dictobject.c index 31c45ef..7a3ed42 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -88,20 +88,17 @@ it's USABLE_FRACTION (currently two-thirds) full. /* Major subtleties ahead: Most hash schemes depend on having a "good" hash function, in the sense of simulating randomness. Python doesn't: its most -important hash functions (for strings and ints) are very regular in common +important hash functions (for ints) are very regular in common cases: - >>> map(hash, (0, 1, 2, 3)) + >>>[hash(i) for i in range(4)] [0, 1, 2, 3] - >>> map(hash, ("namea", "nameb", "namec", "named")) - [-1658398457, -1658398460, -1658398459, -1658398462] - >>> This isn't necessarily bad! To the contrary, in a table of size 2**i, taking the low-order i bits as the initial table index is extremely fast, and there -are no collisions at all for dicts indexed by a contiguous range of ints. -The same is approximately true when keys are "consecutive" strings. So this -gives better-than-random behavior in common cases, and that's very desirable. +are no collisions at all for dicts indexed by a contiguous range of ints. So +this gives better-than-random behavior in common cases, and that's very +desirable. OTOH, when collisions occur, the tendency to fill contiguous slices of the hash table makes a good collision resolution strategy crucial. Taking only |