什么是一个适当的search/检索方法很长的string列表？
这不是一个非常罕见的问题，但我似乎还找不到真正解释select的答案。
我有一个非常大的string列表（准确地说是SHA-256散列的ASCII表示），我需要查询该列表中是否存在string。
这个列表中可能有超过1亿个条目，我需要多次重复查询条目的存在。
给定的大小，我怀疑我可以把它们全部放进一个HashSet<string> 。 什么是适当的检索系统来最大限度地提高性能？
我可以预先sorting列表，我可以把它放到一个SQL表格中，我可以把它放到一个文本文件中，但是我不确定在我的应用程序中最有意义的是什么。
在这些performance方面，还是其他获取方法有明显的优势？
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"); } } }
结果是相当有希望的。 他们运行单线程。 在7.9GB内存使用情况下，哈希集版本每秒钟可以达到100万次以上的查找速度。 基于arrays的版本使用较less的RAM（4.6GB）。 两者之间的启动时间几乎相同（388对391秒）。 哈希集换取内存查找性能。 由于内存分配的限制，两者都必须进行bucketized。
arrays性能：
散列和加法耗时307408ms
哈希清理（通常sorting）耗时81892ms
在562585ms（每秒53k次search）中发现30000000个元素（预计30000000）
======================================
哈希performance：
散列和加法耗时391105ms
哈希清理（通常sorting）需要0ms
在74864ms中发现30000000个元素（预计30000000）[每秒400k次search]
如果列表随时间变化，我会把它放在一个数据库中。
如果列表没有改变，我会把它放在一个sorting文件中，并对每个查询进行二进制search。
在这两种情况下，我都会使用布隆filter来最小化I / O。 我会停止使用string，并使用二进制表示与四个ulong（以避免对象引用成本）。
如果您有超过16 GB的空间（2 * 64 * 4/3 * 100M，假设使用Base64编码），则可以select一个Set＆ltstring>并高兴。 当然，如果使用二进制表示，它将适合于小于7 GB。
大卫·哈尼的回答告诉我们，记忆成本不是那么容易计算的。
使用<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); } }
然后你可以创build一个这样的数组，这将占用大约3.2 GB。 您可以使用Array.BinarySearch方便地进行search 。
当然，您需要将用户的input从ASCII转换为其中一个哈希码结构，但这很简单。
至于性能，这不会像散列表一样快，但它肯定会比数据库查找或文件操作更快。
来想一想，你可以创build一个HashSet<MyHashCode> 。 你必须重写MyHashCode上的Equals方法，但这非常简单。 我记得， HashSet成本HashSet是每个条目24字节，你会有更大的结构增加的成本。 图五六千兆字节，总数，如果你是使用HashSet 。 更多的内存，但仍然可行，你得到O（1）查找。
这些答案不会将string内存分解到应用程序中。 在.NET中，string不是1个字符== 1个字节。 每个string对象都需要一个固定的20个字节的对象数据。 缓冲区每个字符需要2个字节。 因此： string实例的内存使用估计值是20 +（2 * Length）个字节。
我们来做一些math。
- 100,000,000个独特的string
- SHA256 = 32个字节（256位）
- 每个string的大小= 20 +（2 * 32字节）= 84字节
- 所需的总内存：8,400,000,000字节= 8.01千兆字节
这是可能的，但是这不会在.NET内存中存储好。 您的目标应该是将所有这些数据加载到可以访问/分页的表单中，而不必一次全部保存在内存中。 为此，我会使用Lucene.net将您的数据存储在磁盘上，并智能地search它。 将每个string写为可search的索引，然后searchstring的索引。 现在你有一个可以处理这个问题的可扩展的应用程序， 你唯一的限制将是磁盘空间（并且需要大量的string来填充一个太字节的驱动器）。 或者，将这些logging放在数据库中并对其进行查询。 这就是数据库存在的原因：坚持在RAM之外的东西。 🙂
为了获得最大速度，请将其保存在RAM中。 只有〜3GB的数据，加上你的数据结构需要的任何开销。 HashSet<byte[]>应该工作得很好。 如果要降低开销和GC压力，请打开<gcAllowVeryLargeObjects> ，使用单个byte[]和带有自定义比较器的HashSet<int>作为索引。
为了提高速度和低内存使用率，请将它们存储在基于磁盘的散列表中。 为了简单起见，将它们存储在数据库中。
无论你做什么，你都应该将它们存储为简单的二进制数据，而不是string。
散列集将数据拆分成桶（数组）。 在64位系统上， 数组大小限制为2 GB ， 大约为 20亿字节。
由于一个string是一个引用types，并且由于一个引用需要八个字节（假设一个64位系统），每个桶可以容纳约2.5亿（2.5亿）个string的引用。 它似乎比你所需要的更多。
话虽如此，正如Tim S.所指出的那样，即使引用符合哈希集，也不太可能拥有必要的内存来保存string本身。 数据库会让我更适合这个。
在这种情况下，你需要小心，因为大多数语言的大多数集合并不是真正为这种规模devise或优化的。 正如你已经确定的内存使用情况也将是一个问题。
这里明确的赢家是使用某种forms的数据库。 一个SQL数据库或者有一些NoSQL数据库是合适的。
SQL服务器已经经过devise和优化，可以跟踪大量的数据，对其进行索引，并在这些索引中进行search和查询。 它的目的是为了做你正在做的事情，所以真的是最好的方式去。
为了提高性能，您可以考虑使用一个embedded式数据库，该数据库将在您的进程中运行，并节省通信开销 对于Java我可以推荐一个Derby数据库用于这个目的，我不知道C＃等价物足以在那里提出build议，但是我想象一下合适的数据库存在。
可能需要一段时间（1）转储（聚集索引）表中的所有logging（最好使用它们的值，而不是它们的string表示（2）），并让SQL执行search。 它会处理你的二进制search，它会为你处理caching，如果你需要更改列表，这可能是最简单的工作。 而且我非常肯定，查询事物的速度会比构build自己的速度快（或更快）。
（1）：对于加载数据看看SqlBulkCopy对象，像ADO.NET或Entity Framework这样的东西太慢了，因为它们逐行加载数据。
（2）：SHA-256 = 256位，所以二进制（32） 这只是你现在使用的64个字符的一半。 （如果你使用的是Unicode数字= P，那么还有四分之一）然后，如果你现在有一个纯文本文件的信息，你仍然可以使用char（64）方法，只需要转储表中的数据的Bcp.exe。 数据库会变得更大，查询速度稍慢（因为需要更多的I / O +caching只能容纳相同数量内存的一半信息）等等。但是这样做很简单，不满意的结果，你仍然可以编写自己的数据库加载器。
如果该集合是常量，那么只需制作一个大的sorting哈希列表（原始格式，每个32字节）。 存储所有哈希以适应磁盘扇区（4KB），并且每个扇区的开始也是哈希的开始。 将每个第N个扇区中的第一个散列保存在一个特殊的索引列表中，这将很容易地放入内存中。 在此索引列表上使用二进制search来确定散列应该在的扇区簇的起始扇区，然后在此扇区簇内使用另一个二进制search来查找您的散列。 数值N应根据testing数据测量确定。
编辑：替代将是在磁盘上实现自己的哈希表。 该表应该使用开放的寻址策略，探测序列应尽可能限制在同一磁盘扇区。 空插槽必须标记一个特殊的值（例如全零），所以在查询存在时应该特别处理这个特殊值。 为了避免冲突，表中的值不能less于80％，所以在你的情况下，有1亿个大小为32字节的条目，这意味着表应该至less有100M / 80％= 125百万个槽，并且具有大小125M * 32 = 4GB。 你只需要创build哈希函数，将2 ^ 256域转换为125M，以及一些不错的探测序列。
你可以尝试一个后缀树 ，这个问题在C＃中如何做到这一点
或者你可以尝试像这样的search
var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();
AsParallel将帮助加速查询的并行化。
- 将散列存储为UInt32 [8]
2A。 使用sorting列表。 比较两个哈希，首先比较它们的第一个元素; 如果他们是平等的，那么比较第二个等等。
2B。 使用前缀树
首先，我真的build议你使用数据压缩，以尽量减less资源消耗。 高速caching和内存带宽通常是现代计算机中资源最有限的资源。 不pipe你如何实现这个，最大的瓶颈就是等待数据。
另外我会build议使用现有的数据库引擎。 他们中的许多人都有内置的压缩，任何数据库都会利用你可用的RAM。 如果您有一个体面的操作系统，系统caching将尽可能多地存储文件。 但大多数数据库都有自己的caching子系统。
我真的不知道什么数据库引擎将是最适合你的，你必须尝试一下。 我个人经常使用性能良好的H2，可以作为内存和基于文件的数据库使用，并build立在透明压缩。
我发现有些人声称，将数据导入到数据库并构buildsearch索引可能比一些自定义解决scheme需要更长的时间。 这可能是事实，但import通常是非常罕见的。 我会假设你对快速search更感兴趣，因为它们很可能是最常见的操作。
另外为什么SQL数据库既可靠又快速，你可能要考虑NoSQL数据库。 尝试几个select。 知道哪种解决scheme能够为您提供最佳性能的唯一途径就是通过对其进行基准testing。
你也应该考虑如果把你的列表存储为文本是有道理的。 也许你应该将列表转换为数值。 这将使用更less的空间，因此给你更快的查询。 数据库导入可能会明显变慢，但查询可能会变得更快。
如果你想要的速度非常快，并且元素或多或less是不可变的，并且需要精确的匹配，那么可以构build像病毒扫描程序那样的操作：设置范围以使用与条目相关的任何algorithm来收集最小数量的潜在元素search条件，然后遍历这些项目，使用RtlCompareMemory对search项目进行testing。您可以从磁盘中拉出项目，如果它们是相当连续的，并使用类似这样的比较：
private Boolean CompareRegions(IntPtr hFile, long nPosition, IntPtr pCompare, UInt32 pSize) { IntPtr pBuffer = IntPtr.Zero; UInt32 iRead = 0; try { pBuffer = VirtualAlloc(IntPtr.Zero, pSize, MEM_COMMIT, PAGE_READWRITE); SetFilePointerEx(hFile, nPosition, IntPtr.Zero, FILE_BEGIN); if (ReadFile(hFile, pBuffer, pSize, ref iRead, IntPtr.Zero) == 0) return false; if (RtlCompareMemory(pCompare, pBuffer, pSize) == pSize) return true; // equal return false; } finally { if (pBuffer != IntPtr.Zero) VirtualFree(pBuffer, pSize, MEM_RELEASE); } }
我会修改这个例子，以获取一个充满条目的大缓冲区，并循环这些。 但是，托pipe代码可能不是最好的select。最快的是总是接近实际工作的调用，所以具有内核模式访问权限的驱动程序构build在直C上会更快。
首先，你说的string是真正的SHA256散列。 观察到100 million * 256 bits = 3.2 gigabytes ，所以假设您使用内存高效的数据结构，可以将整个列表放在内存中。
如果你原谅偶尔的误报，你可以使用更less的内存。 请参阅bloomfilterhttp://billmill.org/bloomfilter-tutorial/
否则，使用sorting的数据结构来实现快速查询（时间复杂度O（log n））。
如果你真的想将数据存储在内存中（因为你经常查询并需要快速的结果），请尝试Redis。 http://redis.io/
Redis是一个开源的，BSD许可的高级键值存储。 它通常被称为数据结构服务器，因为密钥可以包含string，哈希值，列表，集合和有序集合。
它有一个数据typeshttp://redis.io/topics/data-types#sets
Redis集合是一个无序的string集合。 可以添加，删除和testingO（1）中成员的存在（恒定时间，而不pipe包含在集合中的元素的数量）。
否则，请使用将数据保存在磁盘上的数据库。
普通的香草二叉search树将在大型列表中提供出色的查找性能。 然而，如果你真的不需要存储string，简单的成员资格是你想知道的，Bloom Filter可能是一个三元组解决scheme。 布隆filter是一种紧凑的数据结构，可以用所有的string进行训练。 一旦训练完毕，它可以快速告诉你是否曾经看过一个string。 它很less报道积极的消息，但从不报告错误的消极情况。 根据应用的不同，它们可以快速产生惊人的效果，而且记忆力相对较小。
我开发了类似Insta方法的解决scheme，但有一些差异。 实际上，它看起来很像他的分块arrays解决scheme。 但是，我的方法不是简单地分割数据，而是build立一个块的索引，并只将search引导到合适的块。
build立索引的方式与散列表非常相似，每个存储桶都是一个sorting数组，可以使用二进制search进行search。 不过，我认为计算SHA256散列的散列没有多大意义，所以我只需要一个值的前缀。
关于这种技术有趣的是你可以通过扩展索引键的长度来调整它。 更长的键意味着更大的索引和更小的桶。 我的8位testing用例可能是小方面的， 10-12位可能会更有效。
我试图用这个方法作为基准，但是它很快耗尽了内存，所以我在性能方面看不到任何有趣的东西。
我也写了一个C实现。 C实现无法处理指定大小的数据集（testing机器只有4GB的RAM），但它确实pipe理的更多。 （在这种情况下，目标数据集实际上并不是那么严重的问题，testing数据填满了RAM）。我无法find一个很好的方法来将数据快速地input到内存中看到它的性能testing。
虽然我喜欢写这个，但总的来说，它大多提供了证据支持的论点，你不应该试图用C＃在内存中这样做。
public interface IKeyed { int ExtractKey(); } struct Sha256_Long : IComparable<Sha256_Long>, IKeyed { private UInt64 _piece1; private UInt64 _piece2; private UInt64 _piece3; private UInt64 _piece4; public Sha256_Long(string hex) { if (hex.Length != 64) { throw new ArgumentException("Hex string must contain exactly 64 digits."); } UInt64[] pieces = new UInt64[4]; for (int i = 0; i < 4; i++) { pieces[i] = UInt64.Parse(hex.Substring(i * 8, 1), NumberStyles.HexNumber); } _piece1 = pieces[0]; _piece2 = pieces[1]; _piece3 = pieces[2]; _piece4 = pieces[3]; } public Sha256_Long(byte[] bytes) { if (bytes.Length != 32) { throw new ArgumentException("Sha256 values must be exactly 32 bytes."); } _piece1 = BitConverter.ToUInt64(bytes, 0); _piece2 = BitConverter.ToUInt64(bytes, 8); _piece3 = BitConverter.ToUInt64(bytes, 16); _piece4 = BitConverter.ToUInt64(bytes, 24); } public override string ToString() { return String.Format("{0:X}{0:X}{0:X}{0:X}", _piece1, _piece2, _piece3, _piece4); } public int CompareTo(Sha256_Long other) { if (this._piece1 < other._piece1) return -1; if (this._piece1 > other._piece1) return 1; if (this._piece2 < other._piece2) return -1; if (this._piece2 > other._piece2) return 1; if (this._piece3 < other._piece3) return -1; if (this._piece3 > other._piece3) return 1; if (this._piece4 < other._piece4) return -1; if (this._piece4 > other._piece4) return 1; return 0; } //------------------------------------------------------------------- // Implementation of key extraction public const int KeyBits = 8; private static UInt64 _keyMask; private static int _shiftBits; static Sha256_Long() { _keyMask = 0; for (int i = 0; i < KeyBits; i++) { _keyMask |= (UInt64)1 << i; } _shiftBits = 64 - KeyBits; } public int ExtractKey() { UInt64 keyRaw = _piece1 & _keyMask; return (int)(keyRaw >> _shiftBits); } } class IndexedSet<T> where T : IComparable<T>, IKeyed { private T[][] _keyedSets; public IndexedSet(IEnumerable<T> source, int keyBits) { // Arrange elements into groups by key var keyedSetsInit = new Dictionary<int, List<T>>(); foreach (T item in source) { int key = item.ExtractKey(); List<T> vals; if (!keyedSetsInit.TryGetValue(key, out vals)) { vals = new List<T>(); keyedSetsInit.Add(key, vals); } vals.Add(item); } // Transform the above structure into a more efficient array-based structure int nKeys = 1 << keyBits; _keyedSets = new T[nKeys][]; for (int key = 0; key < nKeys; key++) { List<T> vals; if (keyedSetsInit.TryGetValue(key, out vals)) { _keyedSets[key] = vals.OrderBy(x => x).ToArray(); } } } public bool Contains(T item) { int key = item.ExtractKey(); if (_keyedSets[key] == null) { return false; } else { return Search(item, _keyedSets[key]); } } private bool Search(T item, T[] set) { int first = 0; int last = set.Length - 1; while (first <= last) { int midpoint = (first + last) / 2; int cmp = item.CompareTo(set[midpoint]); if (cmp == 0) { return true; } else if (cmp < 0) { last = midpoint - 1; } else { first = midpoint + 1; } } return false; } } class Program { //private const int NTestItems = 100 * 1000 * 1000; private const int NTestItems = 1 * 1000 * 1000; private static Sha256_Long RandomHash(Random rand) { var bytes = new byte[32]; rand.NextBytes(bytes); return new Sha256_Long(bytes); } static IEnumerable<Sha256_Long> GenerateRandomHashes( Random rand, int nToGenerate) { for (int i = 0; i < nToGenerate; i++) { yield return RandomHash(rand); } } static void Main(string[] args) { Console.WriteLine("Generating test set."); var rand = new Random(); IndexedSet<Sha256_Long> set = new IndexedSet<Sha256_Long>( GenerateRandomHashes(rand, NTestItems), Sha256_Long.KeyBits); Console.WriteLine("Testing with random input."); int nFound = 0; int nItems = NTestItems; int waypointDistance = 100000; int waypoint = 0; for (int i = 0; i < nItems; i++) { if (++waypoint == waypointDistance) { Console.WriteLine("Test lookups complete: " + (i + 1)); waypoint = 0; } var item = RandomHash(rand); nFound += set.Contains(item) ? 1 : 0; } Console.WriteLine("Testing complete."); Console.WriteLine(String.Format("Found: {0} / {0}", nFound, nItems)); Console.ReadKey(); } }
