CODEWITHSUNDEEP
hashtable
Minkyu Kim
Minkyu Kim

Reputation: 21

HashTable vs. Array

I have been working with Java, but in general, what's the advantage of saving elements in a hash table when we have an array?

In my understanding, ff we have arr[100], then accessing i-th element is O(1) since it's just addition of (arr type) * (i) to the base pointer of arr itself. Then how is hashtable useful and when would it be useful as opposed to array? Is

Thank you

Upvotes: 2

Views: 1726

Answers (1)

Amir Omidi
Amir Omidi

Reputation: 339

In Java you should be using HashMaps. The Object class in Java has a int hashcode method where it creates a unique number for the object in mind.

For example, this is the hashcode of a String in java.

In hashmaps you can assign a value to a key. For example, you could be doing: <Username(String), Customer(Custom Object)>. With arrays, to find a specific Customer (If you don't know the index) you would have to go through the entire array (O(n)) in the worst case to find that. Without hashmaps, and using some more search optimized data structures like Binary Search Trees, it would take log(n) time (O(log n)) time to find the customer.

With a hashmap, you can get the customer's object immediately. Without having to go through the entire collection of the customers.

So basically, hashmaps "Map" a "hash" integer value to a key, and then use that key to find the value.

Also just as a bonus, remember since we're putting larger information inside a small integer, we will be facing the so called "hash collision" where two keys have the same hash value but they're not the same actual things. In this case we're obviously not going to find the information instantly, however again, instead of having to search for all the records to find our specific one, we just need to search a smaller "bucket" of values which is substantially smaller than our actual collection.

Upvotes: 2

Related Questions