CODEWITHSUNDEEP
javaalgorithmdata-structures
ghost
ghost

Reputation: 365

A single data structure to store object that has different search parameters

So I have a list of objects, say a list of Students with variables like username, roll number, standard, division, etc.

I am looking out for a data structure that can store student objects and also allows search on any of the above variables. The time complexity is the key part here as there will be thousands of the searches done on the data.

Ex: If I use Binary Tree, then I can take a hashcode of the any variable say, username and then take an index out of it and store the student object in the Binary Tree. However, this has a limitation, as say if I want to search the student on the standard then it is not possible as the index at which the Student is stored in the Binary Tree was generated from username.

Is there any data structure, that can allow storing student once and also allows searching student on the different variables. OR Any hybrid data structure that can be created to fulfill the requirement.

I'd like to achieve a time complexity of O(1) at best else O(log n).

Upvotes: 0

Views: 773

Answers (3)

nullptr
nullptr

Reputation: 580

If you want to find all students that have a particular roll number or particular standard, then you could maintain a many hashmaps to students:

HashMap<Standard, List[Student]>
HashMap<RollNumber, List[Student]>
HashMap<Username, Student>        (assuming usernames are unique)

For some fields (e.g. roll number, standard) that are just integers, you could use an array instead of a HashMap.

However, if you want to find to support queries like "find all students in a standard 5 whose roll numbers are between 5 and 10", then you'd have to do a lookup in two hashmaps and intersect the values.

If you want these operations to be quick, k-d trees might help.

Upvotes: 1

litttle fish
litttle fish

Reputation: 41

Considering username, roll numbers are unique for every student and standard, divisions can be shared by multiple students.

You can work out a solution in fallowing manner to achieve the O(1)/O(log(N))/O(N) depending upon the cases.

Lets define the class structure first :

class Student{

  // Considering all the variables to be string. You can change them according to your use cases.

  String username;

  String rollNumber;

  String standard;

  String division;

}

Lets create some maps to store these students

Map<String, Student> usernameMap; // username to object map

Map<String, Student> rollNumberMap; // roll number to object map

Whenever any Student objectis created you add those respective Maps.

Incase you want to find out all the Students in any given standard/division,

you can keep the another mapping for standards and divisions also.

Something like ->

Map<String, Set<String>> standardMap; // standard to set of student's username/rollnumber.

you can create similarly map for divisions.

Upvotes: 0

Daniel
Daniel

Reputation: 7724

If I were to do this, I would create an array of Students, where the index of each Student would be its ID.

Then, I would create a HashMap<String, Integer> to map the username to an ID, another HashMap<Integer, Integer> to map roll number to an ID, etc.

Upvotes: 0

Related Questions