which hash table - chained or open-addressed?

[Eric Sosman]

[...] Note,
too, that an AND simply discards bits from the hash value;
if you engage in a more complex "folding" operation to let
all the bits participate, the cycle count starts creeping up
toward that of the division.

Real hash functions don't require folding.

Are you saying that a "real" hash function is one whose
high-order bits are irrelevant and can be discarded without
degrading the performance of the hash? If so, it's easy to
see that the only "real" hash functions are constant, yielding
the same output for all inputs (retain the low-order N bits
and consider the behavior as N->0).

Real hash functions (in my notion of "real," not yours)
put useful information in all their output bits.

[...] More generally, if you choose a table
of size T, the skip distances Si should be relatively prime to
T but need not be prime. The attraction of a prime T is that
it's easy to find Si that are relatively prime to it!

Easy but costly. To find small primes for skip values [...]

You don't need to "find" anything. If T is prime, all
numbers in [2,T-1] are relatively prime to it.

I don't know what kind of thing you want to hash, where the index and
stored hash is not dominated by the actual raw data that you are
hashing in the first place.

Consider a large number of large objects, each with half a
dozen keys by which you might want to locate it. Put each object
in six hash tables without wasting a ton of storage and without
making duplicate copies that need to be kept in synch. (And this
time, try not to overlook the phrase "open-addressed table.")

[...] And there's
where the interesting part comes in: For the same expenditure of
storage, you could have a pointers-only table with twice as many
entries,

Huh? In a chained hash solution, [...]

Again, I draw your attention to the phrase "open-addressed
table."

[...] or half the "load factor" for the same number of stored
items. Search and insertion times rise steeply at high load
factors (in ways that depend on the algorithms), so the potential
reduction in probe count might make up for the increased number
of item comparisons per probe.

You must be smoking pot. [...]

I bow to your obviously superior experience of mind-altering
substances, and thank you for this insight into the sources of
your social skills.

 

[santosh]

Richard Bos wrote, On 26/01/07 10:17:

That's all I use it for as well, and each update I've seen seems to make
it worse than the last. Were it not for disk space requirements and the
resulting cost I would be inclined to set up my own competing free (and
advertising free) service.

Indeed. The developers in Google responsible for Groups must be mad. In
this "new" interface, one has to use both the horizontal and vertical
scrollbars to read any message. The entire right half of the page is
hogged by ads.

IIRC, it's possible to request feeds for only the groups your node
wants to host. That ought to keep disk consumption to a permissible
level. Then again, not all servers provide partial feeds.

Santosh did not say how he would get a subscription with. There are
plenty of free or very cheap Usenet providers he could choose from.

I was considering dotsrc.org and aioe.org in the free category and
teranews in the subscription category. The aioe server seems to respond
well, but has a 25 posts per day limit. The registration for dotsrc.org
never seems to succeed. I really don't know much about the pros and
cons of the subscription based services.

Usenet is almost unknown back here, except perhaps in the academia.

 

[matevzb]

The developers in Google responsible for Groups must be mad. In
this "new" interface, one has to use both the horizontal and vertical
scrollbars to read any message. The entire right half of the page is
hogged by ads.

To remove the ads, the following filter seems nicely to work with
Firefox + Adblock:
http://groups.google.com/groups/adfetch*
You won't remove the right frame with this, but it's better than
nothing.

 

[santosh]

To remove the ads, the following filter seems nicely to work with
Firefox + Adblock:
http://groups.google.com/groups/adfetch*
You won't remove the right frame with this, but it's better than
nothing.

Unfortunately, that's of no use. The right frame consumes roughly half
the screen space, forcing me to use both scrollbars for the middle
frame, where the posts appear. The frames used to be resizable in the
old interface, but in this "new" one, you can make them larger, but not
smaller.

Google seems not to attach too much importance to it's Usenet access.
It seems to be mainly concerned about it's private groups, which I
don't care to read.

 

[Ian Collins]

Unfortunately, that's of no use. The right frame consumes roughly half
the screen space, forcing me to use both scrollbars for the middle
frame, where the posts appear. The frames used to be resizable in the
old interface, but in this "new" one, you can make them larger, but not
smaller.

