<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<br>
On 23.01.2012 19:25, Glenn Linderman wrote:
<blockquote cite="mid:4F1DA627.2020407@g.nevcal.com" type="cite">
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
So this sounds like SafeDict, but putting it under the covers and
automatically converting from dict to SafeDict after a collision
threshold has been reached. Let's call it fallback-dict.<br>
<br>
and costs:<br>
<br>
* converting the dict from one hash to the other by rehashing all
the keys.<br>
</blockquote>
<br>
That's not exactly what it does, it calls the randomized
hash-function only for those<br>
keys, that that didn't find a free slot after 20 collision. And it
uses this value only for<br>
the further collision resolution.<br>
<br>
So the value of hash() is used for the first 20 slots,
randomized_hash() is used<br>
after that.<br>
<br>
1st try:
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
slot[i = perturb = hash];<br>
2nd try: slot[i=i * 5 + 1 + (perturb >>= 5)]<br>
3rd try: slot[i=i * 5 + 1 + (perturb >>= 5)]<br>
....<br>
20th try: slot[i= i * 5 + 1 + (perturb >>= 5)]<br>
21th try: slot[i= perturb = randomized_hash(key)] <---- HERE<br>
22th try: slot[i= i * 5 + 1 + (perturb >>= 5)]<br>
<br>
This is also why there is no conversion needed. It's a<br>
per-key/per-lookup rule.<br>
<br>
Frank<br>
</body>
</html>