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?

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.

• Sep 20th, 2008

Binary tree

• Sep 23rd, 2008

One Million Named Objects:

1. I dont think binary Tree is a good idea. Depth of the tree will be huge
2. B+ Tree is the right Data structure

veerun14 Profile Answers by veerun14 Questions by veerun14

• Sep 24th, 2008

Since the objects are named, I would go for the hash table.

• 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-| | ...

• 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

• Oct 23rd, 2009

The ultimate solution for this is TRIE or advanced TRIE

• Oct 26th, 2009

AVL trees

• Mar 5th, 2010

B tree will be most suitable.  B+ is not because the requirement is not sequential search.

• 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.

• 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.

3.

4. Then create array to contain objects (gradebooks):

5.