Why use a prime number as the hash table size

A quick answer

Use a prime number as the hash table size will on average give you the best distribution of hash values to hash buckets [1].

An example

For the hash table, usually, we have more keys than the hash table size. We’d like to have a quick comparison by using this simple example

keys(even numbers)  : 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
hashtable size = 10 : 2, 4, 6, 8, 0, 2, 4, 6, 8, 0
hashtable size = 11 : 2, 4, 6, 8, 10, 1, 3, 5, 7, 9

Detail explanations

See[1] and [2]

Reference

[1]https://www.quora.com/Why-should-the-size-of-a-hash-table-be-a-prime-number

[2]https://stackoverflow.com/questions/3980117/hash-table-why-size-should-be-prime

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

How to Conduct a System Design Interview

The Role of the Architect in an Agile World

Install ZM 1.36 branch, Ubuntu 21.04 Part 2

Spring Web Service response filtering

Let It Go — The Ledge, I mean

cplace DIGITAL CONFERENCE — collaborate. co-create. innovate.

Bedrock Third Person Camera

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Minimum Spanning Tree & Prim’s Algorithm

Anagrams in Dictionary

Kruskal’s Algorithm — A Summary

Median of a Binary Search Tree