对于非常长的字符串列表,什么是合适的搜索/检索方法？

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;

namespace HashsetTest
{
    abstract class HashLookupBase
    {
        protected const int BucketCount = 16;

        private readonly HashAlgorithm _hasher;

        protected HashLookupBase()
        {
            _hasher = SHA256.Create();
        }

        public abstract void AddHash(byte[] data);
        public abstract bool Contains(byte[] data);

        private byte[] ComputeHash(byte[] data)
        {
            return _hasher.ComputeHash(data);
        }

        protected Data256Bit GetHashObject(byte[] data)
        {
            var hash = ComputeHash(data);
            return Data256Bit.FromBytes(hash);
        }

        public virtual void CompleteAdding() { }
    }

    class HashsetHashLookup : HashLookupBase
    {
        private readonly HashSet<Data256Bit>[] _hashSets;

        public HashsetHashLookup()
        {
            _hashSets = new HashSet<Data256Bit>[BucketCount];

            for(int i = 0; i < _hashSets.Length; i++)
                _hashSets[i] = new HashSet<Data256Bit>();
        }

        public override void AddHash(byte[] data)
        {
            var item = GetHashObject(data);
            var offset = item.GetHashCode() & 0xF;
            _hashSets[offset].Add(item);
        }

        public override bool Contains(byte[] data)
        {
            var target = GetHashObject(data);
            var offset = target.GetHashCode() & 0xF;
            return _hashSets[offset].Contains(target);
        }
    }

    class ArrayHashLookup : HashLookupBase
    {
        private Data256Bit[][] _objects;
        private int[] _offsets;
        private int _bucketCounter;

        public ArrayHashLookup(int size)
        {
            size /= BucketCount;
            _objects = new Data256Bit[BucketCount][];
            _offsets = new int[BucketCount];

            for(var i = 0; i < BucketCount; i++) _objects[i] = new Data256Bit[size + 1];

            _bucketCounter = 0;
        }

        public override void CompleteAdding()
        {
            for(int i = 0; i < BucketCount; i++) Array.Sort(_objects[i]);
        }

        public override void AddHash(byte[] data)
        {
            var hashObject = GetHashObject(data);
            _objects[_bucketCounter][_offsets[_bucketCounter]++] = hashObject;
            _bucketCounter++;
            _bucketCounter %= BucketCount;
        }

        public override bool Contains(byte[] data)
        {
            var hashObject = GetHashObject(data);
            return _objects.Any(o => Array.BinarySearch(o, hashObject) >= 0);
        }
    }

    struct Data256Bit : IEquatable<Data256Bit>, IComparable<Data256Bit>
    {
        public bool Equals(Data256Bit other)
        {
            return _u1 == other._u1 && _u2 == other._u2 && _u3 == other._u3 && _u4 == other._u4;
        }

        public int CompareTo(Data256Bit other)
        {
            var rslt = _u1.CompareTo(other._u1);    if (rslt != 0) return rslt;
            rslt = _u2.CompareTo(other._u2);        if (rslt != 0) return rslt;
            rslt = _u3.CompareTo(other._u3);        if (rslt != 0) return rslt;

            return _u4.CompareTo(other._u4);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj))
                return false;
            return obj is Data256Bit && Equals((Data256Bit) obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                var hashCode = _u1.GetHashCode();
                hashCode = (hashCode * 397) ^ _u2.GetHashCode();
                hashCode = (hashCode * 397) ^ _u3.GetHashCode();
                hashCode = (hashCode * 397) ^ _u4.GetHashCode();
                return hashCode;
            }
        }

        public static bool operator ==(Data256Bit left, Data256Bit right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(Data256Bit left, Data256Bit right)
        {
            return !left.Equals(right);
        }

        private readonly long _u1;
        private readonly long _u2;
        private readonly long _u3;
        private readonly long _u4;

        private Data256Bit(long u1, long u2, long u3, long u4)
        {
            _u1 = u1;
            _u2 = u2;
            _u3 = u3;
            _u4 = u4;
        }

        public static Data256Bit FromBytes(byte[] data)
        {
            return new Data256Bit(
                BitConverter.ToInt64(data, 0),
                BitConverter.ToInt64(data, 8),
                BitConverter.ToInt64(data, 16),
                BitConverter.ToInt64(data, 24)
            );
        }
    }

    class Program
    {
        private const int TestSize = 150000000;

        static void Main(string[] args)
        {
            GC.Collect(3);
            GC.WaitForPendingFinalizers();

            {
                var arrayHashLookup = new ArrayHashLookup(TestSize);
                PerformBenchmark(arrayHashLookup, TestSize);
            }

            GC.Collect(3);
            GC.WaitForPendingFinalizers();

            {
                var hashsetHashLookup = new HashsetHashLookup();
                PerformBenchmark(hashsetHashLookup, TestSize);
            }

            Console.ReadLine();
        }

        private static void PerformBenchmark(HashLookupBase hashClass, int size)
        {
            var sw = Stopwatch.StartNew();

            for (int i = 0; i < size; i++)
                hashClass.AddHash(BitConverter.GetBytes(i * 2));

            Console.WriteLine("Hashing and addition took " + sw.ElapsedMilliseconds + "ms");

            sw.Restart();
            hashClass.CompleteAdding();
            Console.WriteLine("Hash cleanup (sorting, usually) took " + sw.ElapsedMilliseconds + "ms");

            sw.Restart();
            var found = 0;

            for (int i = 0; i < size * 2; i += 10)
            {
                found += hashClass.Contains(BitConverter.GetBytes(i)) ? 1 : 0;
            }

            Console.WriteLine("Found " + found + " elements (expected " + (size / 5) + ") in " + sw.ElapsedMilliseconds + "ms");
        }
    }
}

