Hash Function Speed Post: 302364252

Sponsored Content

Top Forums Programming Hash Function Speed Post 302364252 by jim mcnamara on Thursday 22nd of October 2009 11:54:47 AM

10-22-2009

Registered User

As to hash improvement in general - test avalanche/distribution for your data sets on these:

Code:

// XOR-Bernstein hash

unsigned xor_b_hash ( const void *key, 
                      const int len,
                      const unsigned tablesize )
{
  const unsigned char *p = (const unsigned char *)key;
  unsigned hval = 0;
  int i=0;

  for ( i = 0; i < len; i++, p++ )
    hval = 33 * hval ^ *p;

  return hval % tablesize;
}

// fowler/nol/vo hash

unsigned fnv_hash ( const void *key, 
                    const int len,
                    const unsigned tablesize )
{
  const unsigned char *p = (const unsigned char *)key;
  unsigned hval = 2166136261U;
  int i=0;

  for ( i = 0; i < len; i++, p++ )
    hval = ( hval * 16777619 ) ^ *p;

  return hval % tablesize;
}

OP's additive hash fails to treat permutations, i.e., “xyz”, “zyx”, and “xzy” all result in the same hash value.

And if the original hash is "slow", then so will these be. Did you try instrumtenting your code, or using a profiler? ...before you decided the hash algorithm was the bottleneck.

jim mcnamara

View Public Profile for jim mcnamara

Find all posts by jim mcnamara

9 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

Awk Hash Function.

I have a file with a format of A,2 B,2 G,3 A,2 A,3 A,2 D,7 A,2 E,2 A,2 I need to create a sum of each alphabet with the numbers assigned to it using awk.

2. Shell Programming and Scripting

Print Entire hash list (hash of hashes)

I have a script with dynamic hash of hashes , and I want to print the entire hash (with all other hashes). Itried to do it recursively by checking if the current key is a hash and if yes call the current function again with refference to the sub hash. Most of the printing seems to be OK but in...

3. Filesystems, Disks and Memory

data from blktrace: read speed V.S. write speed

I analysed disk performance with blktrace and get some data: read: 8,3 4 2141 2.882115217 3342 Q R 195732187 + 32 8,3 4 2142 2.882116411 3342 G R 195732187 + 32 8,3 4 2144 2.882117647 3342 I R 195732187 + 32 8,3 4 2145 ...

4. Shell Programming and Scripting

Assigning a hash to another hash key

Hello, I have a hash in hsh. I need to assign it to another hash globalHsh. I think the below statement does not work $globalHsh{$id} = %hsh; What is the right way to assign it? Thanks

5. Shell Programming and Scripting

Perl Hash:Can not keep hash data in the same order that it was inserted

Can Someone explain me why even using Tie::IxHash I can not get the output data in the same order that it was inserted? See code below. #!/usr/bin/perl use warnings; use Tie::IxHash; use strict; tie (my %programs, "Tie::IxHash"); while (my $line = <DATA>) { chomp $line; my(...

6. Shell Programming and Scripting

perl hash - using a range as a hash key.

Hi, In Perl, is it possible to use a range of numbers with '..' as a key in a hash? Something in like: %hash = ( '768..1536' => '1G', '1537..2560' => '2G' ); That is, the range operation is evaluated, and all members of the range are...

7. Shell Programming and Scripting

Compare values of hashes of hash for n number of hash in perl without sorting.

Hi, I have an hashes of hash, where hash is dynamic, it can be n number of hash. i need to compare data_count values of all . my %result ( $abc => { 'data_count' => '10', 'ID' => 'ABC122', } $def => { 'data_count' => '20', 'ID' => 'defASe', ...

8. Shell Programming and Scripting

Dynamically parse BibTeX and create hash of hash

Hello gurus, Iam trying to parse following BibTex file (bibliography.bib): @book{Lee2000a, abstract = {Abstract goes here}, author = {Lee, Wenke and Stolfo, Salvatore J}, title = {{Data mining approaches for intrusion detection}}, year = {2000} } @article{Forrest1996, abstract =...

9. Shell Programming and Scripting

Need to print hash of hash in table format

Hi, I have a hash of hash where it has name, activities and count i have data like this - $result->{$name}->{$activities} = $value; content of that are - name - robert tom cat peter activities - running, eating, sleeping , drinking, work i need to print output as below ...

LEARN ABOUT DEBIAN

hash::case::upper

Hash::Case::Upper(3pm)					User Contributed Perl Documentation				    Hash::Case::Upper(3pm)

NAME

       Hash::Case::Upper - native hash with enforced lower cased keys

INHERITANCE

	Hash::Case::Upper
	  is a Hash::Case
	  is a Tie::StdHash

SYNOPSIS

	use Hash::Case::Upper;
	tie my(%uchash), 'Hash::Case::Upper';
	$uchash{StraNGeKeY} = 3;
	print keys %uchash;  # STRANGEKEY

DESCRIPTION

       Hash::Case::Upper extends Hash::Case, which lets you play various trics with hash keys. In this implementation, the fake hash is case
       insensitive and the keys stored in upper-case.

METHODS

   Constructors
       $obj->addHashData(HASH)
	   See "Constructors" in Hash::Case

       $obj->addPairs(PAIRS)
	   See "Constructors" in Hash::Case

       $obj->setHash(HASH)
	   See "Constructors" in Hash::Case

       tie(HASH, 'Hash::Case::Upper', [VALUES,] OPTIONS)
	   Define HASH to have only upper cased keys.  The hash is initialized with the VALUES, specified as ref-array or ref-hash.  Currently,
	   there are no OPTIONS defined.

SEE ALSO

       This module is part of Hash-Case distribution version 1.02, built on March 09, 2012. Website: http://perl.overmeer.net/hash-case/

LICENSE

       Copyrights 2002-2003,2007-2012 by Mark Overmeer. For other contributors see ChangeLog.

       This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.  See
       http://www.perl.com/perl/misc/Artistic.html

perl v5.14.2							    2012-03-09						    Hash::Case::Upper(3pm)