Saturday, August 4, 2012

ArrayList vs LinkedList vs HashSet Performance Comparision



Conclusions

Inserting & Reading sequentially from Collection prefer LinkedList/ArrayList

Inserting & Reading/Deleting by Search/equals from Collection prefer HashSet

Inserting, ArrayList & LinkedList performs best while HashSet takes double the time

Reading, HashSet performs best while ArrayList & LinkedList are marginally less

Deleting, HashSet performs 10 times better than ArrayList & ArrayList performs 4 times better than LinkedList. LinkedList is slow because of sequencial search

Bottom line : unless you are not going to iterate using for(Integer i : list ) then prefer HashSet


Inserting/Reading/Deleting integer's from zero till count

JDK7Collectionactioncounttime ms
ArrayListInsert1000/1
LinkedListInsert1000/1
HashSetInsert1000/1
ArrayListInsert100005
LinkedListInsert100004
HashSetInsert100007
ArrayListInsert10000011
LinkedListInsert10000011
HashSetInsert10000021
ArrayListGet/Read1000
LinkedListGet/Read1000
HashSetGet/Read1000
ArrayListGet/Read100004
LinkedListGet/Read100003
HashSetGet/Read100004
ArrayListGet/Read10000010
LinkedListGet/Read10000010
HashSetGet/Read1000009

JDK6Collectionactioncounttime ms
ArrayListInsert1000/1
LinkedListInsert1000/1
HashSetInsert1000/1
ArrayListInsert100005
LinkedListInsert100004
HashSetInsert100007
ArrayListInsert10000012
LinkedListInsert10000011
HashSetInsert10000017
ArrayListGet/Read1000
LinkedListGet/Read1000
HashSetGet/Read1000
ArrayListGet/Read100005
LinkedListGet/Read100003
HashSetGet/Read100004
ArrayListGet/Read10000010
LinkedListGet/Read10000010
HashSetGet/Read1000009

JDK6Collectionactioncounttime ms
ArrayListinsert & remove 25%100000336
LinkedListGet/Read1000001188
HashSetGet/Read10000025

JDK7Collectionactioncounttime ms
ArrayListinsert & remove 25%100000337
LinkedListGet/Read1000001208
HashSetGet/Read10000032

Environment

MacBook Pro

Processor 2.3 GHz Intel Core i7

Memory 16 GB 1600 MHz DDR3

Software OS X 10.8 (12A269)