这不是一个非常罕见的问题，但我仍然找不到一个真正解释选择的答案。
我有一个非常大的字符串列表（精确地说是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");
}
}
}
结果非常有前途。它们是单线程运行的。哈希集版本可以在使用7.9GB RAM时达到略高于100万次查找每秒的速度。基于数组的版本使用更少的RAM（4.6GB）。两者的启动时间几乎相同（388 vs 391秒）。哈希集以查找性能换取RAM。由于内存分配限制，两者都必须进行桶分配。
数组性能：
哈希和添加花费了307408毫秒
哈希清理（通常是排序）花费了81892毫秒
在562585毫秒内找到30000000个元素（预期为30000000）[每秒53k次搜索]
======================================
哈希集性能：
哈希和添加花费了391105毫秒
哈希清理（通常是排序）花费了0毫秒
在74864毫秒内找到30000000个元素（预期为30000000）[每秒400k次搜索]
gcAllowVeryLargeObjects，并且还要确保如果你使用Any CPU编译，那么在项目选项中禁用“prefer 32 bit”。不幸的是，我无法测试你的HashSet解决方案是否适用于这么多的元素，因为我只有8GB的RAM。但是如果你有足够的RAM，它应该可以工作。但是你需要接近16GB的可用空间，因为哈希集合必须通过复制来增长。除非你从数组创建哈希集合...嗯嗯嗯。 - Jim Mischel使用<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，则总计大约为五到六GB的内存。内存更多了，但仍然可行，而且您可以获得O(1)的查找。
为了达到最大的速度，将它们存储在RAM中。这只是大约3GB的数据加上您的数据结构所需的任何额外开销。HashSet<byte[]>应该可以很好地工作。如果您想降低开销和GC压力，请打开<gcAllowVeryLargeObjects>，使用单个byte[]以及带有自定义比较器的HashSet<int>来索引。
为了速度和低内存使用率，请将它们存储在基于磁盘的哈希表中。 为了简单起见，将它们存储在数据库中。
无论您做什么，都应该将它们存储为普通二进制数据，而不是字符串。
HashSet<byte[]> 是相当昂贵的。分配一个数组需要大约50字节的开销。因此，您的开销比数据还要大。最好创建一个由4个 ulong 值组成的 struct。×评论只能编辑5分钟×评论只能编辑5分钟×评论只能编辑5分钟 - Jim Mischel可能需要一些时间(1)来转储聚集索引表中的所有记录(最好使用它们的值，而不是它们的字符串表示(2))并让SQL进行搜索。它将为您处理二进制搜索，为您处理缓存，并且如果您需要对列表进行更改，则可能是最容易处理的东西。我相信查询事物的速度将与构建自己的速度一样快（或更快）。
(1): 要加载数据，请查看SqlBulkCopy对象，像ADO.NET或Entity Framework这样的东西会很慢，因为它们逐行加载数据。
(2): SHA-256 = 256位，因此二进制(32)就足够了；这只有你现在使用的64个字符的一半。(或者如果你使用Unicode数字，那么它只有四分之一=P) 不过，如果你目前的信息是以纯文本文件的形式存在的，你仍然可以按照char(64)的方式进行，并使用bcp.exe将数据简单地转储到表中。数据库会更大，查询稍微慢一些(因为需要更多的I/O + 相同数量的RAM缓存只保存一半的信息)，等等...但这很容易做到，如果你对结果不满意，仍然可以编写自己的数据库加载程序。
如果集合是恒定的，那么只需制作一个大型排序哈希列表（以原始格式为32字节）。 存储所有哈希，使其适合磁盘扇区（4KB），并且每个扇区的开头也是哈希的开头。 在特殊索引列表中保存每第N个扇区的第一个哈希，它将轻松适合内存。 在此索引列表上使用二进制搜索来确定哈希应该开始的扇区群集的起始扇区，然后在此扇区群集内使用另一个二进制搜索来查找您的哈希。 值N应该根据测试数据进行测量来确定。
编辑：另一种方法是在磁盘上实现自己的哈希表。该表应使用开放地址策略，并且探测序列应尽可能限制在同一磁盘扇区中。空插槽必须用特殊值（例如全零）标记，因此在查询存在性时应特别处理此特殊值。为避免冲突，表不应少于80％的值，因此在您的情况下，具有32字节大小的100百万条目的表至少应具有125百万个插槽，并且具有125M * 32 = 4 GB的大小。您只需要创建将2 ^ 256域转换为125M的哈希函数和一些漂亮的探测序列即可。
HashSet<string>存储string哈希值的字符串 的讽刺吗？ - recursion.ninja