结果很有希望.他们运行单线程.hashset版本可以在7.9GB RAM使用率下每秒查看超过100万次查找.基于阵列的版本使用较少的RAM(4.6GB).两者之间的启动时间几乎相同(388对391秒).hashset交换RAM以获得查找性能.由于内存分配限制,两者都必须被bucketized.

阵列性能:

哈希和加法花了307408ms

哈希清理(通常是排序)花了81892ms

在562585ms中发现了30000000个元素(预期为30000000)[每秒53k次搜索]

======================================

Hashset性能:

哈希和加法花了391105ms

哈希清理(通常是排序)花了0毫秒

在74864ms [每秒400k次搜索]中找到了30000000个元素(预期为30000000)

有了<gcAllowVeryLargeObjects>,你可以拥有更大的数组.为什么不将256位哈希码的ASCII表示转换为实现的自定义结构IComparable<T>？它看起来像这样:

struct MyHashCode: IComparable<MyHashCode>
{
    // make these readonly and provide a constructor
    ulong h1, h2, h3, h4;

    public int CompareTo(MyHashCode other)
    {
        var rslt = h1.CompareTo(other.h1);
        if (rslt != 0) return rslt;
        rslt = h2.CompareTo(other.h2);
        if (rslt != 0) return rslt;
        rslt = h3.CompareTo(other.h3);
        if (rslt != 0) return rslt;
        return h4.CompareTo(other.h4);
    }
}

然后,您可以创建这些数组,这将占用大约3.2 GB.您可以使用Array.BinarySearch轻松搜索它.

当然,您需要将用户的输入从ASCII转换为其中一个哈希代码结构,但这很容易.

至于性能,这不会像哈希表那么快,但它肯定会比数据库查找或文件操作更快.

想想看,你可以创造一个HashSet<MyHashCode>.您必须覆盖该Equals方法MyHashCode,但这非常简单.我记得,HashSet每个条目的成本大约为24个字节,而且你需要增加更大结构的成本.图五或六千兆字节,总计,如果您使用的话HashSet.更多的内存,但仍然可行,你得到O(1)查找.

这些答案不会将字符串内存计入应用程序.在.NET中,字符串不是1个字符== 1个字节.每个字符串对象都需要一个20字节的常量对象数据.缓冲区每个字符需要2个字节.因此:字符串实例的内存使用估计值为20 +(2*Length)字节.

我们来做一些数学.

100,000,000个UNIQUE字符串

SHA256 = 32字节(256位)

每个字符串的大小= 20 +(2*32字节)= 84字节

所需内存总量:8,400,000,000字节= 8.01千兆字节

有可能这样做,但这不会很好地存储在.NET内存中.您的目标应该是将所有这些数据加载到一个可以访问/分页的表单中,而不必将其全部保存在内存中.为此,我将使用Lucene.net哪个将您的数据存储在磁盘上并智能地搜索它.将每个字符串写为可搜索的索引,然后在索引中搜索字符串.现在你有一个可扩展的应用程序,可以解决这个问题; 你唯一的限制是磁盘空间(并且需要很多字符串来填充一个TB的驱动器).或者,将这些记录放在数据库中并对其进行查询.这就是数据库存在的原因:将事物保存在RAM之外.:)

如果列表随时间变化,我会把它放在数据库中.

如果列表没有改变,我会把它放在一个排序的文件中,并为每个查询进行二进制搜索.

