Hash Table - user data for sprites etc

Author

Message

Hodgey

14

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 22nd Mar 2013 02:26 Edited at: 24th Mar 2013 12:10

Link

In the past, a couple of you have asked for user data which can be associated to sprite numbers which should save you the trouble of having to search for the matching sprite in your arrays and then accessing its data. Currently, AppGameKit doesn't have a direct solution for this so I've whipped up a Hash Table for you guys to store your sprite numbers along with associated user data.

For those who don't know what Hash Tables/Sets are - wiki.

How it works
In a nutshell, you give add an entry into the Hash Table by providing a unique key (such as a sprite number) along with user data. The Hash Table will place it into its internal array based in the key. Insertion should be very quick with expected time of O(1) - constant. Worst case it'll have to resize which involves copying the entries into the temporary array, resize the main array and then rehashing (not exactly the same as copying) the entries back into the main array. This isn't done very often however.

How to use it
AddIntegerToHashSet(key,usr) - this will add a key (ie sprite number) into the hashset associated with your user data (usr). In most cases, this will probably be the array index of your own array, of the sprite you've just inserted into the hash table.

e.g AddSpriteToInteger(Sprites[3].spr, 3)

GetUserDataFromHashSet(key) - retrieves the associated data based on the key. Using the example above, this would return 3. In most cases, this retrieval should be instant (or after searching a couple of items).

DeleteIntegerFromHashSet(key) - removes the key along with its associated data from the Hash Set. Most times it will be done in constant time but on rare occasions it may involve resizing which will take O(n) linear time.

Those are the functions of most importance. There are others which will allow you to print the details of the hash set and even write the whole thing to a file.

Testing has been minimal
Because I mainly use Tier 2, I don't really have any projects I can integrate this hash set into so it has not been tested on a large scale. I do however have a small demo:

rem
rem AGK Application
rem

#constant HASH_PRIME 20011

// NOTE: 0 is not a valid number for the hashet; 0 is treated as NULL

// HASH_HashSet type ************************************************************************
type HASH_HashSetObject
    value as integer
    usrData as integer
    occupied as integer
endtype

// HASH_HashSet vars
// current size of HASH_HashSet
global HASH_HashSetSize as integer
HASH_HashSetSize = 20

// number of objects inside HASH_HashSet
global HASH_numObjects as integer
HASH_numObjects = 0

global HASH_scale as integer
HASH_scale = HASH_HashSetSize*10+1

global HASH_offset as integer
HASH_offset = HASH_HashSetSize/2

global HASH_memory_magnitude as integer
HASH_memory_magnitude = 2

// HASH_HashSet
Dim HASH_HashSet[HASH_HashSetSize] as HASH_HashSetObject

// reset the entire HASH_HashSet ie everything = 0
HASH_wipeHashSet()

// End of HashSet vars and initialisation ****************************************************************************

// HashSet Demo ******************************************************************************************************
type Sprite
    x as integer
    y as integer
    spr as integer
    red as integer
    green as integer
    blue as integer
endtype

// Array of red sprites
Dim Sprites[100] as Sprite

for n = 1 to 10
    Sprites[n].x = random(1,getVirtualWidth()-10)
    Sprites[n].y = random(1,getVirtualHeight()-10)
    Sprites[n].spr = createSprite(0)

// add data to HASH_HashSet - unique sprite number, userData: in this case, the index of the individual sprite in the Sprites[] array
    addIntegerToHashSet(Sprites[n].spr,n)
    Sprites[n].red = random(1,255)
    Sprites[n].green = random(1,255)
    Sprites[n].blue = random(1,255)
    setSpriteColor(Sprites[n].spr, Sprites[n].red, Sprites[n].green,Sprites[n].blue,255)
    setSpritePosition(Sprites[n].spr, Sprites[n].x, Sprites[n].y)
    setSpriteSize(Sprites[n].spr, 4,4)
next n

sprCounter = n

writeHashSetToFile()

hit = 0

rem A Wizard Did It!
do
    printHashSetDetails()

// if the user has clicked on a sprite, print out the details - HASH_HashSet vs AGK
    if getPointerState()
        hit = GetSpriteHit(getPointerX(),getPointerY())
        if hit
            // get the user data from the hashset, in this case, the index of the individual sprite in the Sprites[] array
            index = getUserDataFromHashset(hit)
            print("Hash Spr: " + str(Sprites[index].spr) + "     " + "AGK Spr: " + str(hit))
            print("Hash red: " + str(Sprites[index].red) + "     " + "AGK Red: " + str(getSpriteColorRed(hit)))
            print("Hash green: " + str(Sprites[index].green) + "     " + "AGK Red: " + str(getSpriteColorGreen(hit)))
            print("Hash blue: " + str(Sprites[index].blue) + "     " + "AGK Red: " + str(getSpriteColorBlue(hit)))
            printHashSetObject(hit)
            // if the spacebar is pressed, delete the sprite
            if getRawKeyPressed(32)
                deleteSprite(hit)
                deleteIntegerFromHashSet(hit)
                sprCounter = sprCounter - 1
            endif

