Re: Grace and Maps (was Re: Development process in the Ada community)

[Ole-Hjalmar Kristensen <oleh@vlinux.voxelvision.no>]

Darren New <dnew@san.rr.com> writes:

> Ole-Hjalmar Kristensen wrote:
> > You're right, you cannot in general guarantee it. But if you use hash
> > functions which on average change half the bits as a result of a
> > single bit change in the input, you can rest assured that it will not
> > happen in practice.
> 
> I haven't done any safety-critical work, but is this how it's really
> done? "It's very unlikely this airplane will crash into that nuclear
> plant, unless 20 items all hash to the same value"?  :-)  No,
> seriously...

I agree, not the thing you would want in a hard real time
safety-critical system. Buf for soft real time, non saftey critical
systems it's good enough. And it really can make a difference in
throughput in for instance applications like relational algebra
processing.

> 
> In any case, the hashes still have two problems:
> 
> 1) You *could* be hosed this way, so while they may be faster, they're
> still not deterministic, while a red-black tree has a strictly bounded
> upper limit on the number of operations (given a particular number of
> nodes) which is much lower than that of a hash table. In other words,
> the worst-case for a hashtable is still O(N), which if you need realtime
> and safety-critical, you have to take it into account.
> 

Agree, although even O(N) might be good enough, depending on you
application. Also, if the probability of O(N) behaviour is
sufficiently low, it may be way below the probability of a system
failure caused by other errors.

> 2) You need to be able to hash the value. A red-black tree needs only an
> ordering operator (like "<"), not something that gropes the insides of
> an object like a hash needs to. If you want to ensure you have a
> particularly good hash, then you are going to have trouble with the
> strong typing in Ada, yes? That is, every type of hash table I create is
> going to work only if I implement a hash appropriate to the key type,
> and that'll have to get reimplemented (to some extent at least) for
> every type. On the other hand, most of the built-in types and metatypes
> ("record", "array", etc) already have ordering operators or rules on how
> to deduce them from the components.
> 

Yes, although the reimplementation usually just consists of calling the
same hash functions with different parameters. After all, we don't
really care what we are hashing, all we need to know is the location
and size of the key, so one good hash function is really all you need.

> -- 
> Darren New 
> San Diego, CA, USA (PST). Cryptokeys on demand.
>    The 90/10 rule of toothpaste: the last 10% of 
>          the tube lasts as long as the first 90%.