diff --git a/mercurial/verify.py b/mercurial/verify.py
--- a/mercurial/verify.py
+++ b/mercurial/verify.py
@@ -171,7 +171,7 @@ def _verify(repo):
         elif size > 0:
             storefiles[f] = True
 
-    files = util.sort(set(filenodes.keys() + filelinkrevs.keys()))
+    files = util.sort(set(filenodes) | set(filelinkrevs))
     for f in files:
         lr = filelinkrevs[f][0]
         try: