- Committer: John Arbash Meinel
- Date: 2009-10-12 15:55:26 UTC
- mto: (4679.5.3 2.1-static-tuple-no-use)
- Revision ID: john@arbash-meinel.com-20091012155526-b46tuz5cibebbnct
Change the _lookup function to use Quadratic Probing.
The main strength is that we get a bit of locality (collision resolution
looks quickly close to the location.)
The main weakness is that we don't use the upper bits of the hash to
induce divergence. So while we nicely handle collisions in neighboring
buckets (Quadratic means their resolution chains will diverge), if
two objects hash to the same bucket, their resolution chains are identical.
The main strength is that we get a bit of locality (collision resolution
looks quickly close to the location.)
The main weakness is that we don't use the upper bits of the hash to
induce divergence. So while we nicely handle collisions in neighboring
buckets (Quadratic means their resolution chains will diverge), if
two objects hash to the same bucket, their resolution chains are identical.
| Filename | Latest Rev | Last Changed | Committer | Comment | Size | ||
|---|---|---|---|---|---|---|---|
 .. |
|||||||
bzrlib
|
1185.1.29 | 19 years ago | Robert Collins | merge merge tweaks from aaron, which includes late |
|
||
|
contrib
|
1185.1.29 | 19 years ago | Robert Collins | merge merge tweaks from aaron, which includes late |
|
||
|
doc
|
1185.1.29 | 19 years ago | Robert Collins | merge merge tweaks from aaron, which includes late |
|
||
|
man1
|
2425.1.1 | 17 years ago | Robert Collins | ``make docs`` now creates a man page at ``man1/bzr |
|
||
|
tools
|
1185.1.29 | 19 years ago | Robert Collins | merge merge tweaks from aaron, which includes late |
|
||
.bzrignore |
4679.3.76 | 15 years ago | John Arbash Meinel | Rename StaticTupleInterner => SimpleSet. This is | 1.2 KB |
|
|
|
.rsyncexclude |
1185.33.36 | 19 years ago | Martin Pool | Exclude more files from dumb-rsync upload | 203 bytes |
|
|
|
BRANCH.TODO |
4325.3.4 | 15 years ago | Johan Walles | Merge from upstream. | 150 bytes |
|
|
bzr |
4676.4.1 | 15 years ago | Martin Pool | merge 2.0rc2, sphinx, and various fixes back to tr | 5.6 KB |
|
|
|
bzr.ico |
3688.3.3 | 16 years ago | John Arbash Meinel | An updated transparent icon for bzr. | 12.7 KB |
|
|
|
COPYING.txt |
1861.2.9 | 18 years ago | Alexander Belchenko | rename gpl.txt => COPYING.txt | 17.5 KB |
|
|
|
INSTALL |
2696.2.4 | 17 years ago | Aaron Bentley | Fix typo | 1.4 KB |
|
|
|
Makefile |
4719.1.1 | 15 years ago | Andrew Bennetts | Add --subunit to 'make check'. | 14.5 KB |
|
|
|
NEWS |
4728.1.1 | 15 years ago | Vincent Ladeuil | Fix gssapi ftp client mode handling | 394 KB |
|
|
|
profile_imports.py |
4183.7.1 | 15 years ago | Sabin Iacob | update FSF mailing address | 5.5 KB |
|
|
|
README |
3286 | 16 years ago | Canonical.com Patch Queue Manager | Start 1.4 development | 3.3 KB |
|
|
|
setup.py |
4679.3.85 | 15 years ago | John Arbash Meinel | Remove everything except for SimpleSet, and clean | 26.7 KB |
|
|
|
TODO |
2382.2.5 | 17 years ago | Martin Pool | Contents of TODO file moved into bug tracker | 115 bytes |
|
|