Mikhail Kurnosov, Associate Professor (Docent) Follow
www.slideshare.net
Лекция 6 Хеш-таблицы Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатик…
//+------------------------------------------------------------------+//| 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(constboolvalue)
{
return((value)?true:false);
}
//+------------------------------------------------------------------+//| Returns a hashcode for character. |//+------------------------------------------------------------------+int GetHashCode(constcharvalue)
{
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(constshortvalue)
{
return(((int)((ushort)value) | (((int)value) << 16)));
}
//+------------------------------------------------------------------+//| Returns a hashcode for unsigned short. |//+------------------------------------------------------------------+int GetHashCode(constushortvalue)
{
return((int)value);
}
//+------------------------------------------------------------------+//| Returns a hashcode for color. |//+------------------------------------------------------------------+int GetHashCode(const color value)
{
return((int)value);
}
//+------------------------------------------------------------------+//| Returns a hashcode for integer. |//+------------------------------------------------------------------+int GetHashCode(constintvalue)
{
return(value);
}
//+------------------------------------------------------------------+//| Returns a hashcode for unsigned integer. |//+------------------------------------------------------------------+ int GetHashCode(constuintvalue)
{
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(constlongvalue)
{
return(((int)((long)value)) ^ (int)(value >> 32));
}
//+------------------------------------------------------------------+//| Returns a hashcode for unsigned long. |//+------------------------------------------------------------------+ int GetHashCode(constulongvalue)
{
return(((int)value) ^ (int)(value >> 32));
}
//+------------------------------------------------------------------+//| Returns a hashcode for float. |//+------------------------------------------------------------------+int GetHashCode(constfloatvalue)
{
if(value==0)
{
//--- ensure that 0 and -0 have the same hash codereturn(0);
}
BitInterpreter convert;
convert.float_value=value;
return(convert.int_value);
}
//+------------------------------------------------------------------+//| Returns a hashcode for string. |//+------------------------------------------------------------------+int GetHashCode(constdoublevalue)
{
if(value==0)
{
//--- ensure that 0 and -0 have the same hash codereturn(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(conststringvalue)
{
int len=StringLen(value);
int hash=0;
//--- check length of stringif(len>0)
{
//--- calculate a hash as a fucntion of each charfor(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 objectreturn GetHashCode(typename(value));
}
}
//+------------------------------------------------------------------+
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;
};
ハッシュ関数について
これまでの例から、ハッシュ関数が負荷の大部分を担っていることは明らかです。ハッシュ関数は可能な限り高速にすることができますが、ほとんどの場合、非常に衝突しやすくなります。その逆も然りで、ハッシュ関数は可能な限り耐衝突性を高めることができるが、その計算量は実行されるタスクに対して不十分なものとなる。2つの極端な例を考えてみましょう。例1、最速のハッシュ関数。
常に同じ番号を返します。もし、この辞書が1つの単語だけを格納するのであれば、この単語はインデックス0に配置されるので、その作業は十分である。しかし、もし10個の単語があれば、10個の単語はすべてインデックス0になります（配列の中の配列であることを忘れないでください）。
2番目の例として、ラウンド数NのFeistelネットワークに 基づく可逆的な暗号化について考えてみよう。ハッシュ関数ではないので、衝突の心配は全くない。つまり、2つの異なる文字列に対して、異なる数値が保証されることになる。得られた数値の長さは、文字列の長さと同じになる。したがって、文字列の長さが1000文字であれば、サイズ1000の配列ucharを得ることになる。この文字列を3要素の辞書に格納する必要があるとして、たった3要素で単語を探すためにこんな複雑なコードを計算するのはおかしいと思いませんか？
したがって、（fxsaberが正しく指摘しているように）我々は常に幸せな媒体を探すべきです：我々は、ハッシュを素早く計算し、通常は 衝突が発生しない関数を必要としています。先ほどのハッシュ関数について、衝突の確率を推定してみましょう。
アルファベットは26文字です。記号「a」で始まる単語の数と、それ以外の記号で始まる単語の数が等しいとする。そして、この辞書に988個の単語が含まれているとすると、そのうち38個はaで 始まり、38個はbで 始まり、38個はcで 始まり、...となります。wに 38個、-zに 38個。それぞれのケースで衝突が発生する確率は1/26、つまり3.8461%となる。仮に988語であれば、1インデックスあたり988*3.8461=37.999語が得られる。
1つの同じ文字を表す単語が多ければ多いほど、特定の単語を見つけるのが難しくなることは明らかです。この場合、最初の文字のインデックスを計算するだけでなく、同じ文字で始まるすべての単語を検索する必要があります。これを避けるには、ハッシュ関数を複雑にすればよい。
つまり、単語の最初の2文字を取るのです。そうすると、可能な組み合わせは26ではなく、26^2=676になります。ハッシュ関数の計算の複雑さは直線的に、おおよそ半分になったが、衝突に対する耐性は非直線的に2乗倍になったことに注目したい。
2つ目のバリエーションでは、平均して676ワードに1つの衝突が発生することになります。今回の場合、988語の場合、1インデックスあたり988/676=1.4615の衝突が発生することになる。つまり、各インデックスには、平均して1語または2語が含まれることになる。つまり、平均すると衝突が全くないか（比較1回）、非常に短いか（比較2回）になります。
辞書のサイズとハッシュ関数のコブミンの比率が1.0000000に 近い場合、平均してブルートフォースは必要なく、各要素はそれ自体のインデックスに位置することになるからである。ハッシュ関数が非常に大きな値の範囲を提供する場合、ハッシュ関数の可能な組み合わせに対する辞書のサイズの比率は常に1.0よりさらに小さくなる。例えば、ハッシュ関数が2^32の組み合わせを生成する場合、2^32より小さい任意のサイズNに対して、比率N/2^32 < 1.0が成立する。Nが非常に小さい場合は、ハッシュ関数で得られる数を単純に正規化し、常にNの極限値になるようにすればよい。
int index = GetHashCode(word)%ArraySize(m_array);ハッシュ関数が一様に結果を生成する場合、平均して1.000の比率になる。つまり、1つの配列インデックスには1つの単語しか存在しないことになる。したがって、辞書は、インデックスの代わりにキーを持つ配列の特殊なケースであると言うことができる。
配列の大きさは、辞書の大きさに合わせて簡単に変更することができます。
無限変種は考慮していない。
ポイントは、辞書のサイズが不明な場合が多いことです。簡単な例ですが、Expert Advisorでトレードを行うとします。実行された取引を追跡します。履歴に取引が表示されたら、その取引とEAのメジックを紐付ける必要があります。そのためには、辞書を使うのが筋である。ここで、取引番号はキー（一意の識別子）として使用され、Expert Advisorのマジックナンバーは値として使用されます。問題は、EAの開始時に、100回取引するのか、1000回取引するのか、それとも取引しないのか、事前に決定できないことです。事前にどんなメモリを割り当てたとしても、少なすぎるか多すぎるかのどちらかです。
それは、辞書のサイズが不明であることが多いということです。簡単な例ですが、アドバイザーが取引をしているとします。実行された取引を追跡します。履歴に取引が表示されたら、この取引とExpert AdvisorのMedjackを紐づける必要があります。そのためには、辞書を使うのが筋である。ここで、取引番号はキー（一意の識別子）として使用され、Expert Advisorのマジックナンバーは値として使用されます。問題は、EAの開始時に、100回取引するのか、1000回取引するのか、それとも取引しないのか、事前に決定できないことです。いくら事前にメモリを確保しても、少なすぎるか多すぎるかのどちらかです。
まあ、当然ながら、さまざまなタスクがあります。
ある人語の便利な辞書を作るという課題を解いていました。配列のサイズは正確ではありませんが、特定の言語の単語数に合わせることに何か問題があるのでしょうか？簡単に入れることができます。
例えばロシア語。仮に10,000語の基本語が入っているとする。これらの言葉はすべて、私の配列にうまく当てはめることができます。
1次元目-66文字（大小）、2次元目-単語の文字数（例えば25文字まで）、3次元目-1文字目と文字数-50文字が一致します。
全言語が収まる。
//----------------------------
当初は、まさにこの問題を解決していたのです。あなたは今、本来の問題を別の問題にすり替えて、解決策がダメだと言っているのです。
いくら事前にメモリを確保しても、少なすぎるか 多すぎるかのどちらかです。
そうですね。
すべてのタスクに対応する普遍的なソリューションが存在しないのと同じように。
本当です。
また、万能なソリューションがないことも事実です。
完全に議論の余地がない。
同志よ、声を小さくしてください。誰もミスから免れることはできません、あなたでさえも。だから、もっと柔らかい口調で、他人の間違いを指摘する優しさを持ちましょう。これから訂正します。
正解は秘密のままなのでしょうか？
ハッシュテーブルやハッシュは、原理的に正しいバリエーションが存在するわけではなく、特定の目的やアプリケーションの条件によってすべてが決まる。
サンドイッチを作るようなものです。マヨネーズやケチャップを食べない人がいるかもしれないし、ビーガンかもしれないし......。
でも、テーブルにケチャップを置いて、パンを敷いて......というのは、なんとなくわかるような気がします。
怠け者のための基礎知識。
https://www.slideshare.net/mkurnosov/6-32402313
実際にはもっと複雑で、関連する文献や「アルゴリズムとデータ構造」の講座で議論されている。
つまり、ハッシュ関数は、第一に早く動作すること、第二に、同じ値の出現は通常、直接ブルートフォースによって辞書内で解決されるので、非常に複雑なものを考案する必要がないこと、である。要は、あまり頻繁に衝突しないようにすること、それだけです。Genericでは、HashFunction.mqhファイル内の関数群が、基本型の関数のハッシュを担当する。そこですべてがシンプルであることを確認するために、どのように構成されているかを見てみましょう。
整数型は そのまま返すか、短整数型は複雑でないビット単位の変換演算を行う。32桁に収まらない型は、排他的論理和とそれに続く左右の結合を使用する。文字列の場合、単純なハッシュは直接ブルートフォースでも計算される。実数の場合はビット表現を和集合で取り、それをハッシュとして使用する。
辞書型アルゴリズムは、従来、2つのパートに分かれていた。
CHashSetとは？各要素が一意であるコレクション（その性質上、配列）である。例えば、このようなコレクションには、2,5,1,7,10,15,1024の数字を含めることができます。しかし、2つの数字が等しくなることはない。また、文字列、実数、さらにはカスタムの複合型（詳細は後述）を含めることができる。しかし、このルールはどのタイプでも同じで、辞書に同じタイプのものが他に存在することはできません。
CHashMapとは？これはコレクション（本来は配列でもある）であり、各要素は複雑なキー・バリュー型である。
CHashMapとほぼ同じ構造だが、集合1の要素が集合2の要素に対応するような、2つの集合間の対応を許す。 これは非常に便利なもので、平均実行時間O(1)の非常に効率の良い問い合わせアルゴリズムが書ける。
後ほど、例題を見て、何らかの対応関係を構築する方法を考えてみましょう。
興味深いことに、どのようなKey-Value辞書でも、1対多の ような自明でない関係が自然に確立される。例えば、過去の注文の束と、それに基づいて実行されたトレードの束があります。1つの取引は1つの注文にしか対応しませんが、1つの注文は複数の取引に対応することができます。このような関係の辞書には、キーとして取引番号、値としてその取引を開始した注文番号を格納することができる。