Basic little HashSet implementation

  • It's annoying that Lua doesn't have proper support for sets, requiring slightly ugly use of tables.

    To this end, hopefully people can get some use out of this:

    It's not perfect, because Lua lacks proper static typing and ROBLOX is running an old verison of Lua which would let it work a little bit more nicely, and Lua requiring to implement OOP by yourself is an absolute joke, etc...

    Also the in-script commenting is bad.


    Basic implementation of a hash-set in Lua.

    Create an empty set with .new, or create one from an array with .fromArray.

    Check for presence in a set with :contains. Add or remove elements with :add and :remove. Cardinality (size) of the set can be retrieved with :size.

    Element-by-element equality can be checked with :equals, or alternatively, an overload of == is provided, so set1 == set2 is valid. Frankly, when even Lua can provide operator overloading, it's a bit embarrasing when a language can't (looking at you, Java). Overloading of + is not provided, because it'd be ambiguous whether you meant intersect or union. Overloading of - isn't provided because it'd be a bit weird providing - but not +.

    Unfortunately, seamless pairs() use is not possible since ROBLOX is running an old version of Lua. As an alternative, you need to call :pairs(). E.g., for value in set:pairs() do. Note the absence of the second field - it's a set.

    Union and intersect operations are performed in-place with :union and :intersect. Similarly, :minus is in-place, and calculates the relative set complement of two sets. "In-place" just means it doesn't return a new set: it modifies the old one.

    Obviously, being in-place is a bit annoying sometimes, so :copy can be used to create a shallow copy of the set.

    Finally, as a nice little bonus, this class implements __tostring, so printing it actually gives you a real result rather than the mess Lua gives you by default. How hard is it for a language to provide a decent tostring for a data structure when said languages has literally only 1 data structure?

    That's basically it. Contact me if you have any questions.

  • Nice job! Could I ask, though, what inspired you to do this? No offense, but I doubt this will be quite useful to me in the developmental aspect.

    Also, does your set allow duplicates? (I haven't looked into it yet)

  • Well, looking into your code, I see that you do not allow duplicates - that's good. However, there seems to be no real "hashing" that's occuring. In fact, the Java implementation uses a HashMap behind the scenes. From what I can tell, you use an array. Is it possible that you could remove the "Hash" part of your HashSet, and make it an implementation of a Set that uses an array?

    Sorry, this is more of my Java side speaking here.

  • Whoops, I mean table (sorry, my Java side is taking over).

  • Global Moderator

    @Zenith_Lord Lua tables have both an array and hashtable part. The hashing happens behind the scenes.

  • @Zenith_Lord Lua tables are hash maps. All data structures in Lua are just HashMaps jazzed up a bit, except maybe a LinkedList or Tree type structure if you were to make them yourself with Lua's terrible OOP system.

    The set uses the elements as an index, setting values to true, although the values are just arbitrary and could be anything. Since tables are just HashMaps, indexing by value is basically a HashSet.

    The reason I made it is because I was building a depth first search to create welds between already connected parts, and the logic to mess with dictionaries was cluttering up the code. Also, a lot of questions on this forum have optimum solutions involving hash-sets, and I thought it'd be useful to just link to this in future rather than trying to re-explain using a dictionary as a hash-set every time.

  • Global Moderator

    @fredfishy Lua has no OOP system. Lua provides you with the tools necessary to make your own, that's different.

  • @Link150 true, but either way, using OOP in the language makes me want to jump off a bridge. Also it feels like metatables were implemented with OOP in mind specifically.

Log in to reply

Looks like your connection to Scripting Helpers was lost, please wait while we try to reconnect.