diff --git a/mercurial/verify.py b/mercurial/verify.py
--- a/mercurial/verify.py
+++ b/mercurial/verify.py
@@ -21,7 +21,7 @@ def _verify(repo):
     filelinkrevs = {}
     filenodes = {}
     revisions = 0
-    badrevs = {}
+    badrevs = set()
     errors = [0]
     warnings = [0]
     ui = repo.ui
@@ -33,7 +33,7 @@ def _verify(repo):
 
     def err(linkrev, msg, filename=None):
         if linkrev != None:
-            badrevs[linkrev] = True
+            badrevs.add(linkrev)
         else:
             linkrev = '?'
         msg = "%s: %s" % (linkrev, msg)
@@ -166,12 +166,12 @@ def _verify(repo):
 
     ui.status(_("checking files\n"))
 
-    storefiles = {}
+    storefiles = set()
     for f, f2, size in repo.store.datafiles():
         if not f:
             err(None, _("cannot decode filename '%s'") % f2)
         elif size > 0:
-            storefiles[f] = True
+            storefiles.add(f)
 
     files = sorted(set(filenodes) | set(filelinkrevs))
     for f in files:
@@ -194,7 +194,7 @@ def _verify(repo):
 
         for ff in fl.files():
             try:
-                del storefiles[ff]
+                storefiles.remove(ff)
             except KeyError:
                 err(lr, _("missing revlog!"), ff)