ELFhash algorithm is a hash function who works very well with great string and tiny string.
The source code is as follows:
unsigned int ELFhash(char *str)
The time complexity is
O(n) because of the loop of source string has n characters.
While the space complexity is
(gdb) b 5
We set a breakpoint at the beginning of function
main. There is nothing to do at this line, so we let it go.
At this line, we will input
abcdefghijkl as the string to be hashed.
When we reached line 8, enter the function.
(gdb) p str
At the end of the first loop, we got str
abcdefghijkl, and hash became
(gdb) p hash
After the second loop,
0x00000061 will be moved 4 bits to the left. So it’s
For the mixture of the first 7 number, it’s simply moving to the left with 4 bits and an addition.
At the 7th times, 6 is moved to the first bit of the hash. So if we continue the operations, it will be removed. To avoid this, the algorithm provides a serial of operations to guarantee the mixture between every bit near. For the moment,
0 if(( x=hash & 0xf0000000 ) != 0)
After these operations, the high 4 bits at the first bit is cleared to be 0. And the operation exclusive OR (^) will keep the bits from the second to the last second with
789ab. For x, it’s the high 4 bits of the first character. As the similarity between exclusive OR and the addition, it’s the same operation as the code
hash=(hash<<4)+*str. But it’s a looped one. So in the end, the hash became,
Obviously, the following characters will be handled as the seventh bit (“g” for the string), and it can be a ring of addition while a new character added.
I’m waiting for a proof of the homogeneity.