Quick string to hash value routine

Previous topic - Next topic

MrTAToad

This calculates a hash value for a string :

Code (glbasic) Select
INLINE
#define min(a,b) (a<b ? a : b)
ENDINLINE

FUNCTION Hash%:text$
INLINE
long result,temp,counter;

result=0;
for (counter=0; counter<min(text_Str.len(),16); counter++)
{
result=(result<<4)+((char) text_Str[counter]);
temp=result & 0xF000;
if (temp)
{
result=result^(temp>>12);
}

result=(result & (temp^0xFFFF)) & 0xFFFF;

}

return result;
ENDINLINE
ENDFUNCTION


Test :

Code (glbasic) Select
DEBUG Hash("abcdefg")+"\n"
DEBUG Hash("Abcdefg")+"\n"


Produces values of 1085 and 1053

metzzo

Very useful for Hashmaps and things like that, thanks :)
That's no Bug, that's my project!

http://programming-with-design.at/

MrTAToad

Very simple way of mapping a string text to a value :

Code (glbasic) Select
GLOBAL TSMap$[]

FUNCTION CreateHash%:text$
INLINE
long result,temp,counter;

result=0;
for (counter=0; counter<min(text_Str.len(),16); counter++)
{
result=(result<<4)+((char) text_Str[counter]);
temp=result & 0xF000;
if (temp)
{
result=result^(temp>>12);
}

result=(result & (temp^0xFFFF)) & 0xFFFF;

}

return result;
ENDINLINE
ENDFUNCTION

FUNCTION AddMap_String%:ky$,value$
LOCAL hash%

hash%=CreateHash(ky$)
IF BOUNDS(TSMap$[],0)<hash%
REDIM TSMap$[hash%+1]
ENDIF
TSMap$[hash%]=value$
ENDFUNCTION

FUNCTION Return_StringValue$:ky$
LOCAL hash%

hash%=CreateHash(ky$)
IF BOUNDS(TSMap$[],0)<hash%
RETURN ""
ELSE
RETURN TSMap$[hash%]
ENDIF
ENDFUNCTION


Test :

Code (glbasic) Select
AddMap_String("UK","England")
DEBUG "Value : "+Return_StringValue$("UK")+"\n"


Of course, it would be best to increase TSMap$ by 1 for each AddMap and use a search function to find the correct hash value.

MrTAToad

Yes. normally I would define min as :

Code (glbasic) Select
#define min(a,b) ((a)<(b) ? (a) : (b))

But I was feeling a bit lazy at the time.

Good idea about the length check too.