How to map collection of unique large numbers to an array?

Question

I have a list of unique 8 byte random ids and new ids are generated often. Let's say that the total number of ids can become at most N (let's say 100,000). Now, I want to map each of these ids to a unique position in an array of size N. What is the best way to map it?

Context: I was reading about how instant chat messaging systems like facebook/skype/googlechat keep track of presence and apparently, they just maintain one large array and index it based on user id which is a 8 or 16 byte unique random id.

• castletheperson: What programming language? Different languages have different available data structures. In Java, for example, I would recommend using a HashMap.
• NPE: Not specific to any particular programming language. I am just curious about the logic to it.
• castletheperson: Okay, well in general the data structure you should use is an associative array (one that doesn't use index numbers, but instead key/value pairs). I don't think this question is appropriate for this site though. The "Programmers" stack exchange would be better for "conceptual" questions.

Answer 1

Unless there has been a generator function which mapped all integers from 0 to 100,000 to the corresponding IDs (which I suppose you don't, as you said they are random), your best call is a regular hashmap. Storing them in a flat array will otherwise involve a lot of data movement whenever you insert new IDs.

Second best option is to ditch the idea of using a plain array, but use a data-structure which is better suited for random inserts, such as a linked list. Refinements, such as the skiplist, also work well in your case, as you are only ever adding new values, but not removing.