0

I want to know usage of Hashing in Searching. For example does Google or Yahoo uses Hash Algorithms? Does big companies use this Hashing Algorithm?

berkc
  • 525
  • 3
  • 9
  • 21
  • I think it's fair to say that any non-trivial piece of software uses hashing in some way or another (not least because many commonly-used standard containers/collections use hash functions internally). – NPE Dec 25 '14 at 07:29

1 Answers1

2

Yes. Refer to book Page rank and beyond , there you will find that google uses hashing.Hashing make your complexity too low in all aspect like searching,adding etc.Let me tell you a situation suppose you are making an online chatting website.And you have to handle a million users.you can use linear search which will take worst time around 1 million*time to fetch one element.The user will have to wait a lot on the client side.But you will save money as you are not using extra space complexity.But if you will use hashing time taken will be around the time to fetch only one element.But here the system will cost you a lot as you have to pay for extra storage (1 million data storage records with a better hashing function).But here the challenge is to have a best hashing function that can cause minimum collisons to store elements.Hashing is a big topic I cannot explain in short. refer to these links:

What is a good Hash Function?
http://en.wikipedia.org/wiki/Hash_function
http://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson11_2.htm
http://www.tutorialspoint.com/dbms/dbms_hashing.htm
http://www.internetlivestats.com/total-number-of-websites/

Google links trillions of websites, about 1156000000.let us assume 1 milli second in getting one page from db.In worst case it will take around 1156000000*1 ms= 1156000 sec = 5.35 years. The user in worst case will have to wait for 5 years to search.Therefore this cannot be done in simple linear search.Google have its own hidden complex algorithms(you can find in the book above).Google have its own servers to store the hashing records, from where the records will be fetched by using some hashing functions.I doesn't have much idea about how google works.What I know is google uses probability a lot.Find in this book about how google works - http://langvillea.people.cofc.edu/UIUC.pdf

Community
  • 1
  • 1
Saurabh Saluja
  • 190
  • 1
  • 9