Data Structure for one million named objects

If you have one million named objects and you want to store them in a data structure that lets you insert new objects quickly and search for an object by name quickly, what data structure should you use?

Questions by bitsbyter

Editorial / Best Answer

hrshksh  

  • Member Since May-2010 | May 9th, 2010

It depends on the amount of primary memory one has for the process. If we can store 1 million records in primary memory, then we can very well take a hash table with a consistent hashing scheme for avoiding collisions. It will take O(1). 


In most cases however this is not possible. In circumtances like this, there are two ways:
B Trees or Extensible Hashing both of them have interesting time complexities.


Showing Answers 1 - 10 of 10 Answers

katrin.shechtman

  • Apr 1st, 2009
 

I think the most suitable here will be a dictionary solution - the
tree where each node contains a letter. And each name will be a word
in such a dictionary, so we need the node also contains the sign that
there is a name ends here (let's say -|). For example:


N  | M | ...
I | O I | ...
K-| | L K-| | ...

| L | ...


| Y-| | ...


  Was this answer useful?  Yes

nirmo420

  • Apr 3rd, 2009
 

Since there is the question about serching and insertion quickly, i think the data structure should be binary serach tree , not simple binary tree

  Was this answer useful?  Yes

hrshksh

  • May 9th, 2010
 

It depends on the amount of primary memory one has for the process. If we can store 1 million records in primary memory, then we can very well take a hash table with a consistent hashing scheme for avoiding collisions. It will take O(1). 


In most cases however this is not possible. In circumtances like this, there are two ways:
B Trees or Extensible Hashing both of them have interesting time complexities.


  Was this answer useful?  Yes

ptmich

  • May 28th, 2012
 

You can use a hash table or an array of objects

You can use an array of objects because you already know that you need to store a specified number of objects, also you can store and access objects quickly in an array of objects.

First declare the object:

Code
  1.  


  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions