From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: van Emde Boas hash. Date: Mon, 23 Nov 2009 11:43:25 -0500 Message-ID: References: <24616604.12772711258985081474.JavaMail.www@wwinf4633> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1258994708 22683 80.91.229.12 (23 Nov 2009 16:45:08 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 23 Nov 2009 16:45:08 +0000 (UTC) Cc: "Emacs Dev \[emacs-devel\]" To: alinsoar@voila.fr Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Nov 23 17:45:01 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NCc27-0002Jg-RF for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 17:45:00 +0100 Original-Received: from localhost ([127.0.0.1]:54892 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCc27-000412-E0 for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 11:44:59 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NCc0i-0002Hq-BT for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:43:32 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NCc0d-0002Bk-CO for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:43:31 -0500 Original-Received: from [199.232.76.173] (port=39217 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCc0d-0002BC-6j for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:43:27 -0500 Original-Received: from ironport2-out.teksavvy.com ([206.248.154.183]:20029 helo=ironport2-out.pppoe.ca) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NCc0c-00007W-SG for emacs-devel@gnu.org; Mon, 23 Nov 2009 11:43:26 -0500 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqsEAGNKCkvO+IIa/2dsb2JhbACBTdVAhDwEigI X-IronPort-AV: E=Sophos;i="4.47,273,1257138000"; d="scan'208";a="49856167" Original-Received: from 206-248-130-26.dsl.teksavvy.com (HELO pastel.home) ([206.248.130.26]) by ironport2-out.pppoe.ca with ESMTP; 23 Nov 2009 11:43:25 -0500 Original-Received: by pastel.home (Postfix, from userid 20848) id 8472280E5; Mon, 23 Nov 2009 11:43:25 -0500 (EST) In-Reply-To: <24616604.12772711258985081474.JavaMail.www@wwinf4633> (A. Soare's message of "Mon, 23 Nov 2009 15:04:41 +0100 (CET)") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1.50 (gnu/linux) X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:117594 Archived-At: > As far as I understand, the algorthm is so: > oblookup ( obarray, sym ) > ;; hash is an integer, the index of a bucket that may contain sym > hash = hash_string (sym) > ;; bucket is a vector. obarray is a vector of many buckets > bucket = obarray [hash] > ;; search sym in its bucket using a naive search > FOR every symbol S in bucket, check whether S has the same name > as sym. If so, return S. If no symbol matches, returns the hash. > Even if it is very unlikely that we can find many symbols into > a bucket, the algorithm does not require constant time for > every search. Yes, it's a very simple hashing algorithm. I'm sure we can come up with something more efficient. Then again, I haven't seen any indication that this is a performance problem. Stefan