endif
    else
        // if the spacebar has been pressed (while the user isn't clicking) - create a sprite
        if getRawKeyPressed(32) and hit = 0
            // add a sprite
                if sprCounter <= 100
                    Sprites[sprCounter].x = random(1,getVirtualWidth()-10)
                    Sprites[sprCounter].y = random(1,getVirtualHeight()-10)
                    Sprites[sprCounter].spr = createSprite(0)

// add data to HASH_HashSet - unique sprite number, userData
                    addIntegerToHashSet(Sprites[sprCounter].spr,sprCounter)

// colour and position the sprite
                    Sprites[sprCounter].red = random(1,255)
                    Sprites[sprCounter].green = random(1,255)
                    Sprites[sprCounter].blue = random(1,255)
                    setSpriteColor(Sprites[sprCounter].spr, Sprites[sprCounter].red, Sprites[sprCounter].green,Sprites[sprCounter].blue,255)
                    setSpritePosition(Sprites[sprCounter].spr, Sprites[sprCounter].x, Sprites[sprCounter].y)
                    setSpriteSize(Sprites[sprCounter].spr, 4,4)
                    sprCounter = sprCounter + 1
                endif
        endif
    endif

print(str(sprCounter))
    print("Hit: " + str(hit))

Sync()
loop

// end demo *****************************************************************************************************************************************

function getHashSetSize()
endfunction HASH_HashSetSize

function getNumberOfHashSetObjects()
endfunction HASH_numObjects

// fill the HASH_HashSet with 0s
function HASH_wipeHashSet()
    for n = 0 to HASH_HashSetSize
        HASH_HashSet[n].value = 0
        HASH_HashSet[n].usrData = 0
        HASH_HashSet[n].occupied = 0
    next n

endfunction

// hash the key ie generate an index for the HASH_HashSet array based off the key
function hash(key as integer)
    index as integer
    index = mod( mod( key*HASH_scale + HASH_offset, HASH_PRIME), HASH_HashSetSize)
endfunction index

// resize the HASH_HashSet - O(n) time
function HASH_resizeHashSet()

Dim temp[HASH_numObjects] as HASH_HashSetObject

tempIndex = 0

// fill the temp array with the HASH_HashSet objects
    for n = 0 to HASH_HashSetSize
        if HASH_HashSet[n].occupied = 1
            value = HASH_HashSet[n].value
            temp[tempIndex].value = value
            temp[tempIndex].usrData = HASH_HashSet[n].usrData
            tempIndex = tempIndex + 1
        endif
    next n

HASH_HashSetSize = HASH_numObjects*(HASH_memory_magnitude+1)
    HASH_offset = HASH_HashSetSize/2

// resize HASH_HashSet
    Dim HASH_HashSet[HASH_HashSetSize] as HASH_HashSetObject

// wipe the HASH_HashSet
    HASH_wipeHashSet()

// add the temporary values back into the HASH_HashSet
    for n = 0 to HASH_numObjects
        index = hash(temp[n].value)

if HASH_HashSet[index].occupied = 0
            HASH_HashSet[index].value = temp[n].value
            HASH_HashSet[index].usrData = temp[n].usrData
            HASH_HashSet[index].occupied = 1
        else
            while HASH_HashSet[index].occupied = 1
                index = index + 1
                if index > HASH_HashSetSize then index = 0

endwhile

HASH_HashSet[index].value = temp[n].value
            HASH_HashSet[index].usrData = temp[n].usrData
            HASH_HashSet[index].occupied = 1
        endif
    next n

endfunction

// expected - O(1) time, worst case due to resizing is O(n)
function addIntegerToHashSet(key as integer, usr as integer)

// check HASH_HashSetSize
    if HASH_numObjects >= (HASH_HashSetSize-1)/HASH_memory_magnitude
        HASH_resizeHashSet()
    endif

// increase number of objects
    HASH_numObjects = HASH_numObjects + 1

// add the integer and user data to the HASH_HashSet
    index = hash(key)

