Hash function for a string

Question

We are currently dealing with hash function in my class  Our instructor asked us to a hash function on the internet to compare to the two we have used in our code   The first one   int HashTable  hash  string word        POST  the index of entry is returned         int sum   0          for  int k   0  k  lt  word length    k                sum   sum   int word k            return  sum   SIZE       Second   int HashTable  hash  string word       int seed   131      unsigned long hash   0     for int i   0  i  lt  word length    i               hash    hash   seed    word i           return hash   SIZE      Where SIZE is 501  The size of the hash table  and the input is coming from a text file of 20 000  words   I saw this question with a few code examples but wasn t exactly sure what to be looking for in a hash function  If I understand correctly  in my case  a hash takes an input  string  and does a math calculation to assign the string a number and inserts it in a table  This process is done to increase the speed of searching the list    If my logic is sound  does anyone have a good example or a resource showing a different hash function that involves a string  Or even the process of writing my own efficient hash function

User · Answer

Hash functions for algorithmic use have usually 2 goals, first they have to be fast, second they have to evenly distibute the values across the possible numbers. The hash function also required to give the all same number for the same input value.

if your values are strings, here are some examples for bad hash functions:

string[0] - the ASCII characters a-Z are way more often then others
string.lengh() - the most probable value is 1

Good hash functions tries to use every bit of the input while keeping the calculation time minimal. If you only need some hash code, try to multiply the bytes with prime numbers, and sum them.

User · Answer

Java s String implements hashCode like this   public int hashCode    Returns a hash code for this string  The hash code for a String object is computed as       s 0  31  n-1    s 1  31  n-2          s n-1   using int arithmetic  where s i  is the ith character of the string  n is the length of the string  and   indicates exponentiation   The hash value of the empty string is zero      So something like this   int HashTable  hash  string word        int result   0      for size t i   0  i  lt  word length      i            result    word i    pow 31  i             return result

User · Answer

Use boost  hash   include  lt boost functional hash hpp gt         std  string a    ABCDE   size t b   boost  hash value a

User · Answer

-- The way to go these days --  Use SipHash  For your own protection   -- Old and Dangerous --  unsigned int RSHash const std  string amp  str        unsigned int b      378551      unsigned int a      63689      unsigned int hash   0       for std  size t i   0  i  lt  str length    i                  hash   hash   a   str i           a      a   b             return  hash  amp  0x7FFFFFFF        unsigned int JSHash const std  string amp  str           unsigned int hash   1315423911         for std  size t i   0  i  lt  str length    i                      hash      hash  lt  lt  5    str i     hash  gt  gt  2                   return  hash  amp  0x7FFFFFFF        Ask google for  general purpose hash function

User · Answer

First  it usually does not matter that much in practice  Most hash functions are  good enough    But if you really care  you should know that it is a research subject by itself  There are thousand of papers about that  You can still get a PhD today by studying  amp  designing hashing algorithms   Your second hash function might be slightly better  because it probably should separate the string  ab  from the string  ba   On the other hand  it is probably less quick than the first hash function  It may  or may not  be relevant for your application   I ll guess that hash functions used for genome strings are quite different than those used to hash family names in telephone databases  Perhaps even some string hash functions are better suited for German  than for English or French words   Many software libraries give you good enough hash functions  e g  Qt has qhash  and C  11 has std  hash in  lt functional gt   Glib has several hash functions in C  and POCO has some hash function   I quite often have hashing functions involving primes  see B  zout s identity  and xor  like e g    define A 54059    a prime     define B 76963    another prime     define C 86969    yet another prime     define FIRSTH 37    also prime    unsigned hash str const char  s       unsigned h   FIRSTH     while   s         h    h   A     s 0    B        s            return h     or return h   C      But I don t claim to be an hash expert  Of course  the values of A  B  C  FIRSTH should preferably be primes  but you could have chosen other prime numbers   Look at some MD5 implementation to get a feeling of what hash functions can be   Most good books on algorithmics have at least a whole chapter dedicated to hashing  Start with wikipages on hash function  amp  hash table

[c++] Hash function for a string

Examples related to c++

Examples related to string

Examples related to hash

Examples related to hashtable