Generische Klassenbibliothek - Bugs, Beschreibung, Fragen, Nutzungsmöglichkeiten und Vorschläge - Seite 10

[Vasiliy Sokolov]

Über Hash-Funktionen

Aus den vorangegangenen Beispielen ist ersichtlich, dass die Hash-Funktion die Hauptlast trägt. Eine Hash-Funktion kann so schnell wie möglich sein, aber sie ist höchstwahrscheinlich sehr kollisionsanfällig. Umgekehrt kann eine Hash-Funktion zwar so kollisionssicher wie möglich gemacht werden, aber ihre Rechenkomplexität wird der zu erfüllenden Aufgabe nicht gerecht. Betrachten wir zwei extreme Beispiele. Beispiel 1, die schnellstmögliche Hash-Funktion:

int GetHashCode(string word)
{
   return 0;
}

Es wird immer dieselbe Zahl zurückgegeben. Wenn unser Wörterbuch nur ein einziges Wort speichert, dann reicht seine Arbeit aus, denn dieses Wort befindet sich bei Index 0. Wenn wir jedoch 10 Wörter haben, dann befinden sich alle zehn Wörter bei Index 0 (vergessen Sie nicht, dass wir ein Array von Arrays haben).

Für das zweite Beispiel wenden wir uns einer umkehrbaren Verschlüsselung zu, z. B. auf der Grundlage eines Feistel-Netzwerks mit einer Anzahl von Runden N. Es handelt sich dabei nicht um eine Hash-Funktion, und sie ist überhaupt nicht kollisionsgefährdet. D.h. für zwei unterschiedliche Zeichenketten erhalten wir garantiert unterschiedliche Zahlen. Die Länge der erhaltenen Zahlen ist gleich der Länge der Zeichenkette. Wenn also die Zeichenkette 1000 Zeichen lang ist, erhalten wir ein Array uchar mit der Größe 1000. Wenn wir diese Zeichenfolge in einem Wörterbuch mit drei Elementen speichern müssen, wäre es dann nicht seltsam, einen so komplexen Code zu berechnen, um ein Wort mit nur drei Elementen zu finden?

Daher sollten wir immer nach einem goldenen Mittelweg suchen (wie von fxsaber zu Recht hervorgehoben): Wir brauchen eine Funktion, die schnell Hashes berechnet und normalerweise keine Kollisionen verursacht. Schätzen wir die Wahrscheinlichkeit von Kollisionen für unsere vorherige Hash-Funktion:

int GetHashCode(string word)
{
   int index = StringGetCharacter(word, 0)-'a';
}

Das Alphabet besteht aus 26 Zeichen. Nehmen wir an, dass die Anzahl der Wörter, die mit dem Symbol "a" beginnen, gleich der Anzahl der Wörter ist, die mit irgendeinem anderen Symbol beginnen. Wenn unser Wörterbuch also 988 Wörter enthält, beginnen 38 davon mit a, 38 mit b, 38 mit c, ... 38 für den Buchstaben w und 38 für den Buchstaben - z. Die Wahrscheinlichkeit eines Zusammenstoßes wäre in jedem Fall 1/26 oder 3,8461%. Wenn wir 988 Wörter haben, erhalten wir 988*3,8461 = 37,999 Wörter pro Index.

Es ist klar, dass es umso schwieriger ist, ein bestimmtes Wort zu finden, je mehr Wörter es für ein und denselben Buchstaben gibt. In unserem Fall müssen wir nicht nur den Index des ersten Buchstabens berechnen, sondern auch nach allen Wörtern suchen, die mit demselben Buchstaben beginnen. Um dies zu vermeiden, können wir die Hash-Funktion komplizierter gestalten:

int GetHashCode(string word)
{
   uchar i1 = (uchar)word[0]-'a';
   uchar i2 = (uchar)word[1]-'a';
   int hash = i1<<(sizeof(uchar)*8);
   hash += i2;
   return hash;
}

Das heißt, wir nehmen die ersten beiden Buchstaben des Wortes. Dann sind die möglichen Kombinationen nicht 26, sondern 26^2 = 676. Es ist anzumerken, dass die Komplexität der zweiten Variante der Hashfunktion linear, d. h. um die Hälfte, gestiegen ist, während die Kollisionssicherheit nichtlinear, d. h. um ein Quadrat, zugenommen hat.

