From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "A. Soare" Newsgroups: gmane.emacs.devel Subject: Re: van Emde Boas hash. Date: Mon, 23 Nov 2009 15:04:41 +0100 (CET) Message-ID: <24616604.12772711258985081474.JavaMail.www@wwinf4633> Reply-To: alinsoar@voila.fr NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1258985131 18725 80.91.229.12 (23 Nov 2009 14:05:31 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 23 Nov 2009 14:05:31 +0000 (UTC) Cc: "Emacs Dev \[emacs-devel\]" To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Nov 23 15:05:23 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 1NCZXd-0002Bh-Pc for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 15:05:22 +0100 Original-Received: from localhost ([127.0.0.1]:33673 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCZXd-0007SZ-7T for ged-emacs-devel@m.gmane.org; Mon, 23 Nov 2009 09:05:21 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NCZX7-0006sB-DU for emacs-devel@gnu.org; Mon, 23 Nov 2009 09:04:49 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NCZX2-0006mp-NE for emacs-devel@gnu.org; Mon, 23 Nov 2009 09:04:48 -0500 Original-Received: from [199.232.76.173] (port=52569 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NCZX2-0006mV-DP for emacs-devel@gnu.org; Mon, 23 Nov 2009 09:04:44 -0500 Original-Received: from smtp3.voila.fr ([193.252.22.173]:55541 helo=smtp1.voila.fr) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NCZX1-0005jW-RB for emacs-devel@gnu.org; Mon, 23 Nov 2009 09:04:44 -0500 Original-Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf4917.voila.fr (SMTP Server) with ESMTP id B0BBC700008A; Mon, 23 Nov 2009 15:04:41 +0100 (CET) Original-Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf4917.voila.fr (SMTP Server) with ESMTP id 9FD09700008C; Mon, 23 Nov 2009 15:04:41 +0100 (CET) Original-Received: from wwinf4633 (wwinf4633 [10.232.13.107]) by mwinf4917.voila.fr (SMTP Server) with ESMTP id 74980700008A; Mon, 23 Nov 2009 15:04:41 +0100 (CET) X-ME-UUID: 20091123140441477.74980700008A@mwinf4917.voila.fr X-Originating-IP: [91.201.80.240] X-Wum-Nature: EMAIL-NATURE X-WUM-FROM: |~| X-WUM-TO: |~| X-WUM-CC: |~| X-WUM-REPLYTO: |~| 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:117579 Archived-At: > > What algorithm uses emacs for hashing the obarrays of symbols ? >=20 > Read the source: C-h f intern RET then click on top right to get to the > source code, ... >=20 > It's a hash table with simple haqshing into buckets that contain linked > lists of symbols. 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 =3D hash_string (sym) ;; bucket is a vector. obarray is a vector of many buckets bucket =3D 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, th= e algorithm does not require constant time for every search. Hashing using van Emde Boas requires in the worst case a time of log_2(N), = where N is the length of the largest symbol name in obarray. Alin. ____________________________________________________ Derniers jours pour remporter le s=C3=A9jour au Maroc sur http://www.lesrev= oila.fr/=20