// check the currently hashed spot - if available add the object
    if HASH_HashSet[index].occupied = 0
        HASH_HashSet[index].value = key
        HASH_HashSet[index].usrData = usr
        HASH_HashSet[index].occupied = 1
    else
        // if not available, linearly probe until we find an available spot
        while HASH_HashSet[index].occupied = 1
            index = index + 1
            if index > HASH_HashSetSize then index = 0
        endwhile

HASH_HashSet[index].value = key
        HASH_HashSet[index].usrData = usr
        HASH_HashSet[index].occupied = 1
    endif

endfunction

// retrieve user data from a key
// expected O(1) - worst case O(n)
function getUserDataFromHashSet(key as integer)
    // add the integer and user data to the HASH_HashSet
    index = hash(key)

counter = 0

while HASH_HashSet[index].value <> key and counter<=HASH_HashSetSize
        index = index + 1
        if index > HASH_HashSetSize then index = 0

counter = counter + 1
    endwhile

if counter > HASH_HashSetSize
        exitfunction 0
    endif

usr = HASH_HashSet[index].usrData
endfunction usr

// remove integer and associated data from HASH_HashSet
function deleteIntegerFromHashSet(key as integer)

// get a hashed index
    index = hash(key)

counter = 0

if HASH_HashSet[index].value = key
        HASH_HashSet[index].value = 0
        HASH_HashSet[index].usrData = 0
        HASH_HashSet[index].occupied = 0

// decrease the number of objects
        HASH_numObjects = HASH_numObjects-1
    else

while HASH_HashSet[index].value <> key and counter<=HASH_HashSetSize
            index = index + 1
            if index >= HASH_HashSetSize then index = 0

counter = counter + 1
        endwhile

if counter<HASH_HashSetSize
            HASH_HashSet[index].value = 0
            HASH_HashSet[index].usrData = 0
            HASH_HashSet[index].occupied = 0

// decrease the number of objects
            HASH_numObjects = HASH_numObjects-1
        endif
    endif

if HASH_numObjects <= HASH_HashSetSize/(HASH_memory_magnitude+2) and HASH_numObjects > 0
        HASH_resizeHashSet()
    endif

endfunction

// print the entire HASH_HashSet
function printHashSet()

print("HASH_HashSet Size: " + str(HASH_HashSetSize))
    print("Number of Objects: " + str(HASH_numObjects))

for n = 1 to HASH_HashSetSize
        print("[" + str(n) + "]: val=" + str(HASH_HashSet[n].value) + " usr=" + str(HASH_HashSet[n].usrData) + " occ=" + str(HASH_HashSet[n].occupied) + " hash=" + str(hash(HASH_HashSet[n].value)))
    next n

endfunction

// print single HASH_HashSet object
function printHashSetObject(key as integer)
    n = hash(key)
    print("HashSet[" + str(n) + "]: val=" + str(HASH_HashSet[n].value) + " usr=" + str(HASH_HashSet[n].usrData) + " occ=" + str(HASH_HashSet[n].occupied) + " hash=" + str(hash(HASH_HashSet[n].value)))

endfunction

// write the HASH_HashSet to a file
function writeHashSetToFile()
    file = openToWrite("HASH_HashSetLog.txt")

writeLine(file, "HASH_HashSet Size: " + str(HASH_HashSetSize))
    writeLine(file, "Number of Objects: " + str(HASH_numObjects))
    writeLine(file, "Magnitute: " + str(HASH_memory_magnitude))
    writeLine(file, "HASH_scale: " + str(HASH_scale))
    writeLine(file, "HASH_offset: " + str(HASH_offset))
    writeLIne(file, "HASH_PRIME: " + str(HASH_PRIME))

for n = 1 to HASH_HashSetSize
        writeLine(file,"[" + str(n) + "]: val=" + str(HASH_HashSet[n].value) + " usr=" + str(HASH_HashSet[n].usrData) + " occ=" + str(HASH_HashSet[n].occupied) + " hash=" + str(hash(HASH_HashSet[n].value)))
    next n

closefile(file)
endfunction

function printHashSetDetails()
    print("HASH_HashSet Size: " + str(HASH_HashSetSize))
    print("Number of Objects: " + str(HASH_numObjects))
endfunction

+ Code Snippet

rem
rem AGK Application
rem

#constant HASH_PRIME 20011

// NOTE: 0 is not a valid number for the hashet; 0 is treated as NULL

// HASH_HashSet type ************************************************************************
type HASH_HashSetObject
    value as integer
    usrData as integer
    occupied as integer
endtype

// HASH_HashSet vars
// current size of HASH_HashSet
global HASH_HashSetSize as integer
HASH_HashSetSize = 20

