Whats the best data-structure for storing 2-tuple (a, b) which support adding, deleting tuples and c

Posted by bhups on Stack Overflow See other posts from Stack Overflow or by bhups
Published on 2010-04-15T07:39:39Z Indexed on 2010/04/15 7:43 UTC
Read the original article Hit count: 230

Filed under:

algorithm

|

complexity

|

datastructure

Hi
So here is my problem. I want to store 2-tuple (key, val) and want to perform following operations:
- keys are strings and values are Integers
- multiple keys can have same value - adding new tuples
- updating any key with new value (any new value or updated value is greater than the previous one, like timestamps)
- fetching all the keys with values less than or greater than given value
- deleting tuples.
Hash seems to be the obvious choice for updating the key's value but then lookups via values will be going to take longer (O(n)). The other option is balanced binary search tree with key and value switched. So now lookups via values will be fast (O(lg(n))) but updating a key will take (O(n)). So is there any data-structure which can be used to address these issues?
Thanks.

© Stack Overflow or respective owner

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More

Related posts about complexity

Linear complexity and quadratic complexity

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm just not sure... If you have a code that can be executed in either of the following complexities: A sequence of O(n), like for example: two O(n) in sequence O(n²) The preferred version would be the one that can be executed in linear time. Would there be a time such that the sequence… >>> More
When should complexity be removed?

as seen on Programmers - Search for 'Programmers'
Prematurely introducing complexity by implementing design patterns before they are needed is not good practice. But if you follow all (or even most of) the SOLID principles and use common design patterns you will introduce some complexity as features and requirements are added or changed to keep… >>> More
Using Completed User Stories to Estimate Future User Stories

as seen on Programmers - Search for 'Programmers'
In Scrum/Agile, the complexity of a user story can be estimated in story points. After completing some user stories, a programmer or team of programmers can use those experiences to better estimate how much time it might take to complete a future user story. Is there a methodology for breaking down… >>> More
Finding complexity of a program as a service [on hold]

as seen on Programmers - Search for 'Programmers'
I would like to find the complexity of a specific code chunk written in Java. Is there a place/web site/service where I can find out the complexity of any arbitrary program. This program might include loops/recursion. Using theory we can compute complexity ourselves. But, just curious in finding… >>> More
Form, function and complexity in rule processing

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
Tim Bass posted on ‘Orwellian Event Processing’. I was involved in a heated exchange in the comments, and he has more recently published a post entitled ‘Disadvantages of Rule-Based Systems (Part 1)’. Whatever the rights and wrongs of our exchange, it clearly failed to generate any agreement or understanding… >>> More