Possible Duplicate:
How does Java hashmap work?
Can someone explain to me how HashSets in java work and why they are faster than using ArrayLists?
Asked
Active
Viewed 4.3k times
20
-
2Whether it's faster depends entirely on what you use it for. A HashMap
will never be able to look stuff up by index faster than an ArrayList – cHao Feb 02 '12 at 20:55, for example. It's manipulation of the collection that *can be* faster, but even that is dependent on how you add stuff. -
Pick up a good book on data structures and algorithms, such as *Introduction to Algorithms*, and read about hash tables. – Kerrek SB Feb 02 '12 at 20:55
-
http://docs.oracle.com/javase/tutorial/collections/ – JSager Feb 02 '12 at 20:55
-
A HashSet and an ArrayList are two entirely different things. – Hot Licks Feb 02 '12 at 20:55
-
Java has a documentation type called [The API Reference](http://docs.oracle.com/javase/6/docs/api/). Here is the documentation for [HashSet](http://docs.oracle.com/javase/6/docs/api/java/util/HashSet.html) and here is the documentation for [ArrayList](http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html). Reading is fundamental. – DwB Feb 02 '12 at 20:58
-
Just a reminder that if you want to actually drill down to the code, you can; it's publicly available. – DPM Feb 02 '12 at 21:00
4 Answers
22
A HashSet is actually a HashMap where the value is always the same.
The way a HashMap works is described in many places (it is referred to as "hashtable" as well). In short: it generates hashes of keys (objects) and positions them into a table. Then each time you look for a key, its hash is computed and the bucket in the table is referenced directly. This means you have just one operation (best case) to access the map.
The HashSet simply contains the keys, so .contains(..) is O(1). That and remove(..) are the only operations a HashSet is faster than an ArrayList (which is O(n)). Iteration is the same, addition is the same.
-
Just to add to the descriptive answer, Iteration should be O(n) and addition should be of O(1) time complexity, just like a HashMap. A nice concept to check is re-hashing where more data is to be stored in the data structure (checked with load factor) and hence bigger table has to be created for the same, thus resulting in increasing average insertion time. – Bhavesh Agarwal Sep 30 '14 at 17:19
15
First, HashSet, unlike ArrayList is a Set: It cannot contain duplicates while ArrayList can - so they are built for different purposes. It also does not guarantee ordering - again, unlike a list.
Second - a HashSet is built on the hash table data structure, that allows O(1) seek time for an element.
Note that many times, a HashSet is slower then an ArrayList - if you want to iterate on elements for example - usually doing it in an ArrayList will be faster then in a HashSet [because of bad cache performance of hash, among other reasons]
Adil Shaikh
- 44,509
- 17
- 89
- 111
amit
- 175,853
- 27
- 231
- 333
3
These are 2 different data structures.
The concept behind HashSet is key probing.
I.e. you use a transformation of the input key to get an index of the location of the value in an array.
This is a constant O(1) operation since an array allows random access.
The arraylist is also O(1) operation for access since it is also backed by an array.
But only for random access and insertion.
The search though is O(N) operation for an arraylist since you have to search through all the elemements in the list to get to the value unlike the HashSet where you just transform the key and access the array. Search in a HashSet is O(1)
Cratylus
- 52,998
- 69
- 209
- 339
1
As a matter of fact, for example iterating over and appending to an ArrayList is faster.
And heck, you cannot even sort a HashSet.
But the fastest of all is the NoOp. There is nothing just remotely as fast as the NoOp. Granted, it doesn't do much, the NoOp. But it's really fast at that!
You need to be more precise in what you consider to be "faster than".
Has QUIT--Anony-Mousse
- 76,138
- 12
- 138
- 194