From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 1215 invoked by alias); 19 Mar 2010 23:06:26 -0000 Received: (qmail 1158 invoked by uid 22791); 19 Mar 2010 23:06:24 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from fencepost.gnu.org (HELO fencepost.gnu.org) (140.186.70.10) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 19 Mar 2010 23:06:19 +0000 Received: from mx10.gnu.org ([199.232.76.166]:45141) by fencepost.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1NslGj-00026O-Uq for gcc@gnu.org; Fri, 19 Mar 2010 19:06:18 -0400 Received: from eggs.gnu.org ([140.186.70.92]:50064) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1NslGj-0002XA-Md for gcc@gnu.org; Fri, 19 Mar 2010 19:06:17 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1NslGh-0000G6-Vg for gcc@gnu.org; Fri, 19 Mar 2010 19:06:17 -0400 Received: from rock.gnat.com ([205.232.38.15]:51478) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1NslGh-0000Fy-Su for gcc@gnu.org; Fri, 19 Mar 2010 19:06:15 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by filtered-rock.gnat.com (Postfix) with ESMTP id 163E72BAB8C; Fri, 19 Mar 2010 19:06:15 -0400 (EDT) Received: from rock.gnat.com ([127.0.0.1]) by localhost (rock.gnat.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id cJZC4V6dzhyh; Fri, 19 Mar 2010 19:06:15 -0400 (EDT) Received: from [127.0.0.1] (nile.gnat.com [205.232.38.5]) by rock.gnat.com (Postfix) with ESMTP id D00772BAB60; Fri, 19 Mar 2010 19:06:13 -0400 (EDT) Message-ID: <4BA4035E.7070807@adacore.com> Date: Fri, 19 Mar 2010 23:09:00 -0000 From: Robert Dewar User-Agent: Thunderbird 2.0.0.24 (Windows/20100228) MIME-Version: 1.0 To: Dave Korn CC: Jae Hyuk Kwak , Michael Meissner , gcc@gnu.org Subject: Re: Hash Function for "switch statement" References: <8ac33cd71003141343g7ae78185s378fd52205e2deb1@mail.gmail.com> <20100317200410.GA13807@hungry-tiger.westford.ibm.com> <8ac33cd71003172222i3be31fbah209f49bd83dfa9b3@mail.gmail.com> <20100318151753.GA4065@hungry-tiger.westford.ibm.com> <8ac33cd71003181710k263f6a8do6abd49d80e5213f8@mail.gmail.com> <20100319165443.GA9993@hungry-tiger.westford.ibm.com> <8ac33cd71003191358o15ad8e72tb14dc71adfea2066@mail.gmail.com> <4BA3E8EB.3070100@adacore.com> <4BA3FD9F.3080904@gmail.com> In-Reply-To: <4BA3FD9F.3080904@gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 3) Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2010-03/txt/msg00323.txt.bz2 Dave Korn wrote: > Please, nobody bring up the old saw that prime numbers are a good choice for > hashtable sizes. They aren't, they're a crude workaround for a poor hash > function. Well on a machine with a fast modulus operation, the crude workaround is often the most efficient algorithm in practice. >> One thing to realize is that hashing only has good average performance. >> So your O(N) is talking about average case performance, whereas the >> O(NlogN) for a tree search is worst case. That's comparing apples and >> oranges. It is worrisome to have the possibility of really bad >> performance for a particular bad luck case. > > That's not how minimal perfect hashing works, which was one of the main > suggestions. Right, in the case where you can do minimal perfect hashing, of course the consideration of average case performance does not apply. > > cheers, > DaveK