• Post Reply Bookmark Topic Watch Topic
  • New Topic

efficient structure to support searches, inserts and deletes

 
Veda Dhawad
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,
In my application i am having an output array which undergoes following operations repeatedly :search,insert and delete.
Please suggest an efficient structure to support searches, inserts and deletes.Since the array is dyamically generated at present i am using Vector for this.But this is hampering the performance.
Please suggest the useful data structure for this array.
Thanks,
Rutuja
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are a number of structures which support searches, insertion, and deletion. Usually choice of data structure is dependent on more than just the type of operations you'd like to be able to perform, but most of the time HashSet or TreeSet work just fine.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I agree with David. For example, HashSet probably is faster than TreeSet (provided you have a good hashcode implementation), but TreeSet sorts the elements and probably also consumes less memory.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
BTW, it also depends on the size of your data. Many of the "fast" algorithms are actually less than optimal for small data sets.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'd note that you're probably going to be needing Maps rather than Sets. HashMap is best for looking up an abject using a key, if you know the complete key. TreeMap is slower but has the advantage that since it sorts the keys you can find a range of results. E.g. to find all keys that start with "foo" you search for all keys >= "foo" and < "fop" - you will get "foo" and "foobar" and "fool". If that type of search is what you need, use TreeMap. If you want to search for records that contain a given string (not just at the beginning of the key) - Maps probably won't help, and you probably need to do either a comparatively slow but simple linear search, or use a sophisticated indexing algorithm of some kind.
You may also find it useful to have a solution with multiple maps, if you want to be able to execute different types of searches on the same set of records.
You'll also need to consider - how much data is there? Will you have enough memory to keep all these keys and records in memory? If not, you may find it useful to use a file-based DB instead. HSQL is a relatively simple option to use here if you aren't already conversant in setting up a DB.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!