c# - 对不同行长度的文件进行二分搜索

Question

我有一些代码对文件进行二进制搜索，每行都有排序的十六进制值(SHA1 哈希值)。这用于搜索 HaveIBeenPwned数据库。最新版本包含每个密码哈希被发现的次数计数，因此某些行末尾有额外的字符，格式为 ':###'

这个额外检查的长度不是固定的，而且并不总是存在。这会导致缓冲区读取不正确的值并且无法找到实际存在的值。

当前代码:

static bool Check(string asHex, string filename)
{
    const int LINELENGTH = 40;  //SHA1 hash length

    var buffer = new byte[LINELENGTH];
    using (var sr = File.OpenRead(filename))
    {
        //Number of lines
        var high = (sr.Length / (LINELENGTH + 2)) - 1;
        var low = 0L;

        while (low <= high)
        {
            var middle = (low + high + 1) / 2;
            sr.Seek((LINELENGTH + 2) * ((long)middle), SeekOrigin.Begin);
            sr.Read(buffer, 0, LINELENGTH);
            var readLine = Encoding.ASCII.GetString(buffer);
            switch (readLine.CompareTo(asHex))
            {
                case 0:
                    return true;

                case 1:
                    high = middle - 1;
                    break;

                case -1:
                    low = middle + 1;
                    break;

                default:
                    break;
            }
        }
    }
    return false;
}

我的想法是从中间向前查找，直到找到换行符，然后向后查找同一点，这应该给我一个完整的行，我可以用“:”分隔符分隔它。然后，我比较分割字符串数组的第一部分，它应该只是 SHA1 哈希值。

我认为这仍然应该以正确的值为中心，但是我想知道是否有更简洁的方法来做到这一点？如果中点不是行尾字符之间的实际中点，是否应该在高值和低值之前调整它？

Answer 1

我认为这可能是一个可能更简单(更快)的解决方案，无需回溯到行的开头。我认为您可以只使用字节文件索引，而不是尝试使用完整的“记录/行”。因为中间索引并不总是位于行/记录的开头，所以“readline”可以返回部分行/记录.如果您要立即执行第二个“readline”，您将获得完整的行/记录。这不是最佳选择，因为您实际上会在中间索引之前进行比较。

我下载了pwned-passwords-update-1，并在开始、结束和中间提取了大约30条记录，它似乎都找到了它们。你觉得怎么样？

const int HASHLENGTH = 40;

static bool Check(string asHex, string filename)
{
    using (var fs = File.OpenRead(filename))
    {
        var low = 0L;
        // We don't need to start at the very end
        var high = fs.Length - (HASHLENGTH - 1); // EOF - 1 HASHLENGTH

        StreamReader sr = new StreamReader(fs);

        while (low <= high)
        {
            var middle = (low + high + 1) / 2;
            fs.Seek(middle, SeekOrigin.Begin);

            // Resync with base stream after seek
            sr.DiscardBufferedData();

            var readLine = sr.ReadLine();

            // 1) If we are NOT at the beginning of the file, we may have only read a partial line so
            //    Read again to make sure we get a full line.
            // 2) No sense reading again if we are at the EOF
            if ((middle > 0) && (!sr.EndOfStream)) readLine = sr.ReadLine() ?? "";

            string[] parts = readLine.Split(':');
            string hash = parts[0];

            // By default string compare does a culture-sensitive comparison we may not be what we want?
            // Do an ordinal compare (0-9 < A-Z < a-z)
            int compare = String.Compare(asHex, hash, StringComparison.Ordinal);

            if (compare < 0)
            {
                high = middle - 1;
            }
            else if (compare > 0)
            {
                low = middle + 1;
            }
            else
            {
                return true;
            }
        }
    }
    return false;
}