Suggestion of datastructure for a business requirement

Question

My record structure is as below:- (Name,Option,StartNum,EndNum,Vacancy)

Name,Option,StartNum,EndNum form the composite keys of the sturcture/table. So for a given combination of these, there would be only one Vacancy record.

Sample Records

ABC,X,2,14,1
ADE,X,3,8,0
AEF,Y,1,12,2
ERF,X,12,13,17

There could be:

1. 250-300 Names

2. For each Name 20-30 Options

3. For each Option 1-45 StartNum

4. For each StartNum 1-14 EndNum

5. For each combination of above entries, there would be only one entry for Vacancy.

So there could be maximum of 5,670,000 (300*30*45*14) entries

Fast operations to support

1. Search on the composite key i.e. (Name+Option+StartNum+EndNum) and fetch it's Vacancy record value
2. For a given Name,Option and a Number, search and delete records having the given Name,Option and StartNum<=Number<=EndNum

Can anyone please suggest the appropriate datastructure for my above requirement. The data structure building operation can be slow as its done offline, but the above mentioned two operations should be very very fast.

Thanks,
Harish

Answer 1

I would create a hash-map based on the tuple (Name, Option). For each of the combinations of those two, there could be a simple list, ordered by (StartNum, EndNum). Inserting into that list would be O(N) in its size, but you know that size is quite small. Another option would be some balanced binary search tree or a skip list.

If you had a good hash (which shouldn't be hard, the standard ones should work), the time complexity for retrieval would be O(1 + log(|StartNum| * |EndNum|)).

When searching as per 2., you check all values that have StartNum <= Number whether they have matching EndNum.

Answer 2

A hash-map should serve your purposes pretty well. You just have to figure out how to create a good hash for the composite key. If you already have hashes for the individual items, you can combine these using a simple XOR.