最近看到一道经常出现的设计题：设计一个数据结构，对服务器Server类支持以下操作：
- 加入一个Server。
- 删除一个Server。
- 随机选择一个Server。
以上所有操作的时间复杂度都必须为O(1)。此题如果抽象出来，其实就是要求设计一个数据结构支持O(1)的insert，remove 和 find random。
在O(1)时间内支持前两种操作的数据结构其实不多，很容易让人联想到哈希表。关键是如何支持HashMap的随机选择操作。这里假设key和value都是整数类型，简单的用java实现代码如下：
Random random = new Random(); List<Integer> keys = new ArrayList<Integer>(map.keySet()); Integer randomKey = keys.get(random.nextInt(keys.size())); int randomElem = map.get(randomKey);
思路很简单，因为对于一个数组，要获得其中一个随机元素非常容易。利用这个性质，可以先获得HashMap里的key set，映射到一个数组里，然后随机生成数组下标，从而随机的指定一个key。拥有这样一个random key后，就可以获得一个random element了。
可惜的是以上方法并不是严格的O(1)时间，因为生成一个ArrayList其实需要将HashMap里所有的key都拷贝一份。除非是这个HashMap是只读的，不再增加或者删除元素，然后保存这个数组留着以后继续使用，从而得到均摊的O(1)时间。
不过想到这里其实离答案已经很接近了，既然用HashMap可以满足前2个条件，而用数组可以满足第3个条件，那么我们就可以混搭一下，设计一个包含有一个数组和一个HashMap的数据结构。
1. Insert：将server分别加入到HashMap和数组（尾部）；另外让对应的数组元素被数组末尾元素覆盖，然后去掉末尾元素
2. Delete：首先获得要删除的server的对应数组下标，然后将该server从HashMap中删除。另外让对应的数组元素被数组末尾元素覆盖，并且在HashMap里原来那个数组末尾元素的数组下标，最后删除数组的末尾元素。
3. Find Random：在数组中随机选一个数组下标，把相应的server作为key到HashMap里去找。
代码如下：
public class Servers {
private List<Server> servers = new ArrayList<Server>();
// key: server; value: array index
private Map<Server, Integer> serverMap = new HashMap<Server, Integer>();
public void add(Server server) {
servers.add(server);
serverMap.put(server, servers.size() - 1);
}
public void remove(Server server) {
int index = serverMap.get(server);
serverMap.remove(server);
servers.set(index, servers.get(servers.size() - 1));
serverMap.put(servers.get(index), index);
servers.remove(servers.size() - 1);
}
public Server findRandom() {
if (servers.size() == 0)
return null;
Random random = new Random();
int randomKey = random.nextInt(servers.size());
return servers.get(randomKey);
}
}