What is the meaning of "breaking ties in the left"?

Question

When I learned d-left hashing, I met a sentence "Place item in a cell in the least loaded bucket, breaking ties to the left. " I can't understand  the meaning of "breaking tie to the left". Who can explain it to me? Thank you very much!

Clive · Accepted Answer

I take it to mean this.
If both buckets are equally loaded, it is called a tie. In such a case, the tie is resolved (ie broken) by putting the key-value pair in the left half of the table.

Clive

The following details are excerpted from
http://www.pvk.ca/Blog/numerical_experiments_in_hashing.html

The idea behind d-left hashing is simple. Insertions work as follows:

Split our hash table in d equal sections (typically two, the left and the right halves), and order the sections from left to right arbitrarily.
Associate d independent hash values to the key, h_1, h_2, ... h_d.
Use the d hash values to find a bucket in each section of the hash table, and put the key-value pair in the least loaded bucket; break ties not randomly, but by taking the bucket in the leftmost section (as per the arbitrary ordering established in 1.).

Li Hang · Answer

Thank you very much!

What is the meaning of "breaking ties in the left"?

Top answer

Get the Weekly English Kit 📬