Your Ad Here

Thursday, March 29, 2012

What type of search algorithm does Google use for their Hash tables?

Does Google use linear probing, quadratic probing, chaining, or a different algorithm when storing and searching for their data (in BigTable)?

Linear (Very fast with "strings attached")

Since Google has practically unlimited storage, linear probing with minimal collisions is the fastest to store and retrieve the data.
Input with a large hash table, and diverse data will accomplish an order of O(1), likewise when searching for data the order will be O(1).

Chaining (Very Stable)

However, with chain hashing, a Big-O of O(1) is guaranteed. A search of O(n) will always be the case when searching for the data in the "chain".

Quadratic (Eliminates clustering)

I would least likely expect Google to use Quadratic hashing since its great at minimizing clustering. An effect that occurs when too little of a hash table is implemented or it's too populated.

I would assume Google uses a linear probing technique. Am I wrong? Does Google use something different all together?