Re: Data structure query
- From: Alex Fraser <me@xxxxxxxxxxx>
- Date: Sun, 23 Nov 2008 08:47:32 +0000
mysorepushpa@xxxxxxxxx wrote:
I have a specific requirement in which I have thousands of key-value
pairs which needs to be stored and
retrieved in alphabetical order. Which data structure can I use for
the same. Which is the best data-structure to use both in terms of
space to store and also the time required to retrieve given a key the
corresponding value.
Insufficient information. Questions that spring to mind:
Are the key/value pairs static, or do they need to be added/removed dynamically?
Are the keys and values of fixed or variable size?
Will the keys or the key/value pairs fit in memory?
I will guess that the keys are strings (hence variable length), and that "alphabetical order" refers to the keys. I will assume that the values are also of variable length, and that the data structure is static and entirely in memory.
An array of {pointer to key, pointer to value} sorted by key would allow ordered retrieval, as well as binary search to find a value given the key with minimal space overhead.
This could be augmented with a simple hash table using open addressing and storing pointers to the array. This may give better lookup performance at a cost of, say, two pointers per item (ie table 50% full).
Alex
.
- References:
- Data structure query
- From: mysorepushpa
- Data structure query
- Prev by Date: Re: Lock-free reference counting
- Next by Date: Re: in need of help
- Previous by thread: Data structure query
- Next by thread: Re: Data structure query
- Index(es):
Relevant Pages
|
