/**
 * 功能：

[java] view plain copy

 

1. /** 
2.  * 思路： 
3.  * 1）针对每个朋友ID，找出所在机器的位置：int machine_index=getMachineIDForUser(personID); 
4.  * 2)转到编号为#machine_index的机器。 
5.  * 3）在那台机器上，执行：Person friend=getPersonWithID(person_id)。 
6.  *  
7.  * 定义一个Server类，包含一份所有机器的列表，还有一个Machine类，代表一台单独的机器。通过散列表，有效地查找数据。 
8.  * 
9.  */  
10.   
11. class Server{  
12.     HashMap<Integer,Machine> machines=new HashMap<Integer, Machine>();  
13.     HashMap<Integer,Integer> personToMachineMap=new HashMap<Integer, Integer>();  
14.       
15.     public Machine getMachineWithId(int machineID){  
16.         return machines.get(machineID);  
17.     }  
18.       
19.     public int getMachineIDForUser(int personID){  
20.         return personToMachineMap.get(personID);  
21.     }  
22.       
23.     public Person getPersonWithId(int personID){  
24.         Integer machineID=getMachineIDForUser(personID);  
25.         if(machineID==null)  
26.             return null;  
27.         Machine machine=getMachineWithId(machineID);  
28.         if(machine==null)  
29.             return null;  
30.         return machine.getPersonWithId(personID);  
31.     }  
32.       
33. }  
34.   
35. class Machine{  
36.     public int machineID;  
37.     public HashMap<Integer,Person> persons=new HashMap<Integer, Person>();  
38.       
39.     public Person getPersonWithId(int personID){  
40.         return persons.get(personID);  
41.     }  
42.       
43. }  
44.   
45. class Person{  
46.     private int personID;  
47.     private ArrayList<Integer> friendID;  
48.       
49.     public Person(int id){  
50.         this.personID=id;  
51.     }  
52.       
53.     public int getID(){  
54.         return this.personID;  
55.     }  
56.       
57.     public void addFriend(int id){  
58.         this.friendID.add(id);  
59.     }     
60.       
61. }  
62.   
63. /** 
64.  * 优化：减少机器间跳转次数 
65.  *      从一台机器跳转到另外一台机器的开销很昂贵，不要为了找到某个朋友就在机器之间任意跳转，而是试着批处理这些跳转动作。 
66.  * 优化：智能划分用户和机器 
67.  *      根据地域划分 
68.  *  
69.  * 问题：广度优先搜索要求标记访问过的节点，如何处理 
70.  *      同一时间可能会执行很多搜索操作，因此直接编辑数据的做法并不妥当。可以利用散列表模仿节点的标记动作，以查询节点id，是否被访问过。 
71.  */