Re: B-tree performance

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 13-09-01 11:38 , Peter Brooks wrote:
> On Sunday, 1 September 2013 10:05:27 UTC+2, Niklas Holsti  wrote:
>>  
>>
>> If for some reason you want to the keep the hash-table small, although
>> this leads to many collisions, I suppose you could organize the
>> colliding object sets into some kind of keyed containers, for example
>> B-trees, but then you should use the actual key to index these
>> containers, not the hash-value.
>>
> I'm using a tree structure to represent a sparse array because it
> makes inserts and deletes easier and quicker, and cleaner.

But insertion and deletion are simple and fast in the basic hash-table
structure, too, as long as the collision sets are small.

In the traditional hash-table structure, the collision sets are
implemented as unordered linked lists of objects. You can insert or
delete any list entry with a few link changes. If you adjust the size of
the hash table to keep the collision set size bounded by some constant,
insertion and deletions are O(1) on average.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .