On Tue, Sep 8, 2015 at 11:59 PM, John Cowan <xxxxxx@mercury.ccil.org> wrote:

Alex Shinn scripsit:

> > > There's no discussion of the trade-offs involved in perfect
> > > hashes. The requirements seem to forbid them by requiring
> > > amortized O(1) on mutation, but if that were relaxed we could
> > > have guaranteed (non-amortized) O(1) on access. It's probably
> > > better to leave this to a separate data-structure to support the
> > > frequent update case, but I thought I'd mention this.
> >
> > Unpack this, please.

Basically, there's no free lunch with hash tables.

They are probabilistic data structures which only give

you average case times. This is important because

there are algorithms where it may look like a hash table

would speed things up for you, but that's cheating.

One example is 2-sum - given an array of integers, find if

there is a pair of integers which add up to some constant c.

A simple solution would be to build a hash table holding

each number, then for each x in the array, check if c - x is

in the hash table. This is linear time only in the average

case. The proper solution is to first sort the array in n log n

time, then scan from either end as in the inner loop of the

classic solution to 3-sum. O(n log n) worst-case.

But wait, you may ask, what about perfect hashes? These

can guarantee constant time lookups in worst-case. The

problem is you need time to build the table, and there are

no good bounds on this. Two dynamic perfect hash algorithms

are Dietzfelbinger et al's algorithm [1] and the Cuckoo hash [2].

Both of these have additional restrictions on the load factor

in order to get even _expected_ amortized constant time

insertions. This conflicts with implementation extensions to

specify the load factor explicitly.

So if we want to allow dynamic perfect hashing anyway,

then we would need to relax the times to:

O(1) expected amortized time for lookup

unspecified time for insertion and deletion

[1] http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf

[2] http://cs.nyu.edu/courses/fall05/G22.3520-001/cuckoo-jour.pdf

Alex