You can addblock the iframe. All I see are the messages and a small
right hand information column. Not an add in sight.

 

[Keith Thompson]

Indeed. The developers in Google responsible for Groups must be mad. In
this "new" interface, one has to use both the horizontal and vertical
scrollbars to read any message. The entire right half of the page is
hogged by ads.

That's odd. In my browser (Opera under Windows), the left and right
frames are fixed at about 200 pixels wide; the article appears in the
center, which takes up the rest of the window. It's annoying that I
can't expand the left frame. (I run it maximized on a 1600x1200
display.) Maybe there's something wrong either with their frames
code, or your browser's handling of it.

 

[santosh]

That's odd. In my browser (Opera under Windows), the left and right
frames are fixed at about 200 pixels wide; the article appears in the
center, which takes up the rest of the window. It's annoying that I
can't expand the left frame.

It's similar here, (Firefox under Linux), except for the fact that I
can expand the left frame, but not contract it, which is what I want to
do, to give maximum space to the middle frame, where the articles
appear. The right frame is also not resizable, thoough the ads in it
are blockable.

(I run it maximized on a 1600x1200
display.) Maybe there's something wrong either with their frames
code, or your browser's handling of it.

I don't think so.

I think that Google have designed their interface with the assumption
that the minimum screen resolution would be 1024x768. My monitor does
support that resolution, but at a refresh rate of 60 Hz, at which
flicker is noticeable. So I run it at 800x600 and a better refresh rate
of 85 Hz.

As I said, time to upgrade the monitor or get a real Usenet
subscription.

 

[santosh]

You can addblock the iframe. All I see are the messages and a small
right hand information column. Not an add in sight.

Yes, I've blocked the ads, but at 800x600 resolution, this "small right
hand information column", takes roughly 1/3rd of the screen space. As I
said elsewhere, Google seems to assume that users would use a minimum
resolution of 1024x768, at which rate my monitor flickers too much, so
I run it at 800x600.

 

[Ian Collins]

Yes, I've blocked the ads, but at 800x600 resolution, this "small right
hand information column", takes roughly 1/3rd of the screen space. As I
said elsewhere, Google seems to assume that users would use a minimum
resolution of 1024x768, at which rate my monitor flickers too much, so
I run it at 800x600.

You poor bugger, I thought 5120x1600 was enough pixels....

 

[matevzb]

can expand the left frame, but not contract it, which is what I want to
do, to give maximum space to the middle frame, where the articles
appear. The right frame is also not resizable, thoough the ads in it
are blockable.


I think that Google have designed their interface with the assumption
that the minimum screen resolution would be 1024x768. My monitor does
support that resolution, but at a refresh rate of 60 Hz, at which
flicker is noticeable. So I run it at 800x600 and a better refresh rate
of 85 Hz.

As I said, time to upgrade the monitor or get a real Usenet
subscription.

Maybe this will help you. It's off-topic of course (javascript, yay!),
but it works for me. Copy the code below and paste it into address
bar, press return. Better yet, create a new bookmark on the bookmarks
toolbar and paste the code into "Location" field. You still have to
click it each time, but it's free =]
---begin_code---
javascriptfunction(){var i,
n=document.getElementById("google_ads_site").parentNode.parentNode.pare
ntNode.parentNode, cols=document.getElementsByTagName("col");
n.style.display="none"; for(i=0;i<cols.length;i++){if
(cols.style.width=="32ex"){cols.style.display="none";
break;} } })();
---end_code---

 

[santosh]

[...]
Indeed. The developers in Google responsible for Groups must be mad. In
this "new" interface, one has to use both the horizontal and vertical
scrollbars to read any message. The entire right half of the page is
hogged by ads.

That's odd. In my browser (Opera under Windows), the left and right
frames are fixed at about 200 pixels wide; the article appears in the
center, which takes up the rest of the window. It's annoying that I
can't expand the left frame.It's similar here, (Firefox under Linux), except for the fact that I

can expand the left frame, but not contract it, which is what I want to
do, to give maximum space to the middle frame, where the articles
appear. The right frame is also not resizable, thoough the ads in it
are blockable.

(I run it maximized on a 1600x1200
display.) Maybe there's something wrong either with their frames
code, or your browser's handling of it.I don't think so.

I think that Google have designed their interface with the assumption
that the minimum screen resolution would be 1024x768. My monitor does
support that resolution, but at a refresh rate of 60 Hz, at which
flicker is noticeable. So I run it at 800x600 and a better refresh rate
of 85 Hz.

As I said, time to upgrade the monitor or get a real Usenet
subscription.

Maybe this will help you. It's off-topic of course (javascript, yay!),
but it works for me. Copy the code below and paste it into address
bar, press return. Better yet, create a new bookmark on the bookmarks
toolbar and paste the code into "Location" field. You still have to
click it each time, but it's free =]
---begin_code---
javascriptfunction(){var i,
n=document.getElementById("google_ads_site").parentNode.parentNode.pare
ntNode.parentNode, cols=document.getElementsByTagName("col");
n.style.display="none"; for(i=0;i<cols.length;i++){if
(cols.style.width=="32ex"){cols.style.display="none";
break;} } })();
---end_code---

Thanks a lot. It does work. Goes to show the usefullness of knowing
more than one language! Did you write this piece of code yourself?

 

[matevzb]

As I said, time to upgrade the monitor or get a real Usenet
subscription.

Maybe this will help you. It's off-topic of course (javascript, yay!),
but it works for me. Copy the code below and paste it into address
bar, press return. Better yet, create a new bookmark on the bookmarks
toolbar and paste the code into "Location" field. You still have to
click it each time, but it's free =]
---begin_code---
javascriptfunction(){var i,
n=document.getElementById("google_ads_site").parentNode.parentNode.pare
ntNode.parentNode, cols=document.getElementsByTagName("col");
n.style.display="none"; for(i=0;i<cols.length;i++){if
(cols.style.width=="32ex"){cols.style.display="none";
break;} } })();
---end_code---Thanks a lot. It does work. Goes to show the usefullness of knowing

more than one language! Did you write this piece of code yourself?

Yes, luckily the syntax is C-like and, having written some web-related
code in the past, I still recall the basics. If it were perl, then I'd
have to re-learn it (yet again). =)

 

[websnarf]

[...] Note,
too, that an AND simply discards bits from the hash value;
if you engage in a more complex "folding" operation to let
all the bits participate, the cycle count starts creeping up
toward that of the division.

Real hash functions don't require folding.

Are you saying that a "real" hash function is one whose
high-order bits are irrelevant and can be discarded without
degrading the performance of the hash?

Not, irrelevant, *independent*. Obviously removing bits reduces the
range; but we are talking about different "strategies" for reducing
this range. For any serious hash function, if you need to use only a
fixed finite number of sub-set of the number of bits, then simply
*selecting* those bits is at least (up to some small deviation by some
measure) as good any mix of the input bits (including the raw input).
In other words, folding is a pointless waste that does nothing.

[...] If so, it's easy to
see that the only "real" hash functions are constant, yielding
the same output for all inputs (retain the low-order N bits
and consider the behavior as N->0).

I don't have any comprehension of what you are writing here. Can you
elucidate?

Real hash functions (in my notion of "real," not yours)
put useful information in all their output bits.

Well, that's a subset of my definition, and you have provided no
evidence that this is yours. It seems very unlikely that you've
actually put any effort into studying hash functions at all. Each bit
function must also be *INDEPENDENT*.

[...] More generally, if you choose a table
of size T, the skip distances Si should be relatively prime to
T but need not be prime. The attraction of a prime T is that
it's easy to find Si that are relatively prime to it!

Easy but costly. To find small primes for skip values [...]

You don't need to "find" anything. If T is prime, all
numbers in [2,T-1] are relatively prime to it.

