[Patch] Add two tests of hash function quality
Matt Austern
austern@gmail.com
Fri Sep 24 21:42:00 GMT 2010
This patch adds two very different tests to verify that we have a good
hash function. This is a very large and well studied area, and in principle
we could have many more tests of this sort, but a least these ones are
a start.
One test is very simple to describe: it hashes a set of strings to a set
of buckets, and uses chi^2 to verify that the distribution is uniform.
The other is slightly more complicated, but essentially it verifies that
every bit of the input string affects every bit of the output hash code.
--Matt
2010-09-24 Matt Austern <austern@google.com>
* testsuite/20_util/hash/chi2_quality.cc: New, verifies that
hash function gives a good distribution over buckets.
* testsuite/20_util/hash/quality.cc: New, verifies that all bits
are used in hash function input and output.
-------------- next part --------------
Index: libstdc++-v3/testsuite/20_util/hash/chi2_quality.cc
===================================================================
--- libstdc++-v3/testsuite/20_util/hash/chi2_quality.cc (revision 0)
+++ libstdc++-v3/testsuite/20_util/hash/chi2_quality.cc (revision 0)
@@ -0,0 +1,208 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// This file uses the chi^2 test to measure the quality of a hash
+// function, by computing the uniformity with which it distributes a set
+// of N strings into k buckets (where k is significantly greater than N).
+//
+// Each bucket has B[i] strings in it. The expected value of each bucket
+// for a uniform distribution is z = N/k, so
+// chi^2 = Sum_i (B[i] - z)^2 / z.
+//
+// We check whether chi^2 is small enough to be consistent with the
+// hypothesis of a uniform distribution. If F(chi^2, k-1) is close to
+// 0 (where F is the cumulative probability distribution), we can
+// reject that hypothesis. For large k, it turns out to mean we want
+// chi^2 to be not too much larger than k.
+//
+// We use the chi^2 test for several sets of strings. Any non-horrible
+// hash function should do well with purely random strings. A really
+// good hash function will also do well with more structured sets,
+// including ones where the strings differ by only a few bits.
+
+#include <algorithm>
+#include <cstdlib>
+#include <cstdio>
+#include <fstream>
+#include <functional>
+#include <iostream>
+#include <iterator>
+#include <string>
+#include <unordered_set>
+#include <vector>
+#include <testsuite_hooks.h>
+
+template <typename Container>
+ double
+ chi2_hash(const Container& c, long buckets)
+ {
+ std::vector<int> counts(buckets);
+ std::hash<std::string> hasher;
+ double elements = 0;
+ for (auto i = c.begin(); i != c.end(); ++i)
+ {
+ ++counts[hasher(*i) % buckets];
+ ++elements;
+ }
+
+ const double z = elements / buckets;
+ double sum = 0;
+ for (long i = 0; i < buckets; ++i)
+ {
+ double delta = counts[i] - z;
+ sum += delta*delta;
+ }
+ return sum/z;
+ }
+
+// Tests chi^2 for a distribution of uniformly generated random strings.
+void
+test_uniform_random()
+{
+ bool test __attribute__((unused)) = true;
+ std::srand(137);
+ std::unordered_set<std::string> set;
+ std::string s;
+ const unsigned long N = 1000000;
+ const unsigned long k = 10000;
+ const unsigned int len = 25;
+ while (set.size() < N)
+ {
+ s.clear();
+ for (int i = 0; i < len; ++i)
+ {
+ s.push_back(rand() % 128);
+ }
+ set.insert(s);
+ }
+
+ double chi2 = chi2_hash(set, k);
+ VERIFY( chi2 < k*1.1 );
+}
+
+// Tests chi^2 for a distribution of strings that differ from each
+// other by only a few bits. We start with an arbitrary base string, and
+// flip three random bits for each member of the set.
+void
+test_bit_flip_set()
+{
+ bool test __attribute__((unused)) = true;
+ const unsigned long N = 1000000;
+ const unsigned long k = 10000;
+ const unsigned int len = 67;
+ const unsigned int bitlen = len * 8;
+ const unsigned int bits_to_flip = 3;
+ const char base[len+1] = "abcdefghijklmnopqrstuvwxyz"
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+ "0123456789!@#$%";
+
+ std::unordered_set<std::string> set;
+ while (set.size() < N)
+ {
+ std::string s(base, base+len);
+ for (int i = 0; i < bits_to_flip; ++i)
+ {
+ int bit = rand() % bitlen;
+ s[bit/8] ^= (1 << (bit%8));
+ }
+ set.insert(s);
+ }
+
+ double chi2 = chi2_hash(set, k);
+ VERIFY( chi2 < k*1.1 );
+}
+
+// Tests chi^2 of a set of strings that all have a similar pattern,
+// intended to mimic some sort of ID string.
+void
+test_numeric_pattern_set()
+{
+ bool test __attribute__((unused)) = true;
+ const unsigned long N = 1000000;
+ const unsigned long k = 10000;
+ std::vector<std::string> set;
+ for (unsigned long i = 0; i < N; ++i)
+ {
+ long i1 = i % 100000;
+ long i2 = i / 100000;
+ char buf[16];
+ std::sprintf(buf, "XX-%05lu-%05lu", i1, i2);
+ set.push_back(buf);
+ }
+
+ double chi2 = chi2_hash(set, k);
+ VERIFY( chi2 < k*1.1 );
+}
+
+// Tests chi^2 for a set of strings that all consist of '1' and '0'.
+void
+test_bit_string_set()
+{
+ bool test __attribute__((unused)) = true;
+ const unsigned long N = 1000000;
+ const unsigned long k = 10000;
+ std::vector<std::string> set;
+ std::string s;
+ for (unsigned long i = 0; i < N; ++i)
+ {
+ s.clear();
+ for (int j = 0; j < sizeof(unsigned long) * 8; ++j)
+ {
+ const bool bit = (1UL << j) & i;
+ s.push_back(bit ? '1' : '0');
+ }
+ set.push_back(s);
+ }
+
+ double chi2 = chi2_hash(set, k);
+ VERIFY( chi2 < k*1.1 );
+}
+
+// Tests chi^2 for a set of words taken from a document written in English.
+void
+test_document_words()
+{
+ bool test __attribute__((unused)) = true;
+ const std::string f_name = "thirty_years_among_the_dead_preproc.txt";
+ std::ifstream in(f_name);
+ VERIFY( in.is_open() );
+ std::vector<std::string> words;
+ words.assign(std::istream_iterator<std::string>(in),
+ std::istream_iterator<std::string>());
+ VERIFY( words.size() > 100000 );
+ std::sort(words.begin(), words.end());
+ auto it = std::unique(words.begin(), words.end());
+ words.erase(it, words.end());
+ VERIFY( words.size() > 5000 );
+
+ const unsigned long k = words.size() / 20;
+ double chi2 = chi2_hash(words, k);
+ VERIFY( chi2 < k*1.1 );
+}
+
+int
+main()
+{
+ test_uniform_random();
+ test_bit_flip_set();
+ test_numeric_pattern_set();
+ test_bit_string_set();
+ test_document_words();
+ return 0;
+}
Index: libstdc++-v3/testsuite/20_util/hash/quality.cc
===================================================================
--- libstdc++-v3/testsuite/20_util/hash/quality.cc (revision 0)
+++ libstdc++-v3/testsuite/20_util/hash/quality.cc (revision 0)
@@ -0,0 +1,155 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2010 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <cstdlib>
+#include <unordered_set>
+#include <string>
+#include <functional>
+#include <vector>
+#include <testsuite_hooks.h>
+
+using namespace std;
+
+const int num_quality_tests = 5;
+const int num_strings_for_quality_tests = 400;
+const int string_size = 65;
+
+std::vector<std::string>
+random_strings(int n, int len)
+{
+ std::string s(len, '\0');
+ std::unordered_set<std::string> result_set;
+ while (result_set.size() < n)
+ {
+ result_set.insert(s);
+ unsigned int tmp = std::rand();
+ tmp %= len * 256;
+ s[tmp / 256] = tmp % 256;
+ }
+ return std::vector<std::string>(result_set.begin(), result_set.end());
+}
+
+double
+score_from_varying_position(std::string s, int index)
+{
+ bool test __attribute__((unused)) = true;
+ int bits_in_hash_code = sizeof(size_t) * 8;
+
+ // We'll iterate through all 256 vals for s[index], leaving the rest
+ // of s fixed. Then, for example, out of the 128 times that
+ // s[index] has its 3rd bit equal to 0 we would like roughly half 1s
+ // and half 0s in bit 9 of the hash codes.
+ //
+ // Bookkeeping: Conceptually we want a 3D array of ints. We want to count the
+ // number of times each output position (of which there are bits_in_hash_code)
+ // is 1 for each bit position within s[index] (of which there are 8) and value
+ // of that bit (of which there are 2).
+ const int jj = 2;
+ const int kk = jj * bits_in_hash_code;
+ const int array_size = 8 * kk;
+ std::vector<int> ones(array_size, 0);
+
+ for (int i = 0; i < 256; i++)
+ {
+ s[index] = i;
+ size_t h = hash<string>()(s);
+ for (int j = 0; h != 0; j++, h >>= 1)
+ {
+ if (h & 1)
+ {
+ for (int k = 0; k < 8; k++)
+ ++ones[k * kk + j * jj + ((i >> k) & 1)];
+ }
+ }
+ }
+
+ // At most, the innermost statement in the above loop nest can
+ // execute 256 * bits_in_hash_code * 8 times. If the hash is good,
+ // it'll execute about half that many times, with a pretty even
+ // spread across the elements of ones[].
+ VERIFY( 256 * bits_in_hash_code * 8 / array_size == 128 );
+ int max_ones_possible = 128;
+ int good = 0, bad = 0;
+ for (int bit = 0; bit <= 1; bit++)
+ {
+ for (int j = 0; j < bits_in_hash_code; j++)
+ {
+ for (int bitpos = 0; bitpos < 8; bitpos++)
+ {
+ int z = ones[bitpos * kk + j * jj + bit];
+ if (z <= max_ones_possible / 6 || z >= max_ones_possible * 5 / 6)
+ {
+ // The hash function screwed up, or was just unlucky,
+ // as 128 flips of a perfect coin occasionally yield
+ // far from 64 heads.
+ bad++;
+ }
+ else
+ good++;
+ }
+ }
+ }
+ return good / (double)(good + bad);
+}
+
+double
+score_from_varying_position(const std::vector<std::string>& v, int index)
+{
+ double score = 0;
+ for (int i = 0; i < v.size(); i++)
+ score += score_from_varying_position(v[i], index);
+ return score / v.size();
+}
+
+double
+quality_test(int num_strings, int string_size) {
+ // Construct random strings.
+ vector<string> v = random_strings(num_strings, string_size);
+ double sum_of_scores = 0;
+ for (int i = 0; i < string_size; i++)
+ sum_of_scores += score_from_varying_position(v, i);
+
+ // A good hash function should have a score very close to 1, and a bad
+ // hash function will have a score close to 0.
+ return sum_of_scores / string_size;
+}
+
+double
+quality_test()
+{
+ bool test __attribute__((unused)) = true;
+ std::srand(137);
+ double sum_of_scores = 0;
+ for (int i = 0; i < num_quality_tests; i++)
+ {
+ double score = quality_test(num_strings_for_quality_tests, string_size);
+ sum_of_scores += score;
+ VERIFY( score > 0.99 );
+ }
+
+ double mean_quality = sum_of_scores / num_quality_tests;
+ VERIFY( mean_quality > 0.9999 );
+}
+
+int
+main()
+{
+ quality_test();
+ return 0;
+}
More information about the Libstdc++
mailing list