From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Roland Orre Newsgroups: gmane.lisp.guile.user Subject: Re: Efficiency and flexibility of hash-tables Date: 10 Feb 2003 18:09:30 +0100 Organization: Royal Institute of Technology Sender: guile-user-bounces+guile-user=m.gmane.org@gnu.org Message-ID: <1044896969.1032.317.camel@localhost> References: <1044889242.1033.310.camel@localhost> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Trace: main.gmane.org 1044897726 3922 80.91.224.249 (10 Feb 2003 17:22:06 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Mon, 10 Feb 2003 17:22:06 +0000 (UTC) Cc: Greg Troxel Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 18iHd2-00010S-00 for ; Mon, 10 Feb 2003 18:22:00 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18iHd4-0005hO-01 for guile-user@m.gmane.org; Mon, 10 Feb 2003 12:22:02 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.10.13) id 18iHXp-0003uw-00 for guile-user@gnu.org; Mon, 10 Feb 2003 12:16:37 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.10.13) id 18iHWw-0003qO-00 for guile-user@gnu.org; Mon, 10 Feb 2003 12:15:43 -0500 Original-Received: from smtp0.nada.kth.se ([130.237.222.202] helo=smtp.nada.kth.se) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 18iHR5-0001jL-00 for guile-user@gnu.org; Mon, 10 Feb 2003 12:09:39 -0500 X-Authentication-Info: Sender authentication was Original-Received: from [192.168.1.92] (bari.bacon.su.se [130.237.152.231]) (authenticated bits=0) by smtp.nada.kth.se (8.12.1/8.12.1) with ESMTP id h1AH9RwV013886 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NO); Mon, 10 Feb 2003 18:09:33 +0100 (MET) Original-To: djurfeldt@nada.kth.se In-Reply-To: X-Mailer: Ximian Evolution 1.2.1 Original-cc: Joris van der Hoeven Original-cc: Andreas Rottmann Original-cc: guile-user@gnu.org X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: General Guile related discussions List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Xref: main.gmane.org gmane.lisp.guile.user:1624 X-Report-Spam: http://spam.gmane.org/gmane.lisp.guile.user:1624 On Mon, 2003-02-10 at 17:52, Mikael Djurfeldt wrote: > The idea of having an upper threshold comes from the idea of > maintaining the load factor of the hash table in a reasonable > interval. But the purpose of the load factor is to prevent to large > clusters forming in the same hash bucket. What about simply counting > the pairs in a bucket during insertion and rehashing when we reach a > threshold? Then no extra data needs to be stored in the table. (We > would need to globally serialize rehashing with an external mutex, > though.) The risk with this is that if the hash function in a specific situation is bad, not spreading enough, we may form clusters anyway. With a risk that we will reallocate hash tables much too often. > Another disadvantage is that the tables wouldn't shrink. Is this an > issue? For most of our applications it isn't because we will reallocate all hash tables after each run. In all my code over the years hash-remove! is very very rare. Best regards Rolan _______________________________________________ Guile-user mailing list Guile-user@gnu.org http://mail.gnu.org/mailman/listinfo/guile-user