From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 border1.nntp.dca3.giganews.com!border2.nntp.dca3.giganews.com!border4.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!nx01.iad01.newshosting.com!newshosting.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: B-tree performance
Date: Mon, 02 Sep 2013 07:28:57 +0300
Organization: Tidorum Ltd
Message-ID: <b8iig8F6irU1@mid.individual.net>
References: <9fc26b8a-7a5c-4941-81cb-8f0e9c17a660@googlegroups.com>
 <b8fvorFdlvfU1@mid.individual.net>
 <2383e534-646c-4500-ad05-40caf9460c35@googlegroups.com>
 <b8gaq8FfqgkU1@mid.individual.net>
 <a5924091-ecc9-4d11-8bb5-30d84204cb15@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: individual.net B1cdUmBnwc0YRwuBNoufSAA90ntxq2501U68dEjsRUK8oeh6Qv
Cancel-Lock: sha1:vgbxzGFphX+yk4L66LaUqsAJLLI=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6;
 rv:17.0) Gecko/20130801 Thunderbird/17.0.8
In-Reply-To: <a5924091-ecc9-4d11-8bb5-30d84204cb15@googlegroups.com>
X-Original-Bytes: 2229
Xref: number.nntp.dca.giganews.com comp.lang.ada:183256
Date: 2013-09-02T07:28:57+03:00
List-Id: <comp.lang.ada>

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
      .      @       .