• Post Reply Bookmark Topic Watch Topic
  • New Topic

Data Structure that provides constant search time  RSS feed

 
Nimmy
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have an array of numbers(long).
The complexity of search in a number in this case is O(n).
I am looking for a Data Structure which provides constant search time.
 
Tom Blough
Ranch Hand
Posts: 263
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
While you can get searches to run in O(1) in the best case (i.e. already sorted data), the best average case search you can do is O(log n).
Cheers,
[ April 14, 2005: Message edited by: Tom Blough ]
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Take a look at java.util.HashSet. It actually provide O(1) searches, with good implementations of hashCode().
[ April 14, 2005: Message edited by: Ilja Preuss ]
 
Mark Spritzler
ranger
Sheriff
Posts: 17309
11
IntelliJ IDE Mac Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"Mariya"-
Welcome to the JavaRanch! Please adjust your displayed name to meet the

JavaRanch Naming Policy.

You can change it

here.

Thanks! and welcome to the JavaRanch!

Mark
 
Layne Lund
Ranch Hand
Posts: 3061
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Tom Blough:
While you can get searches to run in O(1) in the best case (i.e. already sorted data), the best average case search you can do is O(log n).
Cheers,

[ April 14, 2005: Message edited by: Tom Blough ]


This is true only if you are using a list. Other data structures, as Ilja pointed out, can provide O(1) search time. Under the hood, HashSet probably uses a hashtable, which is a fairly common data structure. If you need to implement your own hashtable, then you should google for more information on it. You should also become familiar with the data structures that are already available in the Collections Framework.

Layne
 
Nimmy
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for your responses.


I think my question was not clear.
I need to store primitive types (array of long values).
In collection framework we are using objects.
I don�t want to convert long to an object of wrapper class and save it.
Collection framework provides us that facility to look for a particular value in a better way.

I have a long array and I want to look for a particular value in that array.
Can you suggest me one way to accomplish?
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For a search in an array, Tom's response applies - O(log n) is the best you can get. For that, your array needs to be sorted, then you can simply use Arrays.binarySearch.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!