Yes, I realize that. But that is an extremely shallow performance
analysis. Chain clustering starts happening when these Si start
sharing common factors. Since you are just picking numbers at random,
there is an actual rate that that will happen (PI^2/6 or something
like that? I don't recall, and am too lazy to rederive it here) is
higher than it needs to be.

If instead you pick primes for Si, then so long as the chains are long
enough not to wrap (a safe assumption, for small enough primes, and
large enough tables; i.e. where it matters) then bad clustering due to
the Si alone can only happen if you pick *THE SAME* Si (since
different primes are always coprime with each other.)

Couple with this with the fact that you will pay the idiotic penalty
of computing a real modulo (%) operation on a per access basis and you
can't help but conclude that this is a laughably stupid strategy.

 

[Christopher Layne]

That's odd. In my browser (Opera under Windows), the left and right
frames are fixed at about 200 pixels wide; the article appears in the
center, which takes up the rest of the window. It's annoying that I
can't expand the left frame. (I run it maximized on a 1600x1200
display.) Maybe there's something wrong either with their frames
code, or your browser's handling of it.

Ken and I have something in common:

We both use Opera.

(unlike the hoardes of Firefox users who use it out of pack mentality)

 

[Ian Collins]

(unlike the hoardes of Firefox users who use it out of pack mentality)

Utter nonsense, but off topic.

 

[Christopher Layne]

Utter nonsense, but off topic.

Yeah I admit, it was tongue in cheek trolling. Sorry.

 

[Richard Heathfield]

Christopher Layne said:

Ken and I have something in common:

Did you mean "Keith"?

We both use Opera.

It's the pack mentality.

(unlike the hoardes of Firefox users who use it out of pack mentality)

That's merely a bigger pack.

 

[Christopher Layne]

Did you mean "Keith"?

Woops, yes, I meant Keith. Sorry about that.

It's the pack mentality.

Right. Been using Opera for around 7 years now, back since Opera 5/6. It's my
primary browser when using my windows applications - but most of the time I'm
using Konqueror under an NX session. Of all the popular browsers out there,
Opera probably has the lowest userbase - yet it's had tabs for ages, and
strives for stricter compliance than most.

What do you use Richard? Lynx?

That's merely a bigger pack.

s/pack/trend/g

 

[Richard Heathfield]

Christopher Layne said:

Woops, yes, I meant Keith. Sorry about that.


Right. Been using Opera for around 7 years now, back since Opera 5/6.
It's my primary browser when using my windows applications - but most
of the time I'm using Konqueror under an NX session. Of all the
popular browsers out there, Opera probably has the lowest userbase -
yet it's had tabs for ages, and strives for stricter compliance than
most.

What do you use Richard? Lynx?

Yes, when checking that People Out There can see my Web site (because
it's hosted on the PC sat right by my desk, which means I can still see
it when The Rest of the World can't, which is great for fixing it but
bad for testing that I've fixed it). First I ssh out to a remote site
(generally I use a wonderful little server in the western half of the
USA), then I lynx back.

I also use lynx if I have any particular reason (other than just general
paranoia) to be wary of a site.

For more general browsing, I use galeon because it loads quite quickly.
It can handle almost everything that I want to browse. For the few
things it can't, I switch to konqueror. On the rare occasions when (a)
neither galeon nor konqueror can handle it and (b) I really want to
browse that site, I use netscape. And if netscape can't handle it, I
decide the site can't be that interesting after all.

 

[James Dow Allen]

I'm at a different Internet cafe than usual, and
*would not have been able to access Google Groups*
(without extreme mascochism) except that I noticed
this post a few days ago.

Maybe this will help you.
... Better yet, create a new bookmark on the bookmarks
toolbar and paste the code into "Location" field. You still have to
click it each time, but it's free =]
---begin_code---
javascriptfunction(){var i, ..

Thank you! Thank you! Merci beaucoup.
Danke schoen and Khop Khnu Khrap.
Grazie.

You're my new hero, Mr. matevzb.
I hope you don't mind, but I think I'll be
pasting your script into the address bar
a lot in future. (In fact it's there now;
presumably it won't interfere 2 seconds from
now when I press Send.) I also intend
to plant the script on my HomePage,
lest I forget it to bring it some day!

PS: returning to the topic "Hash - chained or open"
Why aren't people using Cuckoo? Its
inventors classify it as "Open" but I think
a 3rd type of hash table ("alternate address")
needs to be created for it.

Thanks again and mucho gracias,
James