diff --git a/src/fns.c b/src/fns.c
index ac7c1f265a..2940bfdfbb 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -3915,6 +3915,17 @@ hash_lookup (struct Lisp_Hash_Table *h, Lisp_Object key, EMACS_UINT *hash)
   ptrdiff_t start_of_bucket;
   Lisp_Object idx;
 
+  if (HASH_TABLE_SIZE (h) <= 5 && h->test.cmpfn) {
+    /*Try doing a linear search first */
+    ptrdiff_t i;
+    for (i = 0; i < HASH_TABLE_SIZE (h); i++)
+      {
+        if (h->test.cmpfn (&h->test, key, HASH_KEY (h, i)))
+          return i;
+      }
+    return -1;
+  }
+
   hash_code = h->test.hashfn (&h->test, key);
   eassert ((hash_code & ~INTMASK) == 0);
   if (hash)