Bei der zweiten Variante käme im Durchschnitt eine Kollision auf 676 Wörter. In unserem Fall würde es bei 988 Wörtern 988/676 = 1,4615 Kollisionen pro Index geben. Das bedeutet, dass jeder Index im Durchschnitt entweder ein Wort oder 2 Wörter enthält. Im Durchschnitt gibt es also gar keine Kollisionen (ein Vergleich), oder sie sind sehr kurz (zwei Vergleiche).

Wenn das Verhältnis zwischen der Größe des Wörterbuchs und der Anzahl der Hash-Funktionen nahe bei 1,0000000 liegt, ist im Durchschnitt keine Brute-Force-Methode erforderlich, da jedes Element von selbst an seinem eigenen Index gefunden wird. Wenn eine Hash-Funktion einen sehr großen Wertebereich liefert, wird das Verhältnis zwischen der Größe des Wörterbuchs und den möglichen Kombinationen der Hash-Funktion immer kleiner als 1,0 sein. Wenn zum Beispiel eine Hash-Funktion 2^32 Kombinationen erzeugt, dann gilt für jede Größe N kleiner als 2^32 das Verhältnis N/2^32 < 1,0. Wenn N sehr klein ist, normalisieren wir einfach die von der Hash-Funktion erhaltene Zahl, so dass sie immer im Grenzwert von N liegt:

int index = GetHashCode(word)%ArraySize(m_array);

Wenn die Hash-Funktion gleichmäßig Ergebnisse erzeugt, erhalten wir im Durchschnitt ein Verhältnis von 1,000, d.h. es gibt nur ein Wort in einem Array-Index. Ein Wörterbuch ist also ein Spezialfall eines Arrays mit einem Schlüssel anstelle eines Indexes.

[Vasiliy Sokolov]

Tag Konow:

Die Größe des Arrays kann leicht an die Größe des Wörterbuchs angepasst werden.

Ich berücksichtige keine unendlichen Varianten.

Das Problem ist, dass der Umfang des Wörterbuchs oft unbekannt ist. Ein einfaches Beispiel: Nehmen wir an, wir haben einen Expert Advisor, der Handel treibt. Es verfolgt die durchgeführten Geschäfte. Sobald ein Handel in der Historie erscheint, müssen wir diesen Handel mit der Medjik des EAs verbinden. Hierfür ist es logisch, das Wörterbuch zu verwenden. Dabei wird die Handelsnummer als Schlüssel (eindeutiger Bezeichner) und die magische Zahl des Expert Advisors als Wert verwendet. Das Problem ist, dass wir beim Start des EA nicht im Voraus bestimmen können, ob wir 100, 1000 oder gar keine Trades haben werden. Egal, wie viel Speicher Sie im Voraus zuweisen, es wird entweder zu wenig oder zu viel sein.

[Реter Konow]

Vasiliy Sokolov:

Das ist das Problem: Der Umfang des Wörterbuchs ist oft unbekannt. Ein einfaches Beispiel: Nehmen wir an, wir haben einen Berater, der handelt. Sie verfolgt die ausgeführten Geschäfte. Wenn ein Handel in der Historie erscheint, müssen wir diesen Handel mit dem Medjack des Expert Advisors verbinden. Hierfür ist es logisch, das Wörterbuch zu verwenden. Dabei wird die Handelsnummer als Schlüssel (eindeutiger Bezeichner) und die magische Zahl des Expert Advisors als Wert verwendet. Das Problem ist, dass wir beim Start des EA nicht im Voraus bestimmen können, ob wir 100, 1000 oder gar keine Trades haben werden. Egal, wie viel Speicher Sie vorher zuweisen, es wird immer entweder zu wenig oder zu viel sein.

Natürlich gibt es unterschiedliche Aufgaben.

Ich habe eine Aufgabe gelöst, bei der ich ein praktisches Wörterbuch für eine menschliche Sprache erstellen musste. Die Größe meines Arrays ist nicht exakt, aber wo ist das Problem, wenn ich es an die Anzahl der Wörter einer bestimmten Sprache anpasse? Er kann dort problemlos untergebracht werden.

Zum Beispiel eine russische Sprache. Angenommen, sie enthält 10 000 Grundwörter. Alle diese Wörter passen gut in meine Reihe.

Die erste Dimension - 66 Buchstaben (klein und groß), die zweite Dimension - die Anzahl der Buchstaben in dem Wort (bis zu 25 zum Beispiel), die dritte Dimension - entspricht dem ersten Buchstaben und die Anzahl der Buchstaben - 50.

Die ganze Sprache wird passen.

//----------------------------

Ursprünglich war ich dabei, genau dieses Problem zu lösen. Sie ersetzen jetzt das ursprüngliche Problem durch ein anderes und sagen, dass die Lösung nicht gut ist.

