patterncMinor
Simple string hashing algorithm implementation
Viewed 0 times
simplealgorithmhashingimplementationstring
Problem
I thought of a simple way to hash a string. By taking the ASCII decimal value of each character, multiplying it by 10, and adding all of the values computed together for each character in a string. Is there a name for this algorithm? I highly doubt I was the first one to think of this.
Compiled with
Compiled with
gcc -Wall -Wextra -Werror -std=c99 string.c -o string#include
#include
size_t stringLength(const char* source)
{
if(source == NULL) { return 0; }
size_t length = 0;
while(*source != '\0') {
length++;
source++;
}
return length;
}
static size_t getHash(const char* source)
{
size_t length = stringLength(source);
size_t hash = 0;
for(size_t i = 0; i %zu\n", source, (hash % TABLE_SIZE));
}
return 0;
}Solution
-
Don't check for NULL pointer argument. The function should expect a valid null-terminated string, it's responsibility of the caller to ensure correct argument.
-
You don't need to know the string length. Check for null-terminator right in the hash loop.
-
It's possible to write it shorter and cleaner.
-
It's not quite clear what do you mean by "ASCII decimal value". Are you referring to this expression in your code:
-
Are you aware that for the same expression
-
If you are looking for a short and simple hash function then perhaps either of these might work for you.
Don't check for NULL pointer argument. The function should expect a valid null-terminated string, it's responsibility of the caller to ensure correct argument.
-
You don't need to know the string length. Check for null-terminator right in the hash loop.
-
It's possible to write it shorter and cleaner.
static size_t getHash(const char* cp)
{
size_t hash = 0;
while (*cp)
hash = (hash * 10) + *cp++ - '0';
return hash;
}-
It's not quite clear what do you mean by "ASCII decimal value". Are you referring to this expression in your code:
c - '0'? Well, suppose at some moment c == 'Z', so this expression amounts to 'Z' - '0'. If we substitute ASCII codes for these characters, then we get 90 - 48, this is equal to 42 which is ASCII code for '' character. So you have transformed 'Z' into ''. Is this somehow supposed to improve the quality of your hash function? I'm in doubt.-
Are you aware that for the same expression
c - '0' for a number of possible c values (e.g. ' ', '!', and anything with ASCII value less than 48) you will get a negative result and when you add it to the hash it will be sign-extended and converted to a huge unsigned value, something like 0xffffffffffffffxx?-
If you are looking for a short and simple hash function then perhaps either of these might work for you.
/* D. J. Bernstein hash function */
static size_t djb_hash(const char* cp)
{
size_t hash = 5381;
while (*cp)
hash = 33 * hash ^ (unsigned char) *cp++;
return hash;
}
/* Fowler/Noll/Vo (FNV) hash function, variant 1a */
static size_t fnv1a_hash(const char* cp)
{
size_t hash = 0x811c9dc5;
while (*cp) {
hash ^= (unsigned char) *cp++;
hash *= 0x01000193;
}
return hash;
}Code Snippets
static size_t getHash(const char* cp)
{
size_t hash = 0;
while (*cp)
hash = (hash * 10) + *cp++ - '0';
return hash;
}/* D. J. Bernstein hash function */
static size_t djb_hash(const char* cp)
{
size_t hash = 5381;
while (*cp)
hash = 33 * hash ^ (unsigned char) *cp++;
return hash;
}
/* Fowler/Noll/Vo (FNV) hash function, variant 1a */
static size_t fnv1a_hash(const char* cp)
{
size_t hash = 0x811c9dc5;
while (*cp) {
hash ^= (unsigned char) *cp++;
hash *= 0x01000193;
}
return hash;
}Context
StackExchange Code Review Q#85556, answer score: 7
Revisions (0)
No revisions yet.