Difference between array and Hashtable or HashMap in Java

A couple of days back someone asked me about the difference between an array and a hashtable, though this is a generic data structure and programming question, I'll answer it from both a general programming perspective as well on Java perspective where Hashtable is not just a data structure but also a class from Java Collection API. Even though both array and hashtable data structure are intended for fast search i.e. constant time search operation also known as O(1) search, the fundamental difference between them is that array require an index while hash table requires a key which could be another object. 

Actually, the hash table is an extension of the array where the hash function is used to convert the key into an index required by the array, which is further used to locate the element in the internal array. Yes, a Hashtable or HashMap is also backed by an array, but that's not the full story. 

It also uses a linked list and binary tree data structure to deal with collision and maintain acceptable performance. In this article, you will learn about both structural and performance differences between array and hashtable in Java. 

Let's now compare array in Java with the Hashtable or HashMap class in Java. Most of the differences are also valid for general array vs hash table data structure in computer science programming. Hash table data structure is also known as dictionary in Python and Map in many other programming languages. 

Difference between Array vs hash table in Java

Now, let's see some more details to understand the difference between Array and Hashtable in Java: 

1. Index based vs  Key Based

The first and foremost difference between a hash table and the array is that array needs an index while the hash table needs a key to search the value. 

2. Fixed Capacity vs Dynamic Capacity

The second difference is that array has a fixed capacity but the hashtable can accommodate more elements than the capacity on the internal array by using chaining and a linked list. 

3. Performance

The third difference between a hash table and the array is that the array always gives you O(1) performance if you know the index but hash table performance can be O(n) in the worst case where due to collision you need to traverse through linked list to find the correct value object. 

This has been slightly improved now when JDK uses binary tree instead of linked list from Java 8 and worst-case performance is now pegged to O(logN)

4. Usage

 Array stores just one object but the hash table stores mapping, I mean pair of key and value objects. 

5. Sorting

Array doesn't enforce any requirement on storing objects but hash tables usually require the key object to implement some interface so that it can calculate hash values. For example, in Java, we have Hashtable and HashMap classes in java.util package which is our general-purpose hash table data structure requires key objects to implement equals() and hashcode() method.

6. Collision

There is a collision in the array but collision is possible in the hash table

7. Synchronization

the array is not synchronized and cannot be made synchronized but Hashtable is synchronized in Java.

Similarities

Now that we have seen some differences between array and hash table data structure, now let's see some similarities. 

1. both are linear data structure

2. hashtable is internally backed by an array

3. both provide fast search performance when a search is by key or index.  

That's all about the difference between array and hash table data structure in Java. I have used the Hashtable class as a representative of hash table data structure in Java but you can put HashMap, ConcurrentHashMap or any other Map implementation in place of Hashtable and most of the differences will be valid. 

If you like this article and would like to try out a couple of more challenging programming exercises, then take a look at the following programming questions from various Interviews :

More Java and Data Structure Interview Questions you may like

• 20+ Array-Based Coding Problems for programmers (list)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• 100+ Data Structure Coding Problems from Interviews (questions)
• Recursive InOrder traversal Algorithm (solution)
• Postorder binary tree traversal without recursion (solution)
• Recursive Post Order traversal Algorithm (solution)
• How to print leaf nodes of a binary tree without recursion? (solution)
• 75+ Coding Interview Questions for Programmers (questions)
• Iterative PreOrder traversal in a binary tree (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (list)
• 5 Books to Learn Data Structure and Algorithms in-depth (books) 
• How to print all leaf nodes of a binary tree in Java? (solution)
• 7 Courses to learn Data Structure and Algorithms (courses)
• How to implement a binary search tree in Java? (solution)
• 7 Free Books to learn Algorithms and Data Structure? (books)
• How to implement a recursive preorder algorithm in Java? (solution)
• 20+ Binary tree-based coding problems for programmers (list)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)

Thanks for reading this coding interview question so far. If you like this difference between array and hash table data structure then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these best data structure courses in Java. It contains the best courses Java programmers can take to build their DS and Algorithms skills.