Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up hash_search?)

From	Chet Ramey <chet.ramey@case.edu>
Newsgroups	gnu.bash.bug
Subject	Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up hash_search?)
Date	2020-04-20 11:57 -0400
Organization	ITS, Case Western Reserve University
Message-ID	<mailman.803.1587398263.3066.bug-bash@gnu.org> (permalink)
References	<CALv3B7aiTbhpyUL17Eg5prH39EgMP8uSDdD554OdND3LFETAQg@mail.gmail.com> <CAFLRLk8ydO6ev8wRcJ35kzzN3Yt2_9sjsc6L+C0CC6dCxud_NA@mail.gmail.com> <3e13ada9-01b6-da2e-26d4-2f7b5799edb1@case.edu>

Show all headers | View raw

On 4/19/20 3:51 PM, Koichi Murase wrote:

> 
> The associative arrays in `hashlib.c' are implemented by hash tables
> as is clear from its name.  The main lookup of hash table algorithm is
> done by the following line
> 
>   bucket = HASH_BUCKET (string, table, hv);
> 
> but not by the subsequent linear search.  The linear search is just a
> workaround for the collision of hashes.  As far as the load factor of
> the hash table is maintained properly, the linear search is O(1)
> because the length of the list is O(1).
> 
> 2020-04-19 23:54 George Jones <fooologist@gmail.com>:
>> This slows down (order N?) new inserts when the number of entries
>> gets large.
> 
> I looked into `hashlib.c' and found that rehashing is actually not
> implemented.  I just added a function to perform rehashing, and
> the performance has been improved.

Thanks for the patch. This will be in the next devel branch push.

Chet

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
		 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://tiswww.cwru.edu/~chet/

Back to gnu.bash.bug | Previous | Next | Find similar

Thread

Re: [PATCH] Implement rehashing for associative arrays (Re: speeding up hash_search?) Chet Ramey <chet.ramey@case.edu> - 2020-04-20 11:57 -0400

csiph-web