<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#330033">
On 1/23/2012 10:58 AM, Frank Sievertsen wrote:
<blockquote cite="mid:4F1DADD1.4070907@sievertsen.de" type="cite">
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
<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=UTF-8"
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=UTF-8">
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>
</blockquote>
<br>
Interesting idea, and I see it would avoid conversions. What
happens if the data area also removed from the hash? So you enter
20 colliding keys, then 20 more that get randomized, then delete the
18 of the first 20. Can you still find the second 20 keys? Takes
two sets of probes, somehow?<br>
</body>
</html>