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.

Laravel Advance | How to Add Foreign Key in Laravel Migration

Week 5

AWS CloudWatch Alarms in Slack

Datacamp Data Science with Python Course Review

Roost — a new and a unique way to do CI, your changes are always production-ready

Discovering RapidMiner

What is the docker ENTRYPOINT and how is it used ?

What happens when you type holbertonschool.com in your browser and press ENTER

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

Floyd Warshall Algorithm

Sliding Window + String (Leectcode)

Internship Experience at MoveInSync Technologies

MoveInSync Technologies logo

The case of critical dinosaurs