CMapStringTo… HashKey Implementierung in VC-2003/5/8 ist auch fragwürdig

 Hash-Algorithmen haben es mir irgendwie angetan. 1984 hatte ich das erste mal mit einem miesen Hashverfahren zu tun, das einfach versagte wenn es nur um Ziffern ging. Das ganze betraf das Betriebssystem OASIS (später TheOS) und dessen Index Dateiorganisation. Ich entwickelte hierfür einen Patch in Assembler, der damals exakt in den x-Bytes der Kernels in Z80 Assembler passen musste.
Das Problem bei Strings die nur aus Ziffern bestehen ist das die Veränderung, die immer nur die unteren 4 Bits betrifft und die höheren 4 Bits immer konstant sind mit 3 belegt sind.

Als ich gelesen habe,  dass in VS-2010 die CMap Implementierung nun auch für Strings den selben Algorithmus aus der STL erhalten, habe ich mir auch den mal genauer angesehen. (siehe Beitrag Die MFC erhält mit VC-2010 jetzt eine neue HashKey Implementierung)
Der sieht so aus:

inline UINT CMapStringToString::HashKey(LPCTSTR key) const
{
  UINT nHash = 0;
  if (key == NULL)
  {
    AfxThrowInvalidArgException();
  }
 
  while (*key)
    nHash = (nHash<<5) + nHash + *key++;
  return nHash;
}

Und auch in diesem Fall muss ich sagen, dass der Algorithmus nur scheinbar intelligent ist. Wenn man sich aber die Abstände die hier erzeugt werden etwas genauer anschaut kommt man schnell auf eine Wertekombination, in der der Algorithmus versagt.
Wie sehr er versagt zeigt das folgende Beispiel, in dem ich einfach einen String verwende der aus 5 Ziffern besteht und immer den Abstand 11 verwendet.

CMapStringToPtr myMap;
for (int i=0; i<1000; i+=11)
{
  CString strKey;
  strKey.Format(_T("%05d"),i);
  myMap[strKey] = NULL;
}

Das erschreckende Ergebnis der Verteilung ist bei einem Unicode wie auch MBCS Projekt:

TMyMap<class CMapStringToPtr>::DumpMap
Bucket  0 =  0
Bucket  1 =  0
Bucket  2 =  0
Bucket  3 =  0
Bucket  4 =  0
Bucket  5 =  0
Bucket  6 =  0
Bucket  7 =  0
Bucket  8 = 36
Bucket  9 =  0
Bucket 10 =  0
Bucket 11 =  0
Bucket 12 =  0
Bucket 13 =  0
Bucket 14 = 55
Bucket 15 =  0
Bucket 16 =  0

Wie gut, dass auch die String Variante von HashKey überarbeitet wird.

BTW: Da die internen Strukturen protected sind muss man zu einem kleinen Trick greifen um die Verteilung ausgeben zu können. Ich habe dazu ein template verwendet, dass für alle MFC Maps funktioniert.

template<class TBase> class TMyMap : public TBase
{
public:
  void DumpMap()
  {
    TRACE(__FUNCTION__ "\n");
    if (m_pHashTable)
    {
      for (size_t i=0; i<m_nHashTableSize; ++i)
      {
        int iCount = 0;
        for (CAssoc *p = m_pHashTable[i]; p; p=p->pNext)
          ++iCount;
        TRACE("Bucket %2d = %4d\n", i, iCount);
      }
    }
  }
};

Merke: Wer Hashes verwendet sollte sich über sein Hashverfahren wirklich gedanken machen.

BTW: Sollte es den Leser meines Blogs langsam langweilen weil ich mich permanent mit Hash-Algorithmen aufhalte, der sei getröstet: Dies war vorläufig mein letzter Beitrag zu CMap…