[Реter Konow]

Vasiliy Sokolov:

Egal, wie viel Speicher Sie vorher zuweisen, es wird entweder zu wenig oder zu viel sein.

Richtig.

Genauso wenig wie es eine Universallösung für alle Aufgaben gibt.

[Alexey Viktorov]

Tag Konow:

Das stimmt.

Es stimmt auch, dass es keine Einheitslösung gibt, die für alle passt.

Völlig unbestreitbar.

[Vasiliy Sokolov]

Sergey Dzyublik:

Sprechen Sie leise, Genosse. Niemand ist vor Fehlern gefeit, auch Sie nicht. Seien Sie also so freundlich, die Fehler der anderen in einem sanfteren Ton aufzuzeigen. Ich werde sie jetzt korrigieren.

[Sergey Dzyublik]

Alexey Viktorov:

Wird der Richtige ein Geheimnis bleiben?

Es kann keine prinzipiell richtige Variante von Hash-Tabellen und Hashes geben - alles hängt von spezifischen Zwecken und Anwendungsbedingungen ab.
Das ist wie ein Sandwich zu machen. Vielleicht isst jemand weder Mayonnaise noch Ketchup, oder er ist Veganer....
Aber Ketchup auf den Tisch zu stellen und Brot darauf zu legen - das ist irgendwie klar, dass es nicht....


Grundlagen zum Thema für Faule:
https://www.slideshare.net/mkurnosov/6-32402313

In Wirklichkeit ist es viel komplizierter und wird in der einschlägigen Literatur oder in guten "Algorithmen und Datenstrukturen"-Kursen behandelt.

[Vasiliy Sokolov]

Kurz gesagt, die Hash-Funktion sollte erstens schnell funktionieren und zweitens ist es nicht nötig, etwas sehr Kompliziertes zu erfinden, da das Auftreten gleicher Werte im Wörterbuch normalerweise mit direkter roher Gewalt gelöst wird. Das Wichtigste ist, dass es nicht zu viele Kollisionen gibt, das ist alles. In Generic ist eine Reihe von Funktionen in der Datei HashFunction.mqh für den Hash von Funktionen von Basistypen zuständig. Um sicherzugehen, dass dort alles einfach ist, sehen wir uns an, wie es organisiert ist:

//+------------------------------------------------------------------+
//|                                                 HashFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| Unioun BitInterpreter.                                           |
//| Usage: Provides the ability to interpret the same bit sequence in|
//|        different types.                                          |
//+------------------------------------------------------------------+
union  BitInterpreter
  {
   bool              bool_value;
   char              char_value;
   uchar             uchar_value;
   short             short_value;
   ushort            ushort_value;
   color             color_value;
   int               int_value;
   uint              uint_value;
   datetime          datetime_value;
   long              long_value;
   ulong             ulong_value;
   float             float_value;
   double            double_value;
  };