// number of objects inside HASH_HashSet
global HASH_numObjects as integer
HASH_numObjects = 0

global HASH_scale as integer
HASH_scale = HASH_HashSetSize*10+1

global HASH_offset as integer
HASH_offset = HASH_HashSetSize/2

global HASH_memory_magnitude as integer
HASH_memory_magnitude = 2

// HASH_HashSet
Dim HASH_HashSet[HASH_HashSetSize] as HASH_HashSetObject

// reset the entire HASH_HashSet ie everything = 0
HASH_wipeHashSet()

// End of HashSet vars and initialisation ****************************************************************************

// HashSet Demo ******************************************************************************************************
type Sprite
    x as integer
    y as integer
    spr as integer
    red as integer
    green as integer
    blue as integer
endtype


// Array of red sprites
Dim Sprites[100] as Sprite

for n = 1 to 10
    Sprites[n].x = random(1,getVirtualWidth()-10)
    Sprites[n].y = random(1,getVirtualHeight()-10)
    Sprites[n].spr = createSprite(0)

    // add data to HASH_HashSet - unique sprite number, userData: in this case, the index of the individual sprite in the Sprites[] array
    addIntegerToHashSet(Sprites[n].spr,n)
    Sprites[n].red = random(1,255)
    Sprites[n].green = random(1,255)
    Sprites[n].blue = random(1,255)
    setSpriteColor(Sprites[n].spr, Sprites[n].red, Sprites[n].green,Sprites[n].blue,255)
    setSpritePosition(Sprites[n].spr, Sprites[n].x, Sprites[n].y)
    setSpriteSize(Sprites[n].spr, 4,4)
next n

sprCounter = n

writeHashSetToFile()

hit = 0

rem A Wizard Did It!
do
    printHashSetDetails()

    // if the user has clicked on a sprite, print out the details - HASH_HashSet vs AGK
    if getPointerState()
        hit = GetSpriteHit(getPointerX(),getPointerY())
        if hit
            // get the user data from the hashset, in this case, the index of the individual sprite in the Sprites[] array
            index = getUserDataFromHashset(hit)
            print("Hash Spr: " + str(Sprites[index].spr) + "     " + "AGK Spr: " + str(hit))
            print("Hash red: " + str(Sprites[index].red) + "     " + "AGK Red: " + str(getSpriteColorRed(hit)))
            print("Hash green: " + str(Sprites[index].green) + "     " + "AGK Red: " + str(getSpriteColorGreen(hit)))
            print("Hash blue: " + str(Sprites[index].blue) + "     " + "AGK Red: " + str(getSpriteColorBlue(hit)))
            printHashSetObject(hit)
            // if the spacebar is pressed, delete the sprite
            if getRawKeyPressed(32)
                deleteSprite(hit)
                deleteIntegerFromHashSet(hit)
                sprCounter = sprCounter - 1
            endif

        endif
    else
        // if the spacebar has been pressed (while the user isn't clicking) - create a sprite
        if getRawKeyPressed(32) and hit = 0
            // add a sprite
                if sprCounter <= 100
                    Sprites[sprCounter].x = random(1,getVirtualWidth()-10)
                    Sprites[sprCounter].y = random(1,getVirtualHeight()-10)
                    Sprites[sprCounter].spr = createSprite(0)

                    // add data to HASH_HashSet - unique sprite number, userData
                    addIntegerToHashSet(Sprites[sprCounter].spr,sprCounter)

                    // colour and position the sprite
                    Sprites[sprCounter].red = random(1,255)
                    Sprites[sprCounter].green = random(1,255)
                    Sprites[sprCounter].blue = random(1,255)
                    setSpriteColor(Sprites[sprCounter].spr, Sprites[sprCounter].red, Sprites[sprCounter].green,Sprites[sprCounter].blue,255)
                    setSpritePosition(Sprites[sprCounter].spr, Sprites[sprCounter].x, Sprites[sprCounter].y)
                    setSpriteSize(Sprites[sprCounter].spr, 4,4)
                    sprCounter = sprCounter + 1
                endif
        endif
    endif


    print(str(sprCounter))
    print("Hit: " + str(hit))

    Sync()
loop

// end demo *****************************************************************************************************************************************

function getHashSetSize()
endfunction HASH_HashSetSize

function getNumberOfHashSetObjects()
endfunction HASH_numObjects

// fill the HASH_HashSet with 0s
function HASH_wipeHashSet()
    for n = 0 to HASH_HashSetSize
        HASH_HashSet[n].value = 0
        HASH_HashSet[n].usrData = 0
        HASH_HashSet[n].occupied = 0
    next n

