Author Topic: Quick string to hash value routine  (Read 1643 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.