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.

  • 1
    What programming language? Different languages have different available data structures. In Java, for example, I would recommend using a HashMap. – 4castle Apr 28 '16 at 3:19
  • Not specific to any particular programming language. I am just curious about the logic to it. – NPE Apr 28 '16 at 3:21
  • 2
    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. – 4castle Apr 28 '16 at 3:26

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.