endfunction

// hash the key ie generate an index for the HASH_HashSet array based off the key
function hash(key as integer)
    index as integer
    index = mod( mod( key*HASH_scale + HASH_offset, HASH_PRIME), HASH_HashSetSize)
endfunction index

// resize the HASH_HashSet - O(n) time
function HASH_resizeHashSet()

    Dim temp[HASH_numObjects] as HASH_HashSetObject

    tempIndex = 0

    // fill the temp array with the HASH_HashSet objects
    for n = 0 to HASH_HashSetSize
        if HASH_HashSet[n].occupied = 1
            value = HASH_HashSet[n].value
            temp[tempIndex].value = value
            temp[tempIndex].usrData = HASH_HashSet[n].usrData
            tempIndex = tempIndex + 1
        endif
    next n

    HASH_HashSetSize = HASH_numObjects*(HASH_memory_magnitude+1)
    HASH_offset = HASH_HashSetSize/2


    // resize HASH_HashSet
    Dim HASH_HashSet[HASH_HashSetSize] as HASH_HashSetObject

    // wipe the HASH_HashSet
    HASH_wipeHashSet()

    // add the temporary values back into the HASH_HashSet
    for n = 0 to HASH_numObjects
        index = hash(temp[n].value)

        if HASH_HashSet[index].occupied = 0
            HASH_HashSet[index].value = temp[n].value
            HASH_HashSet[index].usrData = temp[n].usrData
            HASH_HashSet[index].occupied = 1
        else
            while HASH_HashSet[index].occupied = 1
                index = index + 1
                if index > HASH_HashSetSize then index = 0


            endwhile

            HASH_HashSet[index].value = temp[n].value
            HASH_HashSet[index].usrData = temp[n].usrData
            HASH_HashSet[index].occupied = 1
        endif
    next n

endfunction

// expected - O(1) time, worst case due to resizing is O(n)
function addIntegerToHashSet(key as integer, usr as integer)

    // check HASH_HashSetSize
    if HASH_numObjects >= (HASH_HashSetSize-1)/HASH_memory_magnitude
        HASH_resizeHashSet()
    endif

    // increase number of objects
    HASH_numObjects = HASH_numObjects + 1

    // add the integer and user data to the HASH_HashSet
    index = hash(key)

    // check the currently hashed spot - if available add the object
    if HASH_HashSet[index].occupied = 0
        HASH_HashSet[index].value = key
        HASH_HashSet[index].usrData = usr
        HASH_HashSet[index].occupied = 1
    else
        // if not available, linearly probe until we find an available spot
        while HASH_HashSet[index].occupied = 1
            index = index + 1
            if index > HASH_HashSetSize then index = 0
        endwhile

        HASH_HashSet[index].value = key
        HASH_HashSet[index].usrData = usr
        HASH_HashSet[index].occupied = 1
    endif

endfunction

// retrieve user data from a key
// expected O(1) - worst case O(n)
function getUserDataFromHashSet(key as integer)
    // add the integer and user data to the HASH_HashSet
    index = hash(key)

    counter = 0

    while HASH_HashSet[index].value <> key and counter<=HASH_HashSetSize
        index = index + 1
        if index > HASH_HashSetSize then index = 0

        counter = counter + 1
    endwhile

    if counter > HASH_HashSetSize
        exitfunction 0
    endif

    usr = HASH_HashSet[index].usrData
endfunction usr

// remove integer and associated data from HASH_HashSet
function deleteIntegerFromHashSet(key as integer)

    // get a hashed index
    index = hash(key)

    counter = 0

    if HASH_HashSet[index].value = key
        HASH_HashSet[index].value = 0
        HASH_HashSet[index].usrData = 0
        HASH_HashSet[index].occupied = 0

        // decrease the number of objects
        HASH_numObjects = HASH_numObjects-1
    else

        while HASH_HashSet[index].value <> key and counter<=HASH_HashSetSize
            index = index + 1
            if index >= HASH_HashSetSize then index = 0

            counter = counter + 1
        endwhile

        if counter<HASH_HashSetSize
            HASH_HashSet[index].value = 0
            HASH_HashSet[index].usrData = 0
            HASH_HashSet[index].occupied = 0

            // decrease the number of objects
            HASH_numObjects = HASH_numObjects-1
        endif
    endif

    if HASH_numObjects <= HASH_HashSetSize/(HASH_memory_magnitude+2) and HASH_numObjects > 0
        HASH_resizeHashSet()
    endif

endfunction


