How to get a free entry in a C# dictionary

Question

I am running a server, and I would like to have a users dictionary, and give each user a specific number.

Dictionary<int,ServerSideUser> users = new Dictionary<int,ServerSideUser>();

The key represents the user on the server, so when people send messages to that user, they send them to this number. I might as well have used the users IP number, but that's not that a good idea.

I need to allocate such a number for each user, and I'm really not sure how to do so. Someone suggested something like

Enumerable.Range(int.MinValue, int.MaxValue)
.Except(users.Select(x => x.Key)).First();

but I really don't think it's the optimal way. Also, I have the same problem with a List (or LinkedList) somewhere else.

Any ideas?

Answer 1

If the size of the "number" doesn't matter, take a Guid, it will always be unique and non-guessable.

Answer 2

Why don't you keep track of the current maximum number and increment that number by one every time a new user is added?

Answer 3

If you want a dictionary that uses an arbitrary, ordered integer key, you may also be able to use a List<ServerSideUser>, in which the list index serves as the key.

Is there a specific reason you need to use a Dictionary?

Using a List<> or similar data structure definitely has limitations. Because of concurrency issues, you wouldn't want to remove users from the list at all, except when cycling the server. Otherwise, you might have a scenario in which user 255 sends a message to user 1024, who disconnects and is replaced by a new user 1024. New user 1024 then receives the message intended for old user 1024.

If you want to be able to manage the memory footprint of the user list, many of the other approaches here work; Will's answer is particularly good if you want to use ints rather than Guids.

Answer 4

Another option: Use a factory to generate ServerSideUser instances, which assigns a new, unique ID to each user.

In this example, the factory is the class itself. You cannot instantiate the class, you must get a new instance by calling the static Create method on the type. It increments the ID generator and creates a new instance with this new id. There are many ways to do this in a thread safe way, I'm doing it here in a rudimentary 1.1-compatible way (c# pseudocode that may actually compile):

public class ServerSideUser
{
  // user Id
  public Id {get;private set;}
  // private constructor
  private ServerSideUser(){}
  private ServerSideUser(int id) { Id = id; }

  // lock object for generating an id
  private static object _idgenLock = new Object();
  private static int _currentId = 0; // or whatever
  // retrieves the next id; thread safe 
  private static int CurrentId
  {
    get{ lock(_idgenLock){ _currentId += 1; return _currentId; } }
  }  

  public static ServerSideUser Create()
  {
    return new ServerSideUser(CurrentId);
  }
}

Answer 5

I think it depends on how you define the "uniqueness" of the clients.

For example if you have different two clients from the same machine do you consider them two clients or one?

I recommend you to use long value represents the time of connection establishment like "hhmmss" or even you can include milliseconds

Answer 6

I suggest the combination of your approach and incremental.

Since your data is in memory, it is enough to have the identifier of type int. Make a variable for the next user and a linked list of free identifiers.

When new user is added, use an Id from the list. If the list is empty — use the variable and increment it.

When a user is removed, add its identifier to the Dictionary.

P.S. Consider using a database.

Answer 7

First of all, I'd also start by seconding the GUID suggestion. Secondly, I'd assume that you're persisting the user information on the server somehow, and that somehow is likely a database. If this is the case, why not let the database pick a unique ID for each user via a primary key? Maybe it's not the best choice for what you're trying to do here, but this is the kind of problem that databases have been handling for years, so, why re-invent?

Answer 8

Why not just start from 1 and count upwards?

lock(dict) {
   int newId = dict.Count + 1;
   dict[newId] = new User();
}

If you're really concerned about half the worlds population turning up at your one server, try using long:s instead.. :-D

Answer 9

Maybe a bit brutal, but could DateTime.Now.Ticks be something for you? As an added bonus, you know when the user was added to your dict.

From the MSDN docs on Ticks...

A single tick represents one hundred nanoseconds or one ten-millionth of a second. There are 10,000 ticks in a millisecond.

The value of this property represents the number of 100-nanosecond intervals that have elapsed since 12:00:00 midnight, January 1, 0001, which represents DateTime..::.MinValue.