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;
};
关于哈希函数
从前面的例子中可以看出，哈希函数首当其冲地承担了负载。哈希函数可以尽可能快，但它很可能非常容易发生碰撞。反之亦然，一个哈希函数可以尽可能的抗碰撞，但它的计算复杂度将不足以满足所执行的任务。让我们考虑两个极端的例子。例1，可能是最快的散列函数。
将总是返回相同的数字。如果我们的字典只存储一个词，那么它的工作就足够了，因为这个词将位于索引0。然而，如果我们有10个词，那么所有10个词都将在索引0处（别忘了我们有一个数组的数组）。
对于第二个例子，让我们转向一个可逆的加密，例如，基于轮数为N的Feistel网络。这不是一个哈希函数，它完全不受碰撞的影响。也就是说，对于两个不同的字符串，我们将得到保证不同的数字。获得的数字的长度将等于字符串的长度。因此，如果字符串的长度为1000个字符，我们将得到一个大小为1000的数组ugar。如果我们需要将这个字符串存储在一个3元素的字典中，你不觉得计算这样一个复杂的代码来寻找一个只有三个元素的词是很奇怪的吗？
因此，我们应该始终寻找一个快乐的媒介（正如fxsaber正确指出的那样）：我们需要一个快速计算哈希值的函数，通常 不会出现碰撞。让我们估计一下我们之前的哈希函数的碰撞概率。
字母表里有26个字符。我们假设以符号'a'开头的单词数等于以任何其他符号开头的单词数。那么，如果我们的字典包含988个词，其中38个以a 开头，38个以b 开头，38个以c 开头，......。38个为字母w，38个为字母-z。在每种情况下，发生碰撞的概率为1/26或3.8461%。如果我们有988个词，那么我们得到988*3.8461=37.999个词/索引。
很明显，一个相同字母的词越多，就越难找到一个特定的词。在我们的案例中，我们不仅要计算第一个字母的索引，还要搜索所有同样以相同字母开头的单词。为了避免这种情况，我们可以将哈希函数复杂化。
也就是我们取字的前两个字符。那么可能的组合将不是26，而是26^2=676。应该指出的是，计算哈希函数的第二个变体的复杂性已经线性增加，大致上是一半，而它的抗碰撞能力已经非线性增加，是一个平方。
对于第二种变体，平均每676个字就有一次碰撞。在我们的案例中，对于988个词，每个索引将有988/676=1.4615次碰撞。这意味着每个索引将平均包含一个词或两个词。因此，平均而言，将根本没有碰撞（一个比较），或者它们将非常短（两个比较）。
如果字典的大小与哈希函数的cobmins之比接近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的比率，即一个数组索引中只有一个字。因此我们可以说字典是数组的一个特例，它有一个键而不是一个索引。
数组的大小可以很容易地被改变，以配合字典的大小。
我没有考虑到无限的变体。
问题是，字典的大小往往是未知的。一个简单的例子，假设我们有一个交易的专家顾问。它跟踪所进行的交易。一旦一个交易出现在历史上，我们需要将这个交易与EA的Medjik联系起来。为此，使用字典是合乎逻辑的。其中，交易号码被用作键（唯一的标识符），而专家顾问的神奇号码被用作值。问题是，在EA开始时，我们无法事先确定我们是否会有100个交易、1000个交易或没有交易。无论你事先分配了多少内存，它要么太少，要么太多。
这就是问题所在：字典的大小往往是未知的。一个简单的例子，假设我们有一个顾问交易。它跟踪已执行的交易。当一个交易出现在历史上时，我们需要将这个交易与专家顾问的Medjack联系起来。为此，使用字典是合乎逻辑的。其中，交易号码被用作键（唯一的标识符），而专家顾问的神奇号码被用作值。问题是，在EA开始时，我们无法事先确定我们是否会有100个交易、1000个交易或没有交易。无论你事先分配了多少内存，它仍然会是太少或太多。
嗯，显然，有不同的任务。
我正在解决一个任务，我必须为一种人类语言创建一个方便的字典。我的数组的大小并不精确，但将其调整为特定语言的字数有什么问题？它可以很容易地装在那里。
例如，一种俄罗斯语言。假设它包含10 000个基数词。所有这些词都可以很好地融入我的阵列中。
第一个维度--66个字母（小的和大的），第二个维度--单词中的字母数（例如最多25个），第三个维度--与第一个字母和字母数相匹配--50。
整个语言将适合。
//----------------------------
最初，我正是在解决这个问题。你现在是在用另一个问题取代原来的问题，并说解决方案是不好的。
无论你事先分配了多少内存，它要么太少，要么太多。
对。
就像没有适用于所有任务的通用解决方案一样真实。
确实如此。
也确实没有一个放之四海而皆准的解决方案。
完全是无可争议的。
小声点，同志。没有人能够免于犯错，即使是你也不例外。所以要善于用柔和的语气指出别人的错误。我现在就去纠正它。
正确的人是否会一直是个秘密？
原则上不可能有一个正确的哈希表和哈希值的变体--它完全取决于具体的目的和应用条件。
这就像做一个三明治。也许有人不吃蛋黄酱或番茄酱，或者他是个素食主义者....。
但是把番茄酱放在桌子上，把面包铺在上面--这有点明显，这不是....。
关于这个问题的基础知识，供懒人参考。
https://www.slideshare.net/mkurnosov/6-32402313
在现实中，它要复杂得多，并在相关文献或良好的 "算法和数据结构 "课程中讨论。
简而言之，哈希函数的工作原理首先是：快速，其次是不需要发明非常复杂的东西，因为相同数值的出现通常在字典内通过直接蛮力解决。最主要的是不要有太频繁的碰撞，就这么简单。在Generic中，HashFunction.mqh文件中的一组函数负责基础类型的函数的散列。为了确保那里的一切都很简单，让我们看看它是如何组织的。
整数类型 要么按原样返回，要么对于短整数类型，使用非复杂的比特转换操作。对于不适合32位数的类型，使用排他性的或，然后是左-右连接。对于字符串来说，不复杂的哈希值也是通过直接蛮力来计算的。对于实数来说，一个位的表示是用union来表示的，它被用作哈希值。
词典型算法传统上被分为两部分。
什么是CHashSet？这是一个集合（数组的性质），每个元素都是唯一的。例如，这样一个集合可以包含数字2,5,1,7,10,15,1024。但没有两个数字可以相等。它还可以包含字符串、实数甚至是自定义的复杂类型（后面会有更多介绍）。但对任何类型的规则都是一样的--字典里不能有另一个相同的类型。
什么是CHashMap？它是一个集合（本质上也是一个数组），其中每个元素都是一个复杂的键值类型。
它的结构几乎与CHashMap完全一样，但允许两个集合之间的对应关系，即集合1的一个元素对应于集合2的一个元素。这是一个非常方便的事情，允许人们编写非常有效的查询算法，平均执行时间为O(1)。
稍后，我们会看一些例子，看看如何建立某种对应关系。
有趣的是，任何键值字典都自然而然地建立了这样一种非琐碎的关系，即一对多的 关系。例如，我们有一堆历史订单，和一堆基于这些订单执行的交易。每个交易只对应一个订单，但一个订单可以对应多个交易。这种关系的字典可以把交易的号码作为一个键来存储，并把开启交易的订单的号码作为一个值。