CODEWITHSUNDEEP
java
nikitha.vyas
nikitha.vyas

Reputation: 29

why and where do we use hashing?

why do we use hashing for search? what are advantages of using hashing over binary search tree?

Upvotes: 2

Views: 7456

Answers (4)

shikhar
shikhar

Reputation: 2469

Hash Tables are best for searching(=) if you have lower inserts and uniform slot distribution. The time complexity is O(n+k) - linear.

They are not a good idea if you want to do comparison operations (<, >)

Upvotes: 0

ayush
ayush

Reputation: 14568

Hashing means using some function or algorithm to map object data to some representative integer value. This so-called hash code (or simply hash) can then be used as a way to narrow down our search when looking for the item in the map.

If need to use an algorithm that is fast for looking up the information that you need then the HashTable is the most suitable algorithm to use, as it is simply generating a hash of your key object and using that to access the target data - it is O(1). The others are O(N) (Linked Lists of size N - you have to iterate through the list one at a time, an average of N/2 times) and O(log N) (Binary Tree - you halve the search space with each iteration - only if the tree is balanced, so this depends on your implementation, an unbalanced tree can have significantly worse performance).

Upvotes: 0

Nick
Nick

Reputation: 25799

Hashing is generally a constant time operation whereas a Binary Tree has a logarithmic time complexity.

Because a hash is calculated not based on the number of items in the collection but on the item being searched for, the size of the collection has no bearing on the time it takes to find an item. However most hashing algorithms will have collisions which then increases the time complexity so it's very unlikely to get a perfect constant time lookup.

With a binary tree, you have to do up to log2N comparisons before the item can be found.

Upvotes: 5

Kajetan Abt
Kajetan Abt

Reputation: 1545

Wikipedia explains it well:

http://en.wikipedia.org/wiki/Hash_table#Features

Summary: Inserts are generally slow, reads are faster than trees.

As for Java: Any time you have some key/value pair that you read a lot and write not very often and everything easily fits into RAM, use a HashTable for quick read accesses and incredible easy of code maintenance.

Upvotes: 3

Related Questions