Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fastest data structure for contains() in Java?

What's the data structure in Java that has the fastest operation for contains() ?

e.g. i have a set of numbers { 1, 7, 12, 14, 20... }

Given another arbitrary number x, what's the fastest way (on average) to generate the boolean value of whether x is contained in the set or not? The probability for !contains() is about 5x higher.

Do all the map structures provide o(1) operation? Is HashSet the fastest way to go?

like image 530
codechobo Avatar asked Jul 16 '10 17:07

codechobo


People also ask

Which data structure is fastest in Java?

1- in current scenario, if concurrent users are not a concern then you can easily go for arraylist as its faster simpler data structure else if concurrent users are the concern then you can easily go for vector to store your events.

Which data structure is best in Java?

Arrays. An array is the simplest and most widely used data structure. Other data structures like stacks and queues are derived from arrays.

What is the best data structure for fast retrieval of data?

The best data structure I can think is of using the TreeSet. Here is the code, how you should define the structure. One more info- Use hashcode method of your URL class as hashcode of your url. This is how you define URLComparator class.


3 Answers

look at set (Hashset, enumset) and hash (HashMap,linkedhash...,idnetityhash..) based implementations. they have O(1) for contains()

This cheatsheet is of great help.

like image 109
Aravind Yarram Avatar answered Oct 19 '22 20:10

Aravind Yarram


For your particular case of numbers with a relatively high density I'd use a BitSet, it will be faster and much smaller than a hash set.

like image 24
starblue Avatar answered Oct 19 '22 20:10

starblue


The only data structure faster than HashSet is likely to be TIntHashSet from Trove4J. This uses primitives avoiding the need to use Integer Objects.

If the number of integers is small, you can create a boolean[] where each value present is turned into a "true". This will be O(1). Note: HashSet is not guarenteed to be O(1) and is more likely to be O(log(log(N))).

You will only get O(1) for an ideal hash distribution. However, it is more likely you will get collisions of hashed buckets and some lookups will need to check more than one value.

like image 5
Peter Lawrey Avatar answered Oct 19 '22 20:10

Peter Lawrey