Kategorie: C++

 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…

Ich hatte die schlechte Hashkey Implementierung ja bereits in VC-2005 als Bug gemeldet (siehe Die HashKey Implementierung in der MFC in VC-2005 und VC-2008). In VC-2008 geschah dies bzgl. wieder nichts. Aber was lange währt wird manchmal gut 😉

Die neue Implementierung wird aus der aktuellen STL übernommen. Diese Implementierung sorgt für Integer und Pointer für eine sehr gute zufällige Verteilung. Und weitere gute Nachricht dazu, auch die Implementierung für Strings wird aus der STL übernommen.

Zitat:

Hello Martin,

Thanks for the report. This issue has been fixed in MFC for Visual Studio 2010. MFC now uses the STL hash functions directly when possible, or uses a new algorithm copied from STL (in the case of strings).

Pat Brenner
Visual C++ Libraries Development
Von Microsoft am 20.07.2009 um 12:15 bereitgestellt

Siehe https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=468860