Floating Point Keys in Lua: a Simple Ad-Hoc Solution

Lua is an economical programming language: it’s fast, compact, and both the language and its standard library are small but surprisingly powerful. There are only a handful of built-in data types and just one language feature for structuring data: tables can hold arbitrary key/value pairs, and represent, depending on the choice of keys and values, everything from arrays, sets, dictionaries, and structures to classes and objects. An array, for example, is a table indexed with integer keys, and a structure is a table indexed with strings that represent the field names.

All built-in types can be used as table keys and values. In this article I will explain how Lua handles numeric keys, and in particular floating point keys. In keeping with Lua’s tradition, the solution is practical and efficient. But, also in keeping with Lua’s tradition, the implementation isn’t trivial and narrowly skirts undefined behavior. Let’s take a look.

Advertisements

Using Floating Point Numbers as Hash Keys

Strings and integers are the most common keys for hash tables, but in principle every type can be used as a hash key, provided we define a suitable comparison operator and hash function. Most languages that support hash tables also provide hash functions for all built-in types, including floating point numbers. In this series of articles I will take a look at how languages like Lua, Python, JavaScript, and C++ handle floating point keys. It turns out that there are significant differences between these languages, both in the way they handle special values like NaN and in the way they define their hash functions.

This article addresses a few general questions: what is the difference between floating point numbers and other types of hash keys? What are common pitfalls when defining hash functions for floats? How do we handle special values such as minus zero, infinity, and NaN?