Поиск дубликатов файлов на VB.NET с помощью MD5-хеша

Почему имени и даты недостаточно

Копии одной фотографии или документа почти никогда не лежат под одинаковыми именами: «отчёт.doc», «отчёт (2).doc», «копия отчёт.doc». Даты изменения тоже обманчивы, копирование их то сохраняет, то нет. Единственный надёжный признак дубликата это совпадение содержимого байт в байт.

Сравнивать все файлы попарно побайтно слишком дорого: для тысячи файлов это полмиллиона сравнений. Вместо этого для каждого файла один раз вычисляется хеш, короткая строка фиксированной длины, зависящая от всех байтов. Одинаковые файлы дают одинаковый хеш, а совпадение хешей у разных файлов при MD5 на практике не встречается, если никто не подбирает такие файлы намеренно.

.NET Framework содержит готовые реализации хеш-функций в пространстве имён System.Security.Cryptography. Вся работа сводится к вызову ComputeHash.

Правильное вычисление хеша файла

В старых примерах можно встретить код, который читает файл через StreamReader в строку, переводит её в байты через ASCIIEncoding, хеширует и затем снова превращает хеш в строку через ASCII. В нём сразу три ошибки. StreamReader декодирует двоичный файл как текст и искажает байты. Весь файл попадает в память, а для видео это гигабайты. А преобразование хеша через ASCII заменяет все байты больше 127 на знак вопроса, поэтому разные хеши начинают совпадать, и программа находит ложные дубликаты.

Правильный вариант передаёт в ComputeHash сам поток FileStream. Метод читает файл блоками, память расходуется только на буфер, а результат переводится в строку через BitConverter.ToString, который сохраняет все байты. Блоки Using гарантируют закрытие файла даже при ошибке.

Imports System.IO
Imports System.Security.Cryptography

Public Module FileHash
    ' MD5 файла в виде "9E-10-7D-..." без загрузки файла в память
    Public Function GetFileMd5(ByVal path As String) As String
        Using hasher As MD5 = MD5.Create()
            Using fs As New FileStream(path, FileMode.Open, FileAccess.Read, _
                                       FileShare.Read, 65536)
                Return BitConverter.ToString(hasher.ComputeHash(fs))
            End Using
        End Using
    End Function

    ' Сравнение двух файлов: сначала дешёвая проверка размера
    Public Function SameContent(ByVal file1 As String, ByVal file2 As String) As Boolean
        If New FileInfo(file1).Length <> New FileInfo(file2).Length Then Return False
        Return GetFileMd5(file1) = GetFileMd5(file2)
    End Function
End Module

Обход папок без падения на правах доступа

Метод Directory.GetFiles с параметром SearchOption.AllDirectories выглядит как готовое решение, но на первой же папке без прав доступа выбрасывает UnauthorizedAccessException и не возвращает ничего. Для поиска по пользовательскому диску это неприемлемо.

Надёжнее обходить дерево самостоятельно со стеком папок. Ошибка доступа гасится для одной папки, а обход продолжается. Заодно пропускаем точки повторной обработки (junction), иначе обход профиля пользователя может зациклиться.

Public Function SafeEnumerate(ByVal root As String) As List(Of String)
    Dim files As New List(Of String)
    Dim pending As New Stack(Of String)
    pending.Push(root)
    While pending.Count > 0
        Dim dir As String = pending.Pop()
        Try
            files.AddRange(Directory.GetFiles(dir))
            For Each subDir As String In Directory.GetDirectories(dir)
                If (File.GetAttributes(subDir) And FileAttributes.ReparsePoint) = 0 Then
                    pending.Push(subDir)
                End If
            Next
        Catch ex As UnauthorizedAccessException
            ' нет прав на папку: пропускаем её, обход продолжается
        End Try
    End While
    Return files
End Function

Сначала размер, потом хеш

Хешировать каждый файл на диске незачем. Файлы разного размера заведомо разные, а размер известен без чтения содержимого. Поэтому сначала группируем файлы по длине, и хеш считаем только в группах, где файлов два и больше. На типичном диске это отсекает подавляющую часть работы: уникальных по размеру файлов большинство.

Пустые файлы пропускаем: они все одинаковы, но удалять их как дубликаты обычно бессмысленно. Файлы, занятые другими программами, тоже пропускаем, а не прерываем поиск.

Public Function FindDuplicates(ByVal root As String) As List(Of List(Of String))
    ' 1. Группировка по размеру: разные длины не могут совпасть
    Dim bySize As New Dictionary(Of Long, List(Of String))
    For Each path As String In SafeEnumerate(root)
        Dim size As Long = New FileInfo(path).Length
        If size = 0 Then Continue For
        If Not bySize.ContainsKey(size) Then bySize(size) = New List(Of String)
        bySize(size).Add(path)
    Next
    ' 2. Хешируем только группы из двух и более файлов
    Dim result As New List(Of List(Of String))
    For Each group As List(Of String) In bySize.Values
        If group.Count < 2 Then Continue For
        Dim byHash As New Dictionary(Of String, List(Of String))
        For Each path As String In group
            Dim h As String
            Try
                h = GetFileMd5(path)
            Catch ex As IOException
                Continue For                       ' файл занят: пропускаем
            End Try
            If Not byHash.ContainsKey(h) Then byHash(h) = New List(Of String)
            byHash(h).Add(path)
        Next
        For Each dup As List(Of String) In byHash.Values
            If dup.Count > 1 Then result.Add(dup)
        Next
    Next
    Return result
End Function

Удаление найденного: аккуратно и обратимо

Найти дубликаты легко, а вот удалять их стоит с осторожностью. Пользователь должен видеть группы и сам выбирать, какой экземпляр оставить: иногда «дубликат» лежит в папке проекта, который без него не соберётся.

Вместо File.Delete лучше отправлять файлы в Корзину, чтобы ошибку можно было исправить. В VB.NET для этого есть готовый метод в пространстве My, не требующий вызовов Windows API.

' Удаляем все копии, кроме первой в группе, с отправкой в Корзину
Private Sub RemoveCopies(ByVal group As List(Of String))
    For i As Integer = 1 To group.Count - 1
        Try
            My.Computer.FileSystem.DeleteFile(group(i), _
                FileIO.UIOption.OnlyErrorDialogs, _
                FileIO.RecycleOption.SendToRecycleBin)
        Catch ex As Exception
            lstLog.Items.Add("Не удалось удалить " & group(i) & ": " & ex.Message)
        End Try
    Next
End Sub

Насколько можно доверять MD5

MD5 давно не считается криптографически стойким: существуют способы намеренно создать два разных файла с одинаковым хешем. Для поиска случайных копий на своём диске это не имеет значения, вероятность случайного совпадения ничтожна. Но если программа сравнивает файлы из недоверенных источников, например загружаемые пользователями на сервер, используйте SHA-256: интерфейс тот же, достаточно заменить MD5.Create на SHA256.Create.

Учтите и производительность. Узким местом почти всегда оказывается диск, а не процессор: MD5 считает сотни мегабайт в секунду. Поэтому многопоточность даёт выигрыш на SSD, а на обычном жёстком диске параллельное чтение из разных мест, наоборот, замедляет работу.

Как это делают сегодня

Вопросы и ответы