CODEWITHSUNDEEP
javadata-structures
Arkantos
Arkantos

Reputation: 6608

New Data structure to store key value pairs

I've a data set like below

attr1=val1  | attr2=val2  | attr3=val3  | attr4=val4  | attr5=val5,
attr1=val21 | attr2=val22 | attr3=val23 | attr4=val24 | attr5=val25,
attr1=val31 | attr2=val32 | attr3=val33 | attr4=val34 | attr5=val35,

key and value delimited by = and | (changed from space to avoid confusion) is delimiter for pairs. I can take care of parsing / tokenizing the input but my concern is in storing the data. I'm looking for a data structure (preferably in java) that can hold these list of pairs in each row in a key-value pair fashion.

Goals and Assumptions :

  1. Input Key will be unique - there won't be any duplicate key, so hash code might be used in design if it helps constant lookups, no need to handle hash code collisions
  2. Value should be accessible in constant time by passing key as input
  3. No of pairs in a line is always same so no need to bother about dynamic re- size of the data structure
  4. we'll be accessing one row at time using key and get the corresponding value

Note :- I'm already aware of HashMap and its internal implementation in java. I'm just trying to avoid the structural overhead for this particular type of data set :)

The intent is to get the value of any attribute in a given row in a constant time by passing key. I'll be dealing with ONLY ONE row at a time and I want to get the value of say attr1 in that row and if it's true do something. Hope this makes it clear.

I've only two ideas

  1. Using HashMap is the most obvious solution

  2. Having a list of Pair objects with key,value as instance variables and do a binary search in the sorted list which is O(logn) + some time for the equals check

    I'm looking if there's a better way than this :) Any ideas / thoughts on this ?

Upvotes: 0

Views: 1904

Answers (3)

Nagappan
Nagappan

Reputation: 356

Assuming there will be known set of keys and keys in each row will be in same order. If it is not in same order, while parsing and creating the data structure, please place it in the same order. enter image description here

Upvotes: 0

gknicker
gknicker

Reputation: 5569

Assuming your keys are always the same, the most efficient solution is to create classes to represent each type of data.

public class Type1 {
    private String attr1;
    private String attr2;
    // etc
}

If for some reason you cannot represent the data types as classes, use a java.util.Map implementation with fixed keys, such as java.util.EnumMap.

Upvotes: 1

stevebot
stevebot

Reputation: 24005

What structural overhead? HashMap will give you the constant time lookups, you don't care about resizing, and plus you do not have to write/test the implementation as its already been done.

I've used HashMap in dozens of applications and unless you are dealing with massive scale I don't see any reason for you to roll your own implementation or go searching for another.

I should add as well that using common structures makes your code more accessible to others. Most Java developers understand the SDK HashMap implementations and its trade-offs. If they come across your own implementation or some other libraries implementation, they will have to go through the process of re-learning what the structure is and what the trade off's are.

Upvotes: 3

Related Questions