On Tue, Aug 24, 2010 at 2:44 PM, Paul Gilmartin <paulgboul...@aim.com> wrote:
> Is there a hashing technique that works well without a priori > knowledge of the list size? No. The purpose of the hash is to distribute the keys over the entire table, so you need to know the output range of the hash function. The original poster mentioned that often the list is small, but sometimes it is very large. You could start with a hash table that handles all the small cases. When it fills, you allocate one 4 or 8 times as large and rehash the existing entries from the small table (the rehash can be avoided when you can tell early that you're getting a large list). I understood from the first post that the object also has a payload, but the discussion about sparse bitmap suggests there isn't. If that's the case, rather than building a chain in each hash table entry, you could just store the key in the entry and rehash on collision (takes some time on collision, but allows a table twice as big, so collisions are less likely). | Rob