// print the entire HASH_HashSet
function printHashSet()

    print("HASH_HashSet Size: " + str(HASH_HashSetSize))
    print("Number of Objects: " + str(HASH_numObjects))

    for n = 1 to HASH_HashSetSize
        print("[" + str(n) + "]: val=" + str(HASH_HashSet[n].value) + " usr=" + str(HASH_HashSet[n].usrData) + " occ=" + str(HASH_HashSet[n].occupied) + " hash=" + str(hash(HASH_HashSet[n].value)))
    next n

endfunction

// print single HASH_HashSet object
function printHashSetObject(key as integer)
    n = hash(key)
    print("HashSet[" + str(n) + "]: val=" + str(HASH_HashSet[n].value) + " usr=" + str(HASH_HashSet[n].usrData) + " occ=" + str(HASH_HashSet[n].occupied) + " hash=" + str(hash(HASH_HashSet[n].value)))

endfunction

// write the HASH_HashSet to a file
function writeHashSetToFile()
    file = openToWrite("HASH_HashSetLog.txt")

    writeLine(file, "HASH_HashSet Size: " + str(HASH_HashSetSize))
    writeLine(file, "Number of Objects: " + str(HASH_numObjects))
    writeLine(file, "Magnitute: " + str(HASH_memory_magnitude))
    writeLine(file, "HASH_scale: " + str(HASH_scale))
    writeLine(file, "HASH_offset: " + str(HASH_offset))
    writeLIne(file, "HASH_PRIME: " + str(HASH_PRIME))



    for n = 1 to HASH_HashSetSize
        writeLine(file,"[" + str(n) + "]: val=" + str(HASH_HashSet[n].value) + " usr=" + str(HASH_HashSet[n].usrData) + " occ=" + str(HASH_HashSet[n].occupied) + " hash=" + str(hash(HASH_HashSet[n].value)))
    next n

    closefile(file)
endfunction

function printHashSetDetails()
    print("HASH_HashSet Size: " + str(HASH_HashSetSize))
    print("Number of Objects: " + str(HASH_numObjects))
endfunction

Demo controls:
Add a sprite: spacebar
Delete a sprite: click on the sprite and press spacebar

Specifics
In this hashset I treat a key value of 0 as NULL. This means it's not a valid entry so undefined actions may occur if you attempt to add in key values of 0. I also have not catered for negative key values and this may cause "Out of bounds" errors so don't use them.