//+------------------------------------------------------------------+
//| Returns a hashcode for boolean.                                  |
//+------------------------------------------------------------------+
int GetHashCode(const bool value)
  {
   return((value)?true:false);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for character.                                |
//+------------------------------------------------------------------+
int GetHashCode(const char value)
  {
   return((int)value | ((int)value << 16));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned character.                       |
//+------------------------------------------------------------------+
int GetHashCode(const uchar value)
  {
   return((int)value | ((int)value << 16));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for short.                                    |
//+------------------------------------------------------------------+
int GetHashCode(const short value)
  {
   return(((int)((ushort)value) | (((int)value) << 16)));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned short.                           |
//+------------------------------------------------------------------+
int GetHashCode(const ushort value)
  {
   return((int)value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for color.                                    |
//+------------------------------------------------------------------+
int GetHashCode(const color value)
  {
   return((int)value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for integer.                                  |
//+------------------------------------------------------------------+
int GetHashCode(const int value)
  {
   return(value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned integer.                         |
//+------------------------------------------------------------------+ 
int GetHashCode(const uint value)
  {
   return((int)value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for datetime.                                 |
//+------------------------------------------------------------------+
int GetHashCode(const datetime value)
  {
   long ticks=(long)value;
   return(((int)ticks) ^ (int)(ticks >> 32));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for long.                                     |
//+------------------------------------------------------------------+
int GetHashCode(const long value)
  {
   return(((int)((long)value)) ^ (int)(value >> 32));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned long.                            |
//+------------------------------------------------------------------+  
int GetHashCode(const ulong value)
  {
   return(((int)value) ^ (int)(value >> 32));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for float.                                    |
//+------------------------------------------------------------------+
int GetHashCode(const float value)
  {
   if(value==0)
     {
      //--- ensure that 0 and -0 have the same hash code
      return(0);
     }
   BitInterpreter convert;
   convert.float_value=value;
   return(convert.int_value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for string.                                   |
//+------------------------------------------------------------------+
int GetHashCode(const double value)
  {
   if(value==0)
     {
      //--- ensure that 0 and -0 have the same hash code
      return(0);
     }
   BitInterpreter convert;
   convert.double_value=value;
   long lvalue=convert.long_value;
   return(((int)lvalue) ^ ((int)(lvalue >> 32)));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for string.                                   |
//| The hashcode for a string is computed as:                        |
//|                                                                  |
//| s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]                     |
//|                                                                  |
//| using int arithmetic, where s[i] is the ith character of the     |
//| string, n is the length of the string, and ^ indicates           |
//| exponentiation. (The hash value of the empty string is zero.)    |
//+------------------------------------------------------------------+
int GetHashCode(const string value)
  {
   int len=StringLen(value);
   int hash=0;
//--- check length of string
   if(len>0)
     {
      //--- calculate a hash as a fucntion of each char
      for(int i=0; i<len; i++)
         hash=31*hash+value[i];
     }
   return(hash);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }
//+------------------------------------------------------------------+

Die ganzzahligen Typen werden entweder so zurückgegeben, wie sie sind, oder für kurze ganzzahlige Typen werden nicht komplizierte bitweise Umwandlungsoperationen verwendet. Für Typen, die nicht in 32 Ziffern passen, wird ein exklusives oder gefolgt von einer Links-Rechts-Verknüpfung verwendet. Bei Zeichenketten wird ein unkomplizierter Hash auch direkt mit roher Gewalt berechnet. Für reelle Zahlen wird eine Bit-Darstellung mit Union genommen und als Hash verwendet.

[Vasiliy Sokolov]

Algorithmen vom Typ Wörterbuch werden üblicherweise in zwei Teile unterteilt:

• Schlüssel-Wert-Paar-Sets, bei denen der Schlüssel eindeutig ist und der Wert nicht. In Generic ist dies CHashMap
• Sätze von eindeutigen Werten. In Generic ist dies CHashSet.

Was ist ein CHashSet? Es handelt sich um eine Sammlung (von Natur aus ein Array), in der jedes Element eindeutig ist. Eine solche Sammlung kann zum Beispiel die Zahlen 2,5,1,7,10,15,1024 enthalten. Aber keine zwei Zahlen können gleich sein. Sie kann auch Zeichenketten, reelle Zahlen und sogar benutzerdefinierte komplexe Typen enthalten (dazu später mehr). Aber die Regel ist dieselbe für jeden Typ - es kann keinen anderen des gleichen Typs im Wörterbuch geben.

Was ist CHashMap? Es handelt sich um eine Sammlung (von Natur aus auch ein Array), bei der jedes Element ein komplexer Schlüssel-Wert-Typ ist:

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected:
   int               m_buckets[];
   Entry<TKey,TValue>m_entries[];
   int               m_count;
   int               m_free_list;
   int               m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool              m_delete_comparer;
};

Sie ist fast genau wie CHashMap strukturiert, erlaubt aber eine Korrespondenz zwischen zwei Mengen, so dass ein Element der Menge 1 einem Element der Menge 2 entspricht. Das ist eine sehr praktische Sache, mit der man sehr effiziente Abfragealgorithmen mit einer durchschnittlichen Ausführungszeit von O(1) schreiben kann.

Später werden wir anhand von Beispielen sehen, wie man eine Art von Korrespondenz aufbauen kann.

Interessanterweise stellt jedes Schlüssel-Wert-Wörterbuch natürlich eine solche nicht-triviale Beziehung her, nämlicheins zu vielen. Wir haben zum Beispiel eine Reihe von historischen Aufträgen und eine Reihe von Geschäften, die auf der Grundlage dieser Aufträge ausgeführt wurden. Jedes Geschäft entspricht nur einem Auftrag, aber ein Auftrag kann mehreren Geschäften entsprechen. Das Wörterbuch einer solchen Beziehung kann als Schlüssel die Nummer des Geschäfts und als Wert die Nummer des Auftrags, mit dem es eröffnet wurde, speichern.

[Artyom Trishkin]

Bitte lenken Sie den Thread nicht vom Thema ab.