Simple non-cryptographic hash functions in Javascript

4 hashbrowns on a plate, captioned with HASHBROWNS a pun

Introduction
Example 1: modulo operator (%)
Example 2: djbx33a
Example 3: fnv1a_32
Credits & Footnotes

Introduction

"Implement a hash table." is a classic programming interview question.⁽¹⁾ A hash table is a common data structure. It goes by a few names - hash table, hashmap, a Python dictionary.

To answer the question, you first need to clarify the requirements: What is the use-case for the hash table? Understanding the use-case will help you decide whether to use a cryptographic or a non-cryptographic hash function.

To understand cryptographic vs. non-cryptographic hash functions, consider the analogy of a "one-way vs. two-way door" and the following pseudo-code.

A table with pseudo-code comparing cryptographic vs. non-cryptographic hash functions.

A cryptographic hash function is like a "one-way door". It should be irreversible. After applying a cryptographic hash function, crypto_hash, to an input, you should not be able to derive the original input from crypto_output.

A non-cryptographic hash function is more like a "two-way door". After applying a non-cryptographic hash function, non_crypto_hash, to an input, you can still infer certain properties about the input.

This post is about simple non-cryptographic hash functions in Javascript. Again, do not write your own hash functions for passwords or secure data. I include toy examples of Javascript non-cryptographic hash functions for learning purposes.

Example 1: modulo operator (%)

The simplest example of a non-cryptographic hash function is the modulo operator (%).


  const mod_hash = (num) => num % 5;

Suppose you want to hash the numbers 1-100. To visualize this, imagine you have 100 red, bouncy balls numbered 1 to 100. You want to sort them equally into 5 big, blue buckets numbered 1 to 5.

4 stacked hashbrowns on a plate, captioned with 'HASHBROWNS'.

One way to do this mathematically is to use the modulo operator (%). num % 5 is the remainder when you divide num by 5. For example:

42 % 5 = 2 because 42 = 5 * 8 + 2.
30 % 5 = 0 because 30 = 5 * 6 + 0.

To test this, you can also run the mod_hash Javascript code snippet in your browser: right-click and click Inspect, or use the keyboard shortcut (option-command-I on Mac).

A screenshot of the browser console computing mod_hash for the numbers 1-10.


  // 💡 Learning check: Take a minute to compute
  mod_hash(11);
  mod_hash(24);
  mod_hash(90);
  // Do it in your head. You can double-check by running the code.

Example 2: djbx33a

Another example of a simple, non-cryptographic hash function is djbx33a. The function is named after Daniel J. Bernstein (DJB).


  // Magic number.
  const DJB_IV = 5381;

  function djbx33a(str) {
    let hash = DJB_IV;

    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) + hash) + str.charCodeAt(i); // hash * 33 + c
    }
    return hash >>> 0;
  }

To test this, you can run this code snippet in your browser: right-click and click Inspect, or use the keyboard shortcut (option-command-I on Mac). Again, do not use this hash function for passwords or secure data. You can test it with names of fruits or vegetables.

The code snippet is basic Javascript, but 3 bits (pun intended) stand out. For more information on bitwise operations, please see this article on bitwise operations and their performance in Javascript.

$(hash << 5 + hash) = hash * 2^5 + hash = hash * 33$
hash >>> 0 - see mdn web docs
str.charCodeAt(i) - see mdn web docs

Also, why are there magic numbers: 5381 and 33?? Don't think too hard about it - they're magic. You can poke around the Internet more if you're curious.

Example 3: fnv1a_32

The last example I'll share here is fnv1a_32, named after Fowler-Noll-Vo (FNV).


  // Magic numbers, base 16.
  const FNV_PRIME = 0x01000193
  const FNV_IV = 0x811c9dc5
  
  function fnv1a_32(str) {
    let hash = FNV_IV;
  
    for (let i = 0; i < str.length; i++) {
      hash ^= str.charCodeAt(i);
      hash = (hash * FNV_PRIME) >>> 0;
    }
    return hash;
  }

Similarly to the djbx33a function, the fnv1a_32 function is basic Javascript with 3 bits that stand out.

^= operator - see mdn web docs
str.charCodeAt(i) - see mdn web docs
(hash * FNV_PRIME) >>> 0 - see mdn web docs

Credits

This post was inspired by an ACM Queue article, Questioning the Criteria for Evaluating Non-cryptographic Hash Functions. Indeed, we should think more about non-cryptographic hash functions.

For the hashbrown image: The hash brown photo is from Dandk Organizer. The Scrabble tiles are from this Etsy shop. The art was inspired by an Etsy shop selling a hash brown squeaky dog toy.

The LaTeX formula is from QuickLaTeX.

Footnotes

(1) I actually got this question, "Implement a hash table", a few years ago when interviewing. I'm pretty sure I failed it because I did not get the job offer.