Index: sys/netinet/libalias/alias_db.c
===================================================================
--- sys/netinet/libalias/alias_db.c
+++ sys/netinet/libalias/alias_db.c
@@ -324,11 +324,11 @@
 	/* Linked list of pointers for input and output lookup tables  */
 	union {
 		struct {
-			LIST_ENTRY(alias_link) in;
-			LIST_ENTRY(alias_link) out;
+			SPLAY_ENTRY(alias_link) out;
+			LIST_ENTRY (alias_link) in;
 		} all;
 		struct {
-			LIST_ENTRY(alias_link) list;
+			LIST_ENTRY (alias_link) list;
 		} pptp;
 	};
 	struct {
@@ -389,8 +389,6 @@
 /* Local prototypes */
 static struct group_in *
 StartPointIn(struct libalias *, struct in_addr, u_short, int, int);
-static u_int
-StartPointOut(struct in_addr, struct in_addr, u_short, u_short, int);
 static int	SeqDiff(u_long, u_long);
 
 #ifndef NO_FW_PUNCH
@@ -408,6 +406,24 @@
 
 void		SctpShowAliasStats(struct libalias *la);
 
+
+/* Splay handling */
+static inline int
+cmp_out(struct alias_link *a, struct alias_link *b) {
+	int i = a->src_port - b->src_port;
+	if (i != 0) return (i);
+	i = a->src_addr.s_addr - b->src_addr.s_addr;
+	if (i != 0) return (i);
+	i = a->dst_addr.s_addr - b->dst_addr.s_addr;
+	if (i != 0) return (i);
+	i = a->dst_port - b->dst_port;
+	if (i != 0) return (i);
+	i = a->link_type - b->link_type;
+	return (i);
+}
+SPLAY_PROTOTYPE(splay_out, alias_link, all.out, cmp_out);
+SPLAY_GENERATE(splay_out, alias_link, all.out, cmp_out);
+
 #define INGUARD						\
    if (grp->alias_port != alias_port ||			\
        grp->link_type != link_type ||			\
@@ -449,21 +465,6 @@
 }
 #undef INGUARD
 
-static u_int
-StartPointOut(struct in_addr src_addr, struct in_addr dst_addr,
-    u_short src_port, u_short dst_port, int link_type)
-{
-	u_int n;
-
-	n = src_addr.s_addr;
-	n += dst_addr.s_addr;
-	n += src_port;
-	n += dst_port;
-	n += link_type;
-
-	return (n % LINK_TABLE_OUT_SIZE);
-}
-
 static int
 SeqDiff(u_long x, u_long y)
 {
@@ -893,7 +894,7 @@
 			} while ((curr = next) != head);
 		} else {
 			/* Adjust output table pointers */
-			LIST_REMOVE(lnk, all.out);
+			SPLAY_REMOVE(splay_out, &la->splayTableOut, lnk);
 		}
 
 		/* Adjust input table pointers */
@@ -956,7 +957,6 @@
     struct in_addr alias_addr, u_short src_port, u_short dst_port,
     int alias_port_param, int link_type)
 {
-	u_int start_point;
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
@@ -1085,9 +1085,7 @@
 		}
 
 		/* Set up pointers for output lookup table */
-		start_point = StartPointOut(src_addr, dst_addr,
-		    src_port, dst_port, link_type);
-		LIST_INSERT_HEAD(&la->linkTableOut[start_point], lnk, all.out);
+		SPLAY_INSERT(splay_out, &la->splayTableOut, lnk);
 
 		/* Set up pointers for input lookup table */
 		if (lnk->flags & LINK_PARTIALLY_SPECIFIED)
@@ -1139,35 +1137,25 @@
 	return (new_lnk);
 }
 
-
-#define OUTGUARD					\
-   if (lnk->src_port != src_port ||			\
-       lnk->src_addr.s_addr != src_addr.s_addr ||	\
-       lnk->dst_addr.s_addr != dst_addr.s_addr ||	\
-       lnk->dst_port != dst_port ||			\
-       lnk->link_type != link_type)			\
-	   continue;
-
 static struct alias_link *
 _SearchLinkOut(struct libalias *la, struct in_addr src_addr,
     struct in_addr dst_addr,
     u_short src_port,
     u_short dst_port,
     int link_type) {
-	u_int i;
 	struct alias_link *lnk;
+	struct alias_link needle = {
+		.src_addr = src_addr,
+		.dst_addr = dst_addr,
+		.src_port = src_port,
+		.dst_port = dst_port,
+		.link_type = link_type
+	};
 
-	i = StartPointOut(src_addr, dst_addr, src_port, dst_port, link_type);
-	LIST_FOREACH(lnk, &la->linkTableOut[i], all.out) {
-		OUTGUARD;
-		return (UseLink(la, lnk));
-	}
-
-	return (NULL);
+	lnk = SPLAY_FIND(splay_out, &la->splayTableOut, &needle);
+	return (UseLink(la, lnk));
 }
 
-#undef OUTGUARD
-
 static struct alias_link *
 _FindLinkOut(struct libalias *la, struct in_addr src_addr,
     struct in_addr dst_addr,
@@ -2333,7 +2321,7 @@
 		if (head == NULL) {
 			server->next = server;
 			/* not usable for outgoing connections */
-			LIST_REMOVE(lnk, all.out);
+			SPLAY_REMOVE(splay_out, &la->splayTableOut, lnk);
 		} else {
 			struct server *s;
 
@@ -2503,8 +2491,7 @@
 		LibAliasTime = time(NULL);
 #endif
 
-		for (i = 0; i < LINK_TABLE_OUT_SIZE; i++)
-			LIST_INIT(&la->linkTableOut[i]);
+		SPLAY_INIT(&la->splayTableOut);
 		for (i = 0; i < LINK_TABLE_IN_SIZE; i++)
 			LIST_INIT(&la->groupTableIn[i]);
 		LIST_INIT(&la->pptpTable);
Index: sys/netinet/libalias/alias_local.h
===================================================================
--- sys/netinet/libalias/alias_local.h
+++ sys/netinet/libalias/alias_local.h
@@ -48,6 +48,7 @@
 #ifndef _ALIAS_LOCAL_H_
 #define	_ALIAS_LOCAL_H_
 
+#include <sys/tree.h>
 #include <sys/types.h>
 #include <sys/sysctl.h>
 
@@ -100,7 +101,7 @@
 	/* Lookup table of pointers to chains of link records.
 	 * Each link record is doubly indexed into input and
 	 * output lookup tables. */
-	LIST_HEAD (, alias_link) linkTableOut[LINK_TABLE_OUT_SIZE];
+	SPLAY_HEAD(splay_out, alias_link) splayTableOut;
 	LIST_HEAD (, group_in)   groupTableIn[LINK_TABLE_IN_SIZE];
 	LIST_HEAD (, alias_link) pptpTable;
 	/* HouseKeeping */