Map which doesn’t convert all keys to strings first. But
Map still treats floating point keys differently than all the other hash tables we have seen so far: it defines a custom comparison operator for floating point numbers that differs from
===. One important property of this comparison operator is that it avoids the problems with NaN keys we saw with other programming languages, but at the cost of introducing yet another notion of equality to the language.
Let’s take a look at
Map hashing in turn.
Read More »
The Go Programming Language has a built-in map datatype that is implemented using hash tables. The only types that can be used as map keys are those for which the language defines an equality operator
==; this includes primitive types like Booleans, strings, numbers, and pointers, but also composite types like arrays and structures. For all these types Go automatically generates a suitable hash function. Maps are not extensible, however: if you need a hash table that supports custom comparison or hash algorithms you have to write your own.
Floating point numbers can be used as map keys, and since Go follows the normal conventions for comparison, so maps treat all NaN keys as distinct since NaN ≠ NaN. As a consequence NaN keys can be inserted into maps but are unretrievable; in fact, any number of NaN keys can be inserted, and because they are all distinct it’s possible to end up with a map in which every entry is unretrievable. Normally this would be merely a curiosity, an interesting side effect of the quirky semantics of floating point numbers. But this curiosity can lead to an exploitable performance issue if the hash function being used maps every NaN to a single hash code. In this case all the NaN keys collide in the hash table and the runtime cost of inserting n of them drops to O(n2), down from the O(n) we would expect for uniformly distributed hash codes.
Overloading servers by causing hash table collisions has become a a real security threat in recent years. Many languages and hashing algorithms were found to be susceptible to these so-called hash-flooding attacks and had to be updated. In the following I will discuss how Go prevents hash-flooding attacks, in particular for the special of case floating point keys.
Read More »