none
Выбор списочного типа для быстрого поиска RRS feed

  • Вопрос

  • Соит задача сравнить множество мелких файлов из разных источников и отбросить одинаковые. Сравнивать надо по содержимому (имена порядковый номер).

    Сравнивать думаю по хешу файла по-этому и рассматривал для сравнения файлов в качестве списка HashTable, но вот среда рекомендует использовать не System.Collections, а уже System.Collections.Generic. И вот с чего соответственно ряд вопросов:

    1. А аналог HashTable в System.Collections.Generic?
    2. Какой хеш из стандартных реализаций использовать?
    3. В соответствии с ключом держать путь к файлу или FileInfo?
    27 октября 2011 г. 12:00

Ответы

  • Вместо HashTable используйте HashSet<>.

    Для сравнения файлов сделайте класс-обертку вокруг файла, с переопределнными методами GetHashcode и Equals. В качестве хеша используйте CRC32:

    using System;
    using System.Collections.Generic;
    using System.IO;
    
    namespace ConsoleApplication104
    {
        class Program
        {
            static void Main(string[] args)
            {
                //используем HashSet для поиска одинаковых файлов
                HashSet<ComparableFile> files = new HashSet<ComparableFile>();
                //перебираем файлы, отбрасываем дубликаты
                foreach (var f in Directory.GetFiles("c:\\"))
                {
                    var cf = new ComparableFile(f);
                    if (!files.Add(cf))
                        Console.WriteLine("File '{0}' is duplicate", cf.FileName);
                }
            }
        }
    
        //класс для сравнения файлов
        class ComparableFile
        {
            int hash;
            public string FileName { get; private set; }
    
            public ComparableFile(string fileName)
            {
                FileName = fileName;
                //считаем хеш
                hash = ComputeCRC32(fileName);
            }
    
            static int ComputeCRC32(string fileName)
            {
                int crc32 = 0;
                int b = 0;
                int i = 0;
    
                using (var fs = new FileStream(fileName, FileMode.Open))
                    while ((b = fs.ReadByte()) >= 0)
                    {
                        crc32 ^= b << i;
                        i = (i + 8) % 32;
                    }
    
                return crc32;
            }
    
            public override int GetHashCode()
            {
                //испольузем вычисленный хеш как... хеш :)
                return hash;
            }
    
            public override bool Equals(object obj)
            {
                var other  = obj as ComparableFile;
    
                if(other == null)
                    return false;
                
                //сравнение объектов ComparableFile делаем по содержимому файлов
                using (var fs1 = new FileStream(FileName, FileMode.Open))
                using (var fs2 = new FileStream(other.FileName, FileMode.Open))
                {
                    if(fs1.Length != fs2.Length)
                        return false;
    
                    int b;
                    while ((b = fs1.ReadByte()) >= 0)
                        if(b != fs2.ReadByte())
                            return false;
                }
    
                return true;
            }
        }
    }

    • Предложено в качестве ответа PashaPash 27 октября 2011 г. 18:02
    • Изменено Algol36Editor 28 октября 2011 г. 4:59
    • Помечено в качестве ответа Abolmasov Dmitry 28 октября 2011 г. 8:28
    27 октября 2011 г. 17:06
    Отвечающий

Все ответы

  • > аналог HashTable в System.Collections.Generic?


    см. Dictionary(Of TKey, TValue) Class
    27 октября 2011 г. 12:07
  • > Какой хеш из стандартных реализаций использовать? 


    MD5 или SHA1

    P.S.
    How to compare 2 files fast using .NET?

    • Изменено Malobukv 27 октября 2011 г. 12:22
    27 октября 2011 г. 12:14
  • Тогда я не понял в чем заменяемость HashTable там по идее можно было переопределить метод хеширования, на предложенный вами MD5, а тут я уже должен подавать в ключ строку хеша? И возможно для более быстрого поиска из переданной строки уже будет строится хеш? (хеш строковых данных)
    27 октября 2011 г. 12:34
  • > Тогда я не понял в чем заменяемость HashTable там по идее можно было переопределить метод хеширования, на предложенный вами MD5, а тут я уже должен подавать в ключ строку хеша?

     
    Hashtable вообще не нужен если требуется сравнивать файлы.
    код для сравнения файлов тут.
    если файлов много, то можно в базе данных создать таблицу: [путь к файлу | код]
    код создается на основе алгоритма md5 или sha1.
    если надо проверить какой-то новый файл, то создается его код и ищется такой же в базе данных.

    27 октября 2011 г. 13:29
  • Вместо HashTable используйте HashSet<>.

    Для сравнения файлов сделайте класс-обертку вокруг файла, с переопределнными методами GetHashcode и Equals. В качестве хеша используйте CRC32:

    using System;
    using System.Collections.Generic;
    using System.IO;
    
    namespace ConsoleApplication104
    {
        class Program
        {
            static void Main(string[] args)
            {
                //используем HashSet для поиска одинаковых файлов
                HashSet<ComparableFile> files = new HashSet<ComparableFile>();
                //перебираем файлы, отбрасываем дубликаты
                foreach (var f in Directory.GetFiles("c:\\"))
                {
                    var cf = new ComparableFile(f);
                    if (!files.Add(cf))
                        Console.WriteLine("File '{0}' is duplicate", cf.FileName);
                }
            }
        }
    
        //класс для сравнения файлов
        class ComparableFile
        {
            int hash;
            public string FileName { get; private set; }
    
            public ComparableFile(string fileName)
            {
                FileName = fileName;
                //считаем хеш
                hash = ComputeCRC32(fileName);
            }
    
            static int ComputeCRC32(string fileName)
            {
                int crc32 = 0;
                int b = 0;
                int i = 0;
    
                using (var fs = new FileStream(fileName, FileMode.Open))
                    while ((b = fs.ReadByte()) >= 0)
                    {
                        crc32 ^= b << i;
                        i = (i + 8) % 32;
                    }
    
                return crc32;
            }
    
            public override int GetHashCode()
            {
                //испольузем вычисленный хеш как... хеш :)
                return hash;
            }
    
            public override bool Equals(object obj)
            {
                var other  = obj as ComparableFile;
    
                if(other == null)
                    return false;
                
                //сравнение объектов ComparableFile делаем по содержимому файлов
                using (var fs1 = new FileStream(FileName, FileMode.Open))
                using (var fs2 = new FileStream(other.FileName, FileMode.Open))
                {
                    if(fs1.Length != fs2.Length)
                        return false;
    
                    int b;
                    while ((b = fs1.ReadByte()) >= 0)
                        if(b != fs2.ReadByte())
                            return false;
                }
    
                return true;
            }
        }
    }

    • Предложено в качестве ответа PashaPash 27 октября 2011 г. 18:02
    • Изменено Algol36Editor 28 октября 2011 г. 4:59
    • Помечено в качестве ответа Abolmasov Dmitry 28 октября 2011 г. 8:28
    27 октября 2011 г. 17:06
    Отвечающий