"Nick Landsberg" <SPAMhukolauTRAP (AT) SPAMworldnetTRAP (DOT) att.net> wrote

If you store the hash value and record number in an in-memory hash table,
the chances of needing to read in anything other than the desired record
should be very low. Or am I missing your point?

Move that hash table to disc, and use sequential probing, and most of the
time you'll need two reads. The biggest problem with this is delete
operations, or rather, minimising the expense of rebuilding the hash table
when there have been many delete operations.

Alex

"CBFalconer" <cbfalconer (AT) yahoo (DOT) com> wrote

Why do you need pointers?

Maybe we have different things in mind. See my other post for what I was
thinking of.

[snip]
Which example(s)?

Well, space for the pointer only.

Alex

Alex Fraser wrote:
From the heuristics which I remember from many years ago,
the average "probes per search" for a good generic hash
function was about 1.5 . Which translates to about 1.5
disk reads per hash, if the hash table is in memory
and the actual data is on disk.

This depends upon your hash function and how disk is
accessed. If you use a minimalist approach, then
your hash function points to a logical file sector
on disk where the data record can be found, or
where pointers to overflow sectors can be found.
I have never considered rebuilding the hash table
on the fly when the number of records changed
substantilly, but will give it some thought.
I wonder what the tradeoffs are. Would you have
to relocate records on the disk? This would
seem to be counter-productive.

Don't get me wrong, please. I a proponent of hash
tables, but IFF you know what the heck you're doing
ahead of time, e.g. expected number of records
to set the table size.




--
"It is impossible to make anything foolproof
because fools are so ingenious"
- A. Bloch

Nick Landsberg wrote:
Try out my hashlib, on my site below, download section. It is
instrumented so you can tell the average probes per search, etc,
and handles automatic expansion.

--
Chuck F (cbfalconer (AT) yahoo (DOT) com) (cbfalconer (AT) worldnet (DOT) att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

CBFalconer wrote:

I've downloaded it Chuck, and looked at the code, but
work time prohibits me from doing a thorough test.
From what I can see of the code, it's first-class
stuff.

NPL


--
"It is impossible to make anything foolproof
because fools are so ingenious"
- A. Bloch

"Nick Landsberg" <SPAMhukolauTRAP (AT) SPAMworldnetTRAP (DOT) att.net> wrote

Obviously, this depends on the hash table loading. I think 1.5 is right for
an optimal hash function and 50% load (using a "closed" table, ie no
chaining).

Not with what I attempted to describe. Let me try to explain more fully.

Suppose you have a (good) hash function which produces 32- or 64-bit hash
values. After computing the hash value for the key of the record you are
(say) searching for, you must somehow reduce it to the size of the table (eg
using the modulus operator), and that is where you start your probe
sequence. But, and this is the main point, you don't throw away the original
hash value. Instead, you compare it to the hash values you cunningly stored
in the table (along with the record number). If the range of hash values is
much larger than the size of the table, then quite often you won't need to
read the records when keys don't match: even if they hash to the same slot,
the hash values will probably differ.

You can alternatively consider the idea of storing the hash value in the
table as as a cache. The property relied upon is that if the hash values of
two keys differ, then the keys must differ. By caching the hash value, you
have a cheaper way to prove inequality (and continue the probe sequence,
without examining the record).

[snip]
You can avoid the need to relocate records by using indirection (this
applies if you use a B-tree, too). Basically, you seperate the index (hash
table or B-tree) from the records themselves.

I read somewhere on the web about a hash table implementation which sought
to reduce the pain of rebuilding. Unfortunately, I don't remember how it
worked and I can't find it now, but I wonder if it could be applied to this
situation.

Alex

Alex Fraser wrote:
One such is my hashlib, available on the download section of my
page. It doesn't reduce, it eliminates.

--
Chuck F (cbfalconer (AT) yahoo (DOT) com) (cbfalconer (AT) worldnet (DOT) att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

"CBFalconer" <cbfalconer (AT) yahoo (DOT) com> wrote

The pain I referred to was time complexity: rebuilding the table by adding
each entry to a new hash table then discarding the old table (the obvious
algorithm, as used in hashlib) is O(n).

If there are a large number of inserts and deletes (balanced, so the number
of entries is constant in the long term) the table will typically become
cluttered with deleted entries, and performance will suffer unless the table
is (frequently) rebuilt.

If the number of entries is also large, this can result in a significant
proportion of the time being used for rebuilding. Even if the average
performance of operations is excellent, ie O(1), rebuilding will give some
probably undesirable "bumps" in performance. These are the problems
addressed by what I mentioned I read.

Alex

Alex Fraser wrote:
However there are savings available in rebuilding versus inserting.

Hashlib uses the same criterion, approximately 90% full, to trigger
rebuilding. However if deletions can be removed and reach a
different criterion, the table does not expand.

You would think so at first glance. While there are 'bumps' in the
access times, they are much smaller than one would expect
a-priori. At any rate, the system has built in instrumentation, so
you can measure all these things out of the box.

--
Chuck F (cbfalconer (AT) yahoo (DOT) com) (cbfalconer (AT) worldnet (DOT) att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!