Author Topic: Quick string to hash value routine  (Read 1753 times)

MrTAToad

  • Guest
Quick string to hash value routine
« on: 2010-May-28 »
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

Offline metzzo

  • Mr. Polyvector
  • ***
  • Posts: 140
  • Coolo ist cool!
    • View Profile
    • programming with design
Re: Quick string to hash value routine
« Reply #1 on: 2010-May-28 »
Very useful for Hashmaps and things like that, thanks :)
That's no Bug, that's my project!

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

MrTAToad

  • Guest
Re: Quick string to hash value routine
« Reply #2 on: 2010-May-30 »
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

  • Guest
Re: Quick string to hash value routine
« Reply #3 on: 2010-May-30 »
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.