Hash table with linear probing implementation in LSL (Linden Scripting Language)

hashtable.lsl

// Hash Table Implementation (Linear Probing)
// v1.0.0
// Copyright (c) 2026 Testicular Slingshot
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

// Creates and returns a new hash table.
list ht_create(integer initial_capacity, float load_factor)
{
    // Default values.
    if (initial_capacity <= 0)
        initial_capacity = 11;
    if (load_factor <= 0.0)
        load_factor = 0.75;

    list table = [0, load_factor]; // Buckets filled, load factor.
    while (initial_capacity--)
        table += ["", 0]; // Empty key, value pair.
    return table;
}

// Returns the value mapped to the given key.
list ht_get(list table, string key_str)
{
    integer table_size = llGetListLength(table);
    integer key_hash = llAbs(llHash(key_str));
    integer total_capacity = (table_size - 2) / 2;
    integer key_idx = llAbs(key_hash % (total_capacity * 2) ) + 2;
    integer start_idx = key_idx;
    string stored_key = llList2String(table, key_idx);
    do
    {
        if (stored_key == key_str)
        {
            return llList2List(table, key_idx + 1, key_idx + 1);
        }
        else if (stored_key == "")
        {
            // Key doesn't exist.
            return [];
        }
        else
        {
            // Possible collision, linear probe.
            key_idx += 2;
            if (key_idx >= table_size)
                // Wrap around.
                key_idx = 2;
            stored_key = llList2String(table, key_idx);
        }
    } while (key_idx != start_idx); // End of table.
    return [];
}

// Maps the specified key to a specified value.
list ht_put(list table, string key_str, list value)
{
    // Check the load factor before inserting.
    integer table_size = llGetListLength(table);
    integer total_capacity = (table_size - 2) / 2;
    float buckets_filled = llList2Integer(table, 0);
    float load_factor = llList2Float(table, 1);
    if ( (buckets_filled / total_capacity) >= load_factor)
    {
        table = __ht_rehash(table);
    }

    return __ht_put(table, key_str, value);
}

// Removes a key and value from the table.
list ht_remove(list table, string key_str)
{
    integer table_size = llGetListLength(table);
    integer key_hash = llHash(key_str);
    integer total_capacity = (table_size - 2) / 2;
    integer key_idx = llAbs(key_hash % (total_capacity * 2) ) + 2;
    integer start_idx = key_idx;
    string stored_key = llList2String(table, key_idx);
    do
    {
        if (stored_key == key_str)
        {
            table = llListReplaceList(table, ["", 0], key_idx, key_idx + 1);
            // Update.
            integer buckets_filled = llList2Integer(table, 0);
            if (buckets_filled > 0)
            {
                table = llListReplaceList(table, [buckets_filled - 1], 0, 0);
            }
            return table;
        }
        else if (stored_key == "")
        {
            // Key doesn't exist.
            return table;
        }
        else
        {
            // Possible collision, linear probe.
            key_idx += 2;
            if (key_idx >= table_size)
                // Wrap around
                key_idx = 2;
            stored_key = llList2String(table, key_idx);
        }
    } while (key_idx != start_idx); // End of table.
    return table;
}

// Returns how many keys are in a table.
integer ht_size(list table)
{
    return llList2Integer(table, 0);
}

// Returns if the specified key is in a table.
integer ht_contains_key(list table, string key_str)
{
    return (ht_get(table, key_str) != []);
}

// Maps the specified key to a specified value
// @internal
list __ht_put(list table, string key_str, list value)
{
    integer table_size = llGetListLength(table);
    integer total_capacity = (table_size - 2) / 2;
    integer key_hash = llHash(key_str);
    integer key_idx = llAbs( key_hash % (total_capacity * 2) ) + 2;
    integer start_idx = key_idx;
    string stored_key = llList2String(table, key_idx);
    do
    {
        if (stored_key == key_str)
        {
            // Update.
            table = llListReplaceList(table, llList2List(value, 0, 0), key_idx + 1, key_idx + 1);
            return table;
        }
        else if (stored_key == "")
        {
            // Insert.
            table = llListReplaceList(table, [key_str] + llList2List(value, 0, 0), key_idx, key_idx + 1);
            integer buckets_filled = llList2Integer(table, 0) + 1;
            table = llListReplaceList(table, [buckets_filled], 0, 0);
            return table;
        }

        // Collision.
        key_idx += 2;
        if (key_idx >= table_size)
            // Wrap around.
            key_idx = 2;
        stored_key = llList2String(table, key_idx);
    } while (key_idx != start_idx); // End of table.
    return table;
}

// Expands the table and rehashes all of the keys.
// @internal
list __ht_rehash(list table)
{
    integer table_size = llGetListLength(table);
    integer total_capacity = ( (table_size - 2) / 2 ) * 2;   // Double the size.
    list rehashed_table = ht_create(total_capacity, llList2Float(table, 1));
    integer key_idx;
    for (key_idx = 2; key_idx < table_size; key_idx += 2)
    {
        // Refill.
        string stored_key = llList2String(table, key_idx);
        if (stored_key != "")
            rehashed_table = __ht_put(rehashed_table, stored_key, llList2List(table, key_idx + 1, key_idx + 1));
    }
    return rehashed_table;
}

default
{
    state_entry()
    {
        // == EXAMPLE CODE ==
        list keys = ["foo", "bar", "aaaa", "bbbb", "Hello", "World", "cccc", "dddd", "5"];
        integer keys_length = llGetListLength(keys);
        list map = ht_create(4, 0.0); // Create map with capacity of 4 and default load factor.
        integer i;
        for (; i < keys_length; ++i)
        {
            // Fill up the table.
            // It should automatically resize and rehash after the third
            // and sixth iterations.
            map = ht_put(map, llList2String(keys, i), [ (string)i ]);
        }

        integer val = llList2Integer(ht_get(map, "bbbb"), 0);
        llOwnerSay("val = " + (string)val); // Should print that val is 3.
        map = ht_remove(map, "bbbb"); // Key "bbbb" should get removed.
        if (! ht_contains_key(map, "bbbb"))
        {
            // Should print this.
            llOwnerSay("Key \"bbbb\" does not exist.");
        }

        llOwnerSay("Number of keys: " + (string)ht_size(map)); // Should print 8.

        if (ht_get(map, "NOT FOUND KEY") == [])
        {
            // Should print this.
            llOwnerSay("Another way of checking if a key exists or not.");
        }
        // == /EXAMPLE CODE ==
    }
}