title: Fastest possible string key lookup for known set of keys
body: <p>Consider a lookup function with the following signature, which needs to return an integer for a given string key:</p>
  
  <pre><code>int GetValue(string key) { ... }
  </code></pre>
  
  <p>Consider furthermore that the key-value mappings, numbering N, are known in advance when the source code for function is being written, e.g.:</p>
  
  <pre><code>// N=3
  { "foo", 1 },
  { "bar", 42 },
  { "bazz", 314159 }
  </code></pre>
  
  <p>So a valid (but not perfect!) implementation for the function for the input above would be:</p>
  
  <pre><code>int GetValue(string key)
  {
      switch (key)
      {
           case "foo": return 1;
           case "bar": return 42;
           case "bazz": return 314159;
      }
  
      // Doesn't matter what we do here, control will never come to this point
      throw new Exception();
  }
  </code></pre>
  
  <p>It is also known in advance exactly how many times (C>=1) the function will be called at run-time for every given key. For example:</p>
  
  <pre><code>C["foo"] = 1;
  C["bar"] = 1;
  C["bazz"] = 2;
  </code></pre>
  
  <p>The order of such calls is <em>not</em> known, however. E.g. the above could describe the following sequence of calls at run-time:</p>
  
  <pre><code>GetValue("foo");
  GetValue("bazz");
  GetValue("bar");
  GetValue("bazz");
  </code></pre>
  
  <p>or any other sequence, provided the call counts match.</p>
  
  <p>There is also a restriction M, specified in whatever units is most convenient, defining the upper memory bound of any lookup tables and other helper structures that can be used by the <code>GetValue</code> (the structures are initialized in advance; that initialization is not counted against the complexity of the function). For example, M=100 chars, or M=256 sizeof(object reference).</p>
  
  <p>The question is, how to write the body of <code>GetValue</code> such that it is as fast as possible - in other words, the aggregate time of all <code>GetValue</code> calls (note that we know the total count, per everything above) is minimal, for given N, C and M?</p>
  
  <p>The algorithm may require a reasonable minimal value for M, e.g. M >= <code>char.MaxValue</code>. It may also require that M be aligned to some reasonable boundary - for example, that it may only be a power of two. It may also require that M must be a function of N of a certain kind (for example, it may allow valid M=N, or M=2N, ...; or valid M=N, or M=N^2, ...; etc).</p>
  
  <p>The algorithm can be expressed in any suitable language or other form. For runtime performance constrains for generated code, assume that the generated code for <code>GetValue</code> will be in C#, VB or Java (really, any language will do, so long as strings are treated as immutable arrays of characters - i.e. O(1) length and O(1) indexing, and no other data computed for them in advance). Also, to simplify this a bit, answers which assume that C=1 for all keys are considered valid, though those answers which cover the more general case are preferred.</p>
  
  <h2>Some musings on possible approaches</h2>
  
  <p>The obvious first answer to the above is using a perfect hash, but generic approaches to finding one seem to be imperfect. For example, one can easily generate a table for a minimal perfect hash using Pearson hashing for the sample data above, but then the input key would have to be hashed for every call to <code>GetValue</code>, and Pearson hash necessarily scans the entire input string. But all sample keys actually differ in their third character, so only that can be used as the input for the hash instead of the entire string. Furthermore, if M is required to be at least <code>char.MaxValue</code>, then the third character itself becomes a perfect hash.</p>
  
  <p>For a different set of keys this may no longer be true, but it may still be possible to reduce the amount of characters considered before the precise answer can be given. Furthermore, in some cases where a <em>minimal</em> perfect hash would require inspecting the entire string, it may be possible to reduce the lookup to a subset, or otherwise make it faster (e.g. a less complex hashing function?) by making the hash non-minimal (i.e. M > N) - effectively sacrificing space for the sake of speed.</p>
  
  <p>It may also be that traditional hashing is not such a good idea to begin with, and it's easier to structure the body of <code>GetValue</code> as a series of conditionals, arranged such that the first checks for the "most variable" character (the one that varies across most keys), with further nested checks as needed to determine the correct answer. Note that "variance" here can be influenced by the number of times each key is going to be looked up (C). Furthermore, it is not always readily obvious what the best structure of branches should be - it may be, for example, that the "most variable" character only lets you distinguish 10 keys out of 100, but for the remaining 90 that one extra check is unnecessary to distinguish between them, and on average (considering C) there are more checks per key than in a different solution which does <em>not</em> start with the "most variable" character. The goal then is to determine the perfect sequence of checks.</p>