在这两种情况下,我都会使用Bloom过滤器来最小化I/O. 我会停止使用字符串并使用带有四个ulongs的二进制表示(以避免对象引用成本).

如果您有超过16 GB(2*64*4/3*100M,假设使用Base64编码),则可以选择制作Set<string>并感到高兴.当然,如果使用二进制表示,它将小于7 GB.

David Haney的回答告诉我们,内存成本并不是那么容易计算出来的.

如果集合是常量,那么只需创建一个大的排序哈希列表(原始格式,每个32字节).存储所有哈希值以使它们适合磁盘扇区(4KB),并且每个扇区的开头也是哈希的开头.将每个第N个扇区中的第一个哈希保存在特殊索引列表中,该列表很容易适合内存.在此索引列表上使用二进制搜索来确定散列应该在的扇区群集的起始扇区,然后在此扇区群集中使用另一个二进制搜索来查找散列.应根据测试数据进行测量,确定值N.

编辑:替代方法是在磁盘上实现自己的哈希表.该表应使用开放寻址策略,探测序列应尽可能限制在同一磁盘扇区.空槽必须用特殊值标记(例如全部为零),因此在查询存在时应特别处理此特殊值.为避免冲突,表的值不应小于80%,因此在您的情况下,有1亿个大小为32字节的条目,这意味着该表应至少有100M/80%= 125百万个插槽,并且具有大小125M*32 = 4 GB.您只需要创建将2 ^ 256域转换为125M的散列函数,以及一些不错的探测序列.

在这种情况下,您需要小心,因为大多数语言中的大多数集合并未真正针对这种规模进行设计或优化.正如您已经确定的,内存使用也是一个问题.

这里明显的赢家是使用某种形式的数据库.SQL数据库或者有许多适合的NoSQL数据库.

SQL服务器已经过设计和优化,可以跟踪大量数据,对其进行索引以及跨这些索引进行搜索和查询.它专为完成你想做的事而设计,所以真的是最好的方法.

为了提高性能,您可以考虑使用将在您的进程中运行的嵌入式数据库,并节省由此产生的通信开销.对于Java,我可以为此推荐一个Derby数据库,我不知道C#的等价物足以在那里提出建议,但我想象存在合适的数据库.

你可以尝试一个后缀树,这个问题讨论了如何在C#中做到这一点

或者您可以尝试这样的搜索

var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();

AsParallel将帮助加快速度,因为它可以创建查询的并行化.

哈希集将您的数据拆分为存储桶(数组).在64位系统上,阵列的大小限制为2 GB,大约为 2,000,000,000字节.

由于字符串是引用类型,并且由于引用占用8个字节(假设为64位系统),因此每个存储桶可以容纳大约250,000,000(2.5亿)个字符串引用.它似乎比你需要的更多.

话虽如此,正如Tim S.所指出的那样,即使引用符合hashset,你也不太可能拥有必要的内存来保存字符串.数据库让我更适合这个.

可能需要一段时间(1)将所有记录转储到(聚簇索引)表中(最好使用它们的值,而不是它们的字符串表示形式(2))并让SQL进行搜索.它将为您处理二进制搜索,它将为您处理缓存,如果您需要对列表进行更改,这可能是最容易处理的事情.而且我很确定查询事物的速度与构建自己的东西一样快(或更快).

(1):为了加载数据,看一下SqlBulkCopy对象,像ADO.NET或Entity Framework这样的东西在逐行加载数据时会变得太慢.

(2):SHA-256 = 256位,所以二进制(32)会这样做; 这只是你现在使用的64个字符的一半.(如果您使用的是Unicode数字= P,则为四分之一)然后再次,如果您当前在纯文本文件中有信息,您仍然可以使用char(64)方式,只需将数据转储到表中即可的Bcp.exe.数据库将更大,查询稍慢(因为需要更多的I/O +缓存仅保留相同数量RAM的一半信息)等等......但这样做非常简单,如果你'对结果不满意,您仍然可以编写自己的数据库加载器.

要获得最大速度,请将它们保存在RAM中.它只有大约3GB的数据,加上你的数据结构需要的任何开销.A HashSet<byte[]>应该工作得很好.如果要降低开销和GC压力,请打开<gcAllowVeryLargeObjects>,使用单个byte[],并HashSet<int>使用自定义比较器对其进行索引.

对于速度和低内存使用率,请将它们存储在基于磁盘的哈希表中.为简单起见,将它们存储在数据库中.

无论你做什么,你都应该将它们存储为普通的二进制数据,而不是字符串.