这不是一个非常罕见的问题，但我似乎仍然找不到一个真正解释这个选择的答案。
我有一个非常大的字符串列表(确切地说，是SHA-256哈希的ASCII表示)，我需要查询该列表中是否存在字符串。
这个列表中可能有超过1亿个条目，我需要多次重复查询条目的存在。
考虑到尺寸，我怀疑我能把它全部塞进HashSet<string>。怎样的检索系统才能使性能最大化?
我可以预先排序列表，我可以把它放入一个SQL表，我可以把它放入一个文本文件，但我不确定什么是真正有意义的给我的应用程序。
在这些或其他检索方法中，在性能方面是否存在明显的赢家?
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秒vs 391秒)。哈希集以RAM换取查找性能。由于内存分配的限制，两者都必须进行桶化。
阵列性能:
哈希和加法耗时307408ms
哈希清理(通常是排序)耗时81892ms
在562585ms内找到30000000个元素(预期为30000000个)
======================================
Hashset性能:
哈希和加法耗时391105ms
哈希清理(通常是排序)耗时0ms
在74864ms内找到30000000个元素(预期30000000个)[每秒400k次搜索]
如果列表随时间变化，我会将其放入数据库中。
如果列表没有改变，我将把它放在一个排序文件中，并对每个查询进行二进制搜索。
在这两种情况下，我会使用Bloom过滤器来最小化I/O。我将停止使用字符串，而使用带有四个long的二进制表示(以避免对象引用成本)。
如果您有超过16 GB (2*64*4/3*100M，假设Base64编码)空闲，一个选项是创建Set<string>并感到高兴。当然，如果您使用二进制表示，它将适合小于7 GB
David Haney的答案告诉我们，内存成本不是那么容易计算的。
使用<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>。您必须重写MyHashCode上的Equals方法，但这真的很容易。我记得，HashSet每个条目的开销大约是24个字节，而且还会有更大的结构体的开销。如果您使用HashSet，图5或6gb，总共。更多的内存，但仍然是可行的，并且您得到O(1)查找。
这些答案没有将字符串内存考虑到应用程序中。字符串在。net中不是1 char == 1字节。每个字符串对象需要一个20字节的常量作为对象数据。缓冲区每个字符需要2字节。因此:一个字符串实例的内存使用估计是20 + (2 * Length)字节。
让我们做一些数学。
- 100,000,000个唯一字符串
- SHA256 = 32字节(256位)
- 每个字符串的大小= 20 +(2 * 32字节)= 84字节
- 总内存需求:8,400,000,000 bytes = 8.01 gb
这样做是可能的，但这将不能很好地存储在。net内存中。您的目标应该是将所有这些数据加载到一个可以访问/分页的表单中，而不必一次将所有数据保存在内存中。为此，我会使用Lucene.net，它会将您的数据存储在磁盘上并智能搜索它。将每个字符串写入可搜索的索引，然后在索引中搜索该字符串。现在你有一个可扩展的应用程序可以处理这个问题;唯一的限制将是磁盘空间(要填满一个tb的驱动器需要大量的字符串)。或者，将这些记录放入数据库并对其进行查询。这就是数据库存在的原因:在RAM之外持久化数据。:)
为了获得最高速度，请将它们保存在RAM中。它只有~3GB的数据价值，加上数据结构所需的任何开销。HashSet<byte[]>应该工作得很好。如果您想降低开销和GC压力，请打开byte[]，并使用带有自定义比较器的HashSet<int>来索引它。
对于速度和低内存使用，将它们存储在基于磁盘的哈希表中。为简单起见，将它们存储在数据库中。
无论如何，都应该将它们存储为纯二进制数据，而不是字符串。
哈希集将数据分成桶(数组)。在64位系统上，数组的大小限制为2gb，即大约 2,000,000,000字节。
由于字符串是引用类型，并且引用占用8个字节(假设是64位系统)，因此每个bucket可以容纳大约250,000,000(2.5亿个)对字符串的引用。这似乎远远超过你所需要的。
话虽如此，正如Tim S.指出的那样，即使引用可以放入哈希集，您也不太可能拥有保存字符串本身所需的内存。数据库对我来说更合适。
在这种情况下您需要小心，因为大多数语言中的大多数集合并没有真正针对这种规模进行设计或优化。正如您已经确定的那样，内存使用也将是一个问题。
显然这里的赢家是使用某种形式的数据库。无论是SQL数据库还是一些NoSQL数据库都是合适的。
SQL server已经被设计和优化为跟踪大量的数据，索引它，搜索和查询这些索引。它的设计正是为了做你想做的事情，所以这真的是最好的方法。
为了提高性能，您可以考虑使用将在您的进程中运行的嵌入式数据库，从而节省通信开销。对于Java，我可以推荐一个Derby数据库来实现这个目的，我不知道c#是否有足够的同类数据库来进行推荐，但我认为存在合适的数据库。
可能需要一段时间(1)来转储(集群索引)表中的所有记录(最好使用它们的值，而不是它们的字符串表示(2))，并让SQL进行搜索。它会帮你处理二进制搜索，它会帮你处理缓存如果你需要修改列表，它可能是最简单的方法。而且我很确定查询东西会和自己构建东西一样快(甚至更快)。
(1):要加载数据，请查看SqlBulkCopy对象，类似ADO。. NET或实体框架在逐行加载数据时会太慢。
(2): SHA-256 = 256 bits，所以二进制(32)就可以了;这只是你现在使用的64个字符的一半。(或四分之一，如果你使用Unicode数字=P)然后再一次，如果你目前有一个纯文本文件中的信息，你仍然可以去char(64)的方式，并简单地转储数据在表中使用bcp.exe。数据库会更大，查询会稍微慢一些(因为需要更多的I/O +对于相同数量的RAM，缓存只能保存一半的信息)，等等……但是这样做非常简单，如果您对结果不满意，您仍然可以编写自己的数据库加载器。
如果该集合是常量，则只需创建一个大的排序散列列表(原始格式，每个32字节)。存储所有散列，使它们适合磁盘扇区(4KB)，并且每个扇区的开始也是散列的开始。将每个第n个扇区中的第一个散列保存在一个特殊的索引列表中，这样可以很容易地放入内存中。在这个索引列表上使用二进制搜索来确定一个扇区集群的起始扇区应该在哪里，然后在这个扇区集群中使用另一个二进制搜索来找到你的哈希值。N值应根据试验数据测量确定。
编辑:另一种选择是在磁盘上实现您自己的哈希表。表应该使用开放寻址策略，并且探测序列应该尽可能地限制在同一个磁盘扇区。空槽必须用一个特殊值(例如全0)标记，因此在查询是否存在时应该特别处理这个特殊值。为了避免冲突，表的值不应该少于80%，所以在您的情况下，1亿个条目的大小为32字节，这意味着表应该至少有100M/80%= 1.25亿个插槽，并且大小为125M*32= 4 GB。您只需要创建将2^256域转换为125M的散列函数和一些不错的探测序列。
你可以尝试后缀树，这个问题是关于如何在c#中做到这一点
或者你可以尝试像这样搜索
var matches = list.AsParallel().Where(s => s.Contains(searchTerm)).ToList();
AsParallel将帮助加快速度，因为它创建了查询的并行化。
- 存储你的哈希值为UInt32[8]
2 a。使用排序列表。要比较两个散列，首先比较它们的第一个元素;如果它们相等，则比较第二个，依此类推。
2 b。使用前缀树
首先，我强烈建议您使用数据压缩，以便最大限度地减少资源消耗。在现代计算机中，缓存和内存带宽通常是最有限的资源。无论你如何实现它，最大的瓶颈将是等待数据。
我还建议使用现有的数据库引擎。它们中的许多都有内置压缩功能，任何数据库都可以利用可用的RAM。如果您有一个不错的操作系统，系统缓存将存储尽可能多的文件。但是大多数数据库都有自己的缓存子系统。
我真的不知道哪个db引擎最适合你，你必须尝试一下。就我个人而言，我经常使用H2，它性能不错，既可以用作内存数据库，也可以用作基于文件的数据库，并且内置透明压缩。
我看到有人说，将数据导入数据库并构建搜索索引可能比一些自定义解决方案需要更长的时间。这可能是真的，但进口通常是相当罕见的。我假设您对快速搜索更感兴趣，因为它们可能是最常见的操作。
为什么SQL数据库既可靠又相当快，你可能想考虑NoSQL数据库。尝试一些替代方案。要知道哪个解决方案能给您带来最佳性能，唯一的方法就是对它们进行基准测试。
您还应该考虑将列表存储为文本是否有意义。也许您应该将列表转换为数值。这将使用更少的空间，从而提供更快的查询。数据库导入可能会慢得多，但查询可能会快得多。
如果您想要非常快，并且元素或多或少是不可变的并且需要精确匹配，您可以构建一些类似于病毒扫描程序的操作:设置作用域以使用与您的条目和搜索标准相关的任何算法收集最小数量的潜在元素，然后遍历这些项，使用RtlCompareMemory对搜索项进行测试。如果条目相当连续，可以从磁盘中取出它们，并使用如下命令进行比较:
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);
}
}
我将修改这个示例以获取一个充满条目的大缓冲区，并循环遍历这些条目。但是托管代码可能不是正确的选择。"最快"总是更接近于执行实际工作的调用，因此使用直接C构建的内核模式访问的驱动程序会快得多。
首先，你说字符串实际上是SHA256哈希。观察100 million * 256 bits = 3.2 gigabytes，因此可以将整个列表放入内存中，假设您使用内存高效的数据结构。
如果你原谅偶尔的误报，你实际上可以使用更少的内存。参见bloom filters http://billmill.org/bloomfilter-tutorial/
否则，使用排序的数据结构实现快速查询(时间复杂度O(log n))。
如果你真的想把数据存储在内存中(因为你经常查询，需要快速的结果)，试试Redis。http://redis.io/
Redis是一个开源，BSD许可，高级键值存储。它通常被称为数据结构服务器，因为键可以包含字符串、哈希、列表、集合和排序集合。
它有一个固定的数据类型http://redis.io/topics/data-types#sets
Redis set是一个无序的string集合。可以在O(1)中添加、删除和测试成员的存在性(常数时间，无论Set中包含多少个元素)。
否则，使用将数据保存在磁盘上的数据库。
普通的二叉搜索树将在大型列表中提供出色的查找性能。然而，如果你真的不需要存储字符串和简单的成员关系是你想知道的，一个布隆过滤器可能是一个很好的解决方案。布隆过滤器是一种紧凑的数据结构，您可以使用所有字符串进行训练。经过训练后，它可以迅速告诉你它以前是否见过字符串。它很少报告。假阳性，但从不报告假阴性。根据应用程序的不同，它们可以快速产生惊人的结果，并且占用相对较少的内存。
我开发了一个类似于Insta方法的解决方案，但有一些不同。实际上，它看起来很像他的分块数组解决方案。但是，我的方法不是简单地分割数据，而是构建块的索引，并将搜索定向到适当的块。
索引的构建方式与哈希表非常相似，每个桶都是一个排序数组，可以用二进制搜索进行搜索。然而，我认为计算SHA256哈希的哈希没有什么意义，所以我只是简单地取值的前缀。
这项技术的有趣之处在于，您可以通过扩展索引键的长度来调优它。更长的键意味着更大的索引和更小的桶。我的8位测试用例可能有点小;10-12位可能更有效。
我尝试对这种方法进行基准测试，但是它很快就耗尽了内存，所以我无法看到任何关于性能的有趣的东西。
我还写了一个C实现。C实现也不能处理指定大小的数据集(测试机器只有4GB的RAM)，但它确实能处理更多的数据集。(在这种情况下，目标数据集实际上并不是什么大问题，而是测试数据填满了RAM。)我没能想出一个好办法，能足够快地向它扔数据，以真正看到它的性能测试。
虽然我很喜欢写这篇文章，但我想说的是，总的来说，它主要提供了支持你不应该在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();
}
}