To use in your projects, place everything in-between the rows of stars (including the #constant and TYPE) at the top of your program.

This Hash Set uses linear probing as opposed to bucket lists since resizing multi-dimensional arrays are unpredictable in AGK.

To adjust the starting size of memory (>1 would be a good start), adjust the value of HASH_hashSetSize in its declaration.

After the HASH_HashSet has been declared the wipeHashSet() function must be called.

You can slightly control the size of the hash set by varying the HASH_memory_magnitude value. I recommend:
1: uses more processing but less memory
2: uses less processing but more memory

If you find any bugs, crashing etc, let me know and I'll try to fix it. Remember to back up your projects before you integrate this.

I hope this helps some of you out there.

Back to top

Profile PM Email

Lucas Tiridath

AGK Developer

15

Years of Service

User Offline

Joined: 28th Sep 2008

Location: Kings Langley, UK

Posted: 22nd Mar 2013 08:58

Link

Hey Hodgey, nice work! This looks really neat. Thanks for sharing! I've heard a lot about hash tables but I've never seen an implementation before so this is great to have.

I just tried the demo and everything worked fine for me. I'll be sure to let you know if I end up using this in any of my projects. Thanks!

Back to top

Profile PM Email Website

Hodgey

14

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 22nd Mar 2013 11:16

Link

Thanks Lucas! I hope you find it useful. From my preliminary tests I actually couldn't cause any collisions ie two or more entries which have the same hash value which means retrieval shouldn't require any searching at all. But I do have a fail-safe in the event that collisions occur. So most of the time, it should be pretty darn quick!

Quote: "I've heard a lot about hash tables but I've never seen an implementation before so this is great to have."

The Hashset is one of my favourite data structures and not just because they have a cool name. This implementation however is quite basic, it's the elaborate ones which I find interesting. At uni we had to implement what was called a Ping Pong Hash Set. The idea was to have two tables and when a collision occurs, you bounce the original into the other table and pop in the new entry. You're pretty much playing ping pong with the entries! After X number of consecutive bounces, you'd resize both hash tables.

Back to top

Profile PM Email

baxslash

Valued Member

Bronze Codemaster

17

Years of Service

User Offline

Joined: 26th Dec 2006

Location: Duffield

Posted: 22nd Mar 2013 12:02

Link

This is an incredibly useful share for those of us who worry about looping through a huge array just to find one piece of data. When there are hundreds of data entries it can certainly impact on game speed.

Thanks a LOT for sharing this Hodgey I will certainly use it

this.mess = abs(sin(times#))

Back to top

Profile PM Email

Marl

12

Years of Service

User Offline

Joined: 19th Nov 2011

Location: Bradford, UK

Posted: 22nd Mar 2013 18:20

Link

Always meant to write one of these - now you've saved me the trouble.

Trivia: Amiga File system... Hashed. (Hash index created from the filename)

Back to top

Profile PM Email

Hodgey

14

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 22nd Mar 2013 21:17

Link

I hope you make good use of it guys.

Quote: "Trivia: Amiga File system... Hashed. (Hash index created from the filename)"

Sounds like you'd need to take a polynomial approach. The tricky part is producing different hash indexes for words with the same letters like "stop", "pots", "tops" etc. The poly should do it but if you're given a huge path, you might have to tone it down a bit an put up with collisions.

Back to top

Profile PM Email

JimHawkins

14

Years of Service

User Offline

Joined: 26th Jul 2009

Location: Hull - UK

Posted: 22nd Mar 2013 23:50 Edited at: 22nd Mar 2013 23:50

Link

It's quite hard to do string hashing without getting some collisions, but obviously it's important not to let collision buckets get too big. In general hash tables should be at least twice the size of the maximum capacity.

The simplest method to generate a key is to scan the string (sometimes it's better to do it backwards), multiply the char value of each character by a prime number, and add it to the result. Simple Pascal example:

+ Code Snippet


Function GenKey(const s : ansistring): int64;
const prime = 29;
var i : integer;
begin
 result := length(s);
 for i := length(s) downto 1 do
  result := result + (ord(s[i]) * prime);
end;

This will usually make a large number, so to insert or try to check it we need to mod it with the size of the hash table.

It may not be worth doing this with small amounts of data, because a sorted array can be much faster to probe with a binary search. I would think with sprites that you're unlikely to have thousands, and it should not be hard to have an array of user data structures whose indices match the sprite index - that's a guaranteed instant hit!

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL

Back to top

Profile PM Website

Hodgey

14

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 23rd Mar 2013 01:02 Edited at: 23rd Mar 2013 01:10

Link

Quote: "It's quite hard to do string hashing without getting some collisions, but obviously it's important not to let collision buckets get too big."

I haven't yet tried with strings. What one could do is break the string up into chunks, then apply the polynomial to each chunk and then add up the chunks. Of course this opens you up for collisions but they should be rarer than just adding up the ascii values. A half-half type solution. There is another technique mentioned in my data structures book known as "Cyclic Shifting", I haven't yet looked at it in depth.

Quote: "It may not be worth doing this with small amounts of data, because a sorted array can be much faster to probe with a binary search. "

But you do have to sort the array which (unless you're feeding the numbers to the array in order) can take O(nlogn) time if you've got decent algorithms. Also, from what I can tell, since the Hash Set's size is always larger than the number of objects, each entry gets a unique hash index. The linear probing is there just incase a duplicate hashkey is caused and with a large enough prime number, (which I need to change) should mean that they're quite spread out so any linear probing shouldn't have to search more than a couple of indices ahead.

Quote: "I would think with sprites that you're unlikely to have thousands, and it should not be hard to have an array of user data structures whose indices match the sprite index - that's a guaranteed instant hit!"

The only problem is that the auto generated sprite numbers begin at 10001. And then if you have multiple arrays, direct sprite number to index is impossible. The main idea of the Hashset is so that you can pair your sprites with the corresponding array index. Rarely, if ever, should it actually have to search for the desired key, most likely, retrieval will be only a math calculation away.

To each their own Jim. It's here for those who'd like to use it.

Back to top

Profile PM Email

JimHawkins

14

Years of Service

User Offline

Joined: 26th Jul 2009

Location: Hull - UK

Posted: 23rd Mar 2013 13:59 Edited at: 23rd Mar 2013 14:01

Link

Hodgey - I understand that.

It's only a Tier 1 issue, anyway. In C++ or Object Pascal it's very easy to extend the sprite class with any fields or methods, link them with lists etc. For those who don't understand just how easy it is, this adds a Name field to a sprite in Pascal:

+ Code Snippet

Type TMySprite = class(TAGKSprite)
      public
       Name: string;
     end;

// Instead of creating the base class we can create
// the extended class

var Piggy : TMySprite;

Piggy := TMySprite.Create(self, image_deadpig);
Piggy.name := 'Pork joint';

// Everything to do with this sprite works exactly as
// it should, and because the data is held within the
// object instance we don't need separate arrays.

It would be very easy before the next release for TGC to add at least one user data integer field to the sprite class and add simple set and get functions for T1 users.

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL

Back to top

Profile PM Website

Hodgey

14

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 24th Mar 2013 12:12

Link

Quote: "It would be very easy before the next release for TGC to add at least one user data integer field to the sprite class and add simple set and get functions for T1 users."

Oh is that what you meant? It'd be a cinch to do that.

Back to top

Profile PM Email

JimHawkins

14

Years of Service

User Offline

Joined: 26th Jul 2009

Location: Hull - UK

Posted: 24th Mar 2013 12:46

Link

What I meant was - T1 users could set that to an index into an array of UDTs where they could keep their extended information, or use it as a tag to store flags etc. In fact it would be useful for all objects to have a tag field.

Cost to TGC - about ten minutes of programming!

-- Jim DO IT FASTER, EASIER AND BETTER WITH AppGameKit FOR PASCAL

Back to top

Profile PM Website

Timshark

16

Years of Service

User Offline

Joined: 30th Jun 2007

Location: Oslo, Norway

Posted: 13th May 2013 06:34 Edited at: 13th May 2013 06:54

Link

@Hodgey

Very nice and very generous!

I've currently decided to rewrite my whole array system. I didn't do enough planning and now it's just growing and I'm starting to create new arrays to make up for bad planning. This hash system is very tempting but before I use it want to make sure It suits my needs.

I have a huge amount of sprites. They are laid out in a x,y matrix on the screen. They will all be drawn each frame but only a selection of them will be active (set up for collision) in each level.

I need to reference these sprites in two principal ways. Their x,y value and their sprite values. Right now I'm using a two dimensional array for their x,y position. And one array for their sprite numbers which contains a UDT with the x,y value. So the two arrays can reference to eachother if I need to.

Do you think, based on this very limited view on my need, I would benefit from using a hash table?

I guess this is a lot to ask, buth what the heck...

I never want what I know.

Back to top

Profile PM

Markus

Valued Member

20

Years of Service

User Offline

Joined: 10th Apr 2004

Location: Germany

Posted: 13th May 2013 13:18 Edited at: 13th May 2013 17:44

Link

i had made a feature request, for a integer reference number in the sprite Structure. then if we get this we can save a index to a udt array direct in the sprite and also get this index back for direct access a udt array.

edit:
you can bump it here

http://code.google.com/p/agk/issues/detail?id=531&can=4&sort=-id%20-type

Back to top

Profile PM Email

Hodgey

14

Years of Service

User Offline

Joined: 10th Oct 2009

Location: Australia

Posted: 13th May 2013 15:20

Link

@Timshark: The main idea of this particular implementation is to tag a sprite number with a single integer of user data (usually an array index). If I've read your situation correctly, you could use the hash table to pair your sprite ids with the array indices of your sprite udt array (second one you mentioned).

A few things to consider before implementing it:
1. From what I hear, people have requested for AppGameKit to support user data and sprite id pairs which could quickly render the hash table redundant. Double check with Paul if he plans to add that because it would save more memory, run faster and be much less hassle.

2. I mainly use C++ nowadays and so I haven't really needed the hash table myself therefore I haven't thoroughly tested it . Should you choose to use it and find problems, I'll be happy to take a look.

I'm glad to see others taking an interest in it and it was fun to write. I do think the hash table can help you but check with Paul before implementing (also have a backup plan and back up source in case it doesn't work). All he would have to do is modify the sprite class and add a few functions to make the hash table obsolete.

Back to top

Profile PM Email

Timshark

16

Years of Service

User Offline

Joined: 30th Jun 2007

Location: Oslo, Norway

Posted: 13th May 2013 23:30 Edited at: 14th May 2013 02:21

Link

@Hodgey: Thank you for your time and evalutation. If they are considering Markus request I think this could be the thing for me. But I've also thought about it a little more. In my setup I'm feeding the sprite numbers to the array so they are the same. I think maybe the hash table is really useful when you don't know the spriteID and let agk create them for you.
Anyway, I'm intrigued by the system.

@Markus
The ability to attach a UDT to a sprite is a really good idea. I'm bumping it!

I never want what I know.

Back to top

Profile PM

Sorry your browser is not supported!

AppGameKit Classic Chat / Hash Table - user data for sprites etc