Feature #16851

Ruby hashing algorithm could be improved using Tabulation Hashing

Added by ana06 (Ana Maria Martinez Gomez) 3 months ago. Updated 3 months ago.

Target version:


I have implemented Linear Probing and Simple tabulation in Ruby:

I tested it using the following code:
It benchmarks the insertion of 600000 elements (by hashing their 64 bits ids) in an empty hash 100 times. Below are the times (in seconds) I got executing this code for different versions of the Ruby code:

  • master (without Simple Tabulation): 29.68
  • master with Linear Probing (without Simple Tabulation): 99.76
  • master with Quadratic Probing (without Simple Tabulation): 29.97
  • master with Simple Tabulation: 15.76
  • master with Linear Probing and Simple Tabulation: 24.23
  • master with Quadratic Probing and Simple Tabulation: 13.73

master refers to ruby 2.8.0dev:
(2020-05-07T16:22:38Z master 7ded8fd) [x86_64-linux].
I tried with 8 x Intel i5-8265U.

Although this is just a proof of concept and not something that could be already use in production, I think it proves the potential of Simple Tabulation to improve current Ruby implementation. It may be worthwhile to explore this idea further. What do you think?

I did this as part of a project for my Advanced Algorithms course. For more details check the project report:

Also available in: Atom PDF