diff --git a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/ServerManager.java b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/ServerManager.java
index 612a8d0..531883a 100644
--- a/hbase-server/src/main/java/org/apache/hadoop/hbase/master/ServerManager.java
+++ b/hbase-server/src/main/java/org/apache/hadoop/hbase/master/ServerManager.java
@@ -135,8 +135,8 @@
     new ConcurrentSkipListMap<byte[], ConcurrentNavigableMap<byte[], Long>>(Bytes.BYTES_COMPARATOR);
 
   /** Map of registered servers to their current load */
-  private final ConcurrentHashMap<ServerName, ServerLoad> onlineServers =
-    new ConcurrentHashMap<ServerName, ServerLoad>();
+  private final ConcurrentNavigableMap<ServerName, ServerLoad> onlineServers =
+    new ConcurrentSkipListMap<ServerName, ServerLoad>();
 
   /**
    * Map of admin interfaces per registered regionserver; these interfaces we use to control
@@ -439,8 +439,14 @@
    */
   private ServerName findServerWithSameHostnamePortWithLock(
       final ServerName serverName) {
-    for (ServerName sn: this.onlineServers.keySet()) {
-      if (ServerName.isSameHostnameAndPort(serverName, sn)) return sn;
+    ServerName end = ServerName.valueOf(serverName.getHostname(), serverName.getPort(),
+        Long.MAX_VALUE);
+
+    ServerName r = onlineServers.lowerKey(end);
+    if (r != null) {
+      if (ServerName.isSameHostnameAndPort(r, serverName)) {
+        return r;
+      }
     }
     return null;
   }