`Hash` Set and Array List performances
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.
Overview
Understanding data structures is fundamental for efficiently solving problems and optimizing algorithms in software development. Two commonly used data structures in Java are HashSet and ArrayList. Both have unique characteristics that make them suitable for different types of tasks. This article will delve into the technical details of HashSet and ArrayList, examining their performance, use cases, and how they operate under the hood.
HashSet
HashSet is part of the Java Collection Framework and implements the Set interface. It is designed to store unique elements, meaning it does not allow duplicates. Here's a detailed look at its properties and performance characteristics:
Characteristics of HashSet
- Underlying Structure: The
HashSetuses a hash table. Elements are stored in buckets based on their hash code. - Order: Does not guarantee any order of elements. The order can change over time as elements are added and removed.
- Null Values: Allows one null element.
- Duplicates: Automatically handles duplicate checks based on hashcode and equals() method.
Performance
- Time Complexity:
- Add: on average. Collisions may degrade performance to in the worst case.
- Remove: on average.
- Contains: on average. Effective due to direct access via hash codes.
- Storage: Higher memory usage due to storing hash codes and linked lists/buckets.
Use Cases
- When you need a collection of unique elements.
- Quick lookup, insertion, and deletion operations are essential.
- Order of elements is not important.
Example
- Underlying Structure: Based on a dynamically resized array.
- Order: Maintains the order of insertion.
- Null Values: Allows multiple null elements.
- Duplicates: Permits duplicate elements.
- Time Complexity:
- Add: (amortized), in the worst case when resizing.
- Remove: . If elements are shifted post-removal.
- Get: for accessing elements by index.
- Contains: when searching for an element, as it needs to search linearly.
- Storage: Slightly more efficient in terms of space compared to
HashSet. - Maintaining ordered collections where duplicates are allowed.
- Efficient random access or iteration through elements.
- Suitable for indexing operations where you need to retrieve elements based on their position.
Related reading
- \`Hash\` table - why is it faster than arrays?
- Hash table runtime complexity insert, search and delete
- \`Hash\` table vs Balanced binary tree
- `Hash` Table Why deletion is difficult in open addressing scheme
- Hashing of pointer values
- HashMap get/put complexity
- HashMap - contains and get methods should not be used together
- HashMap - getting First Key value

DSA Fundamentals
Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.
View the courseTrack what you have practised
A free account saves your progress, solutions and study plan across every problem on Codemia.
Data Structures & Algorithms practice on Codemia
Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.