Author: Stan Eisenstat
Subject: Re: [Cs323] Pruning
Date: Thursday, 29 Oct 2020, 18:00:51

    > Message Posted By: Unknown
    >
    > Say the hash table reaches 1024 entries with MAXBITS=10 and pruning is
    > enabled, and <= 512 entries survive the pruning algorithm. Should the new
    > hash table have capacity=512 or capacity=1024? More generally, does
    > pruning ever decrease the capacity of the string table?

A chained hash table does not have a capacity since the
chains can be arbitrarily long.

There should be 128 chains if the hash table has 1024
entries.  If the number of entries after pruning is less
than or equal to 512, then the number of chains should
be 64.

The general case is similar.

--Stan-