LinuxQuestions.org
LinuxAnswers - the LQ Linux tutorial section.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

View Poll Results: Do you find this thread useful?
Yes 1 16.67%
No 5 83.33%
Voters: 6. You may not vote on this poll

Reply
 
Search this Thread
Old 11-09-2010, 12:41 PM   #1
Sanmayce
LQ Newbie
 
Registered: Jul 2010
Location: Sofia
Posts: 10

Rep: Reputation: 2
Fastest hash function


Hi,
I am interested in fast hashers(targeted on alpha strings to be more specific). Here is one of my two hash-of-choice functions:

Code:
UINT FNV1A_Hash_WHIZ(const char *str, SIZE_T wrdlen)
{
	const UINT PRIME = 1607;

	UINT hash32 = 2166136261;
	const char *p = str;

	for(; wrdlen >= sizeof(DWORD); wrdlen -= sizeof(DWORD), p += sizeof(DWORD)) {
		hash32 = (hash32 ^ *(DWORD *)p) * PRIME;
	}
	if (wrdlen & sizeof(WORD)) {
		hash32 = (hash32 ^ *(WORD*)p) * PRIME;
		p += sizeof(WORD);
	}
	if (wrdlen & 1) 
		hash32 = (hash32 ^ *p) * PRIME;

	return hash32 ^ (hash32 >> 16);
}
The speed/collision performance on Intel Atom N450 1.66GHz:

Code:
C:\Test\hash>dir

11/07/2010  06:47 AM            84,992 hash.exe
10/27/2010  03:48 PM       146,973,879 wikipedia-en-html.tar.wrd

C:\Test\hash>hash wikipedia-en-html.tar.wrd
12561874 lines read
33554432 elements in the table (25 bits)
    Sixtinsensitive+:   16153226  16031348  16039844  16048697  16026421|  16026421 [2251734] !FASTEST!
Hash_Sixtinsensitive:   16501364  16504662  16506868  16509768  16515127|  16501364 [2139242]
                Whiz:   16081498  16080691  16080162  16079881  16085656|  16079881 [2189360] !Second-to-FASTEST! 
           Bernstein:   16222890  16208653  16195534  16205258  16207576|  16195534 [2074237]
                 K&R:   16181141  16153089  16147347  16144145  16144279|  16144145 [2083145]
        x17 unrolled:   16196693  16200720  16203124  16195429  16196980|  16195429 [2410605]
              x65599:   17213371  17215886  17211092  17225140  17218658|  17211092 [2102893]
              FNV-1a:   17648084  17649994  17644643  17654437  17650937|  17644643 [2081195]
           Sedgewick:   17715483  17711538  17706339  17709057  17711857|  17706339 [2080640]
          Weinberger:   19795514  19798517  19792040  19783954  19796407|  19783954 [3541181]
         Paul Larson:   16904068  16909317  16906315  16905215  16899096|  16899096 [2080111]
          Paul Hsieh:   16731679  16720594  16932967  16731003  16725432|  16720594 [2180206]
         One At Time:   18317093  18329453  18319193  18325990  18318877|  18317093 [2087861]
             lookup3:   16591932  16600364  16593657  16594726  16605181|  16591932 [2084889]
        Arash Partow:   16790714  16782529  16783414  16782986  16791156|  16782529 [2084572]
              CRC-32:   16878539  16872606  16866719  16876415  16860548|  16860548 [2075088]
         Ramakrishna:   16437073  16449160  16438019  16442447  16452696|  16437073 [2093253]
            Fletcher:   74995725  74991965  74983105  75027126  75020605|  74983105 [9063797]
             Murmur2:   16742975  16730183  16736149  16741761  16735690|  16730183 [2081476]
              Hanson:   17286767  17288260  17273143  17280187  17371322|  17273143 [2129832]
      Novak unrolled:   60320056  60322432  60315223  60308709  60325221|  60308709 [6318611]
                SBox:   17677039  17685532  17686854  17681897  17680986|  17677039 [2084018]
           MaPrime2c:   19286056  19296348  19307574  19294326  19295151|  19286056 [2084467]

C:\Test\hash>
Please, if anybody knows faster one let drop a link here.
The second function is called 'Sixtinsensitive' with source code at link below.
For more info:
http://www.strchr.com/hash_functions
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash function in C EnTe Programming 7 11-09-2010 12:48 PM
Perl hash function from logfile eentonig Programming 7 08-02-2008 05:57 AM
hash function in kernel vishalbutte Programming 11 02-26-2006 02:30 AM
Using hash value as key for other hash in Perl scuzzman Programming 6 02-14-2006 05:08 PM
Hash-Function (string to int) Hady Programming 5 04-05-2004 01:53 AM


All times are GMT -5. The time now is 10:29 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration