{"id":502,"date":"2009-08-01T18:26:28","date_gmt":"2009-08-01T16:26:28","guid":{"rendered":"http:\/\/blog.m-ri.de\/?p=502"},"modified":"2009-08-01T18:30:14","modified_gmt":"2009-08-01T16:30:14","slug":"cmapstringto-hashkey-implementierung-in-vc-200358-ist-auch-fragwuerdig","status":"publish","type":"post","link":"http:\/\/blog.m-ri.de\/index.php\/2009\/08\/01\/cmapstringto-hashkey-implementierung-in-vc-200358-ist-auch-fragwuerdig\/","title":{"rendered":"CMapStringTo… HashKey Implementierung in VC-2003\/5\/8 ist auch fragw\u00fcrdig"},"content":{"rendered":"

\u00a0Hash-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\u00e4ter TheOS) und dessen Index Dateiorganisation. Ich entwickelte hierf\u00fcr einen Patch in Assembler, der damals exakt in den x-Bytes der Kernels in Z80 Assembler passen musste.
\nDas Problem bei Strings die nur aus Ziffern bestehen ist das die Ver\u00e4nderung, die immer nur die unteren 4 Bits betrifft und die h\u00f6heren 4 Bits immer konstant sind mit 3 belegt sind.<\/p>\n

Als ich gelesen habe, \u00a0dass in VS-2010 die CMap Implementierung nun auch f\u00fcr Strings den selben Algorithmus aus der STL erhalten, habe ich mir auch den mal genauer angesehen. (siehe Beitrag Die MFC erh\u00e4lt mit VC-2010 jetzt eine neue HashKey Implementierung<\/a>)
\nDer sieht so aus:<\/p>\n

inline UINT CMapStringToString::HashKey(LPCTSTR key) const\r\n{\r\n  UINT nHash = 0;\r\n  if (key == NULL)\r\n  {\r\n    AfxThrowInvalidArgException();\r\n  }\r\n\u00a0\r\n  while (*key)\r\n    nHash = (nHash<<5) + nHash + *key++;\r\n  return nHash;\r\n}<\/pre>\n
Und auch in diesem Fall muss ich sagen, dass der Algorithmus nur scheinbar intelligent ist. Wenn man sich aber die Abst\u00e4nde die hier erzeugt werden etwas genauer anschaut kommt man schnell auf eine Wertekombination, in der der Algorithmus versagt.
\nWie 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.<\/p>\n
CMapStringToPtr myMap;\r\nfor (int i=0; i<1000; i+=11)\r\n{\r\n  CString strKey;\r\n  strKey.Format(_T(\"%05d\"),i);\r\n  myMap[strKey] = NULL;\r\n}<\/pre>\n
Das erschreckende Ergebnis der Verteilung ist bei einem Unicode wie auch MBCS Projekt:<\/p>\n
TMyMap<class CMapStringToPtr>::DumpMap\r\nBucket  0 =  0\r\nBucket  1 =  0\r\nBucket  2 =  0\r\nBucket  3 =  0\r\nBucket  4 =  0\r\nBucket  5 =  0\r\nBucket  6 =  0\r\nBucket  7 =  0\r\nBucket  8 = 36\r\nBucket  9 =  0\r\nBucket 10 =  0\r\nBucket 11 =  0\r\nBucket 12 =  0\r\nBucket 13 =  0\r\nBucket 14 = 55\r\nBucket 15 =  0\r\nBucket 16 =  0<\/pre>\n
Wie gut, dass auch die String Variante von HashKey \u00fcberarbeitet wird.<\/p>\n
BTW: Da die internen Strukturen protected sind muss man zu einem kleinen Trick greifen um die Verteilung ausgeben zu k\u00f6nnen. Ich habe dazu ein template verwendet, dass f\u00fcr alle MFC Maps funktioniert.<\/p>\n
template<class TBase> class TMyMap : public TBase\r\n{\r\npublic:\r\n  void DumpMap()\r\n  {\r\n    TRACE(__FUNCTION__ \"\\n\");\r\n    if (m_pHashTable)\r\n    {\r\n      for (size_t i=0; i<m_nHashTableSize; ++i)\r\n      {\r\n        int iCount = 0;\r\n        for (CAssoc *p = m_pHashTable[i]; p; p=p->pNext)\r\n          ++iCount;\r\n        TRACE(\"Bucket %2d = %4d\\n\", i, iCount);\r\n      }\r\n    }\r\n  }\r\n};<\/pre>\n
Merke: Wer Hashes verwendet sollte sich \u00fcber sein Hashverfahren wirklich gedanken machen.<\/p>\n
BTW: Sollte es den Leser meines Blogs langsam langweilen weil ich mich permanent mit Hash-Algorithmen aufhalte, der sei getr\u00f6stet: Dies war vorl\u00e4ufig mein letzter Beitrag zu CMap… \":mrgreen:\"<\/p>\n","protected":false},"excerpt":{"rendered":"
\u00a0Hash-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\u00e4ter TheOS) und dessen Index Dateiorganisation. Ich entwickelte hierf\u00fcr einen Patch in Assembler, der damals exakt in den x-Bytes der Kernels in … \u201eCMapStringTo… HashKey Implementierung in VC-2003\/5\/8 ist auch fragw\u00fcrdig\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[30,4,3,27,172],"tags":[99,352,36,44,171],"class_list":["post-502","post","type-post","status-publish","format-standard","hentry","category-c","category-mfc","category-programmieren","category-vs2008","category-vs2010","tag-bug","tag-mfc","tag-vs-2005","tag-vs-2008","tag-vs-2010"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/502","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/comments?post=502"}],"version-history":[{"count":0,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/posts\/502\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/media?parent=502"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/categories?post=502"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.m-ri.de\/index.php\/wp-json\/wp\/v2\/tags?post=502"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}