通用类库 - 错误、说明、问题、使用功能和建议 - 页 35

 
Renat Fatkhullin:

几乎是不可能的,如果你碰到了,访问仍然是超级有效的。

在任何效率水平上的碰撞都是不好的。谢谢你的答复。我会牢记这一点。

 
fxsaber:

在任何效率水平上的碰撞都是不好的。谢谢你的答复。我会牢记这一点。

根据定义,哈希图不是无碰撞的。

 
fxsaber #:

关于碰撞的问题。在这种情况下,有可能遇到碰撞吗?

如果已经制作了27000份记录。

你会不断得到碰撞,特别是当集合增长(调整大小)时。由于哈希值被额外地截断为帮派号码,而它们的数量总是有限的(理想情况下等于1)。

结论。

1.对地图来说,重要的不是哈希函数的密码学稳定性,而是它的速度。哈希函数只需要提供一个良好的随机性,就可以了。

2.最好通过各种手段避免调整大小。导致主要缩减的是尺寸的调整,而不是哈希函数的碰撞。只要有可能,总是用一个预设的项目数来初始化集合。即使你不确切知道它们,也要给出一个大概的数字--这将大大有助于算法。

3.碰撞是一种常规的压实机制。通过碰撞,有可能将三条id为159、4'569'209、29'459'876的记录存储在长度为3的数组中,而不是长度为30 000 000的数组中,即使最后两个值都落入索引为2的帮组中。

 
Vasiliy Sokolov #:

2.最好通过各种方式避免调整大小。主要的缺点是调整大小,而不是哈希函数的碰撞。只要有可能,就用一个预设的项目数来初始化这个集合。即 使你不确切知道它们,也要给出一个大概的数字--这对算法会有很大帮助。

请以实例说明。

到目前为止,我只使用这个。

//+------------------------------------------------------------------+
//| Adds the specified key and value to the map.                     |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(TKey key,TValue value);
//+------------------------------------------------------------------+
//| Gets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TryGetValue(TKey key,TValue &value);
 
fxsaber #:

请给我看一个例子。

到目前为止,我只使用这个。

当你创建一个CHashMap集合时,使用其中一个接受容量参数的构造函数。关于调整大小时的性能细节,请看我关于CDicionary的文章。对这种算法有一个完整的演练。

 

我在CHashMap中发现了一个非常不寻常的行为。

// Демонстрация невозможности доступа по ключу после первого добавления.

#include <Generic\HashMap.mqh>

void OnStart()
{
  // Отсортированный массив неповторяющихся цен.
  const double Array[] =
{1.70682, 1.70691, 1.70700, 1.70709, 1.70710, 1.70717, 1.70721, 1.70742, 1.70749, 1.70752, 1.70757, 1.70766, 1.70768, 1.70769, 1.70771, 1.70773, 1.70774, 1.70777,
 1.70782, 1.70785, 1.70786, 1.70797, 1.70804, 1.70808, 1.70813, 1.70850, 1.70868, 1.70879, 1.70881, 1.70883, 1.70895, 1.70905, 1.70918, 1.70921, 1.70936, 1.70962,
 1.70966, 1.71022, 1.71027, 1.71047, 1.71056, 1.71080, 1.71081, 1.71093, 1.71096, 1.71109, 1.71112, 1.71119, 1.71120, 1.71127, 1.71128, 1.71135, 1.71136, 1.71138,
 1.71145, 1.71147, 1.71148, 1.71150, 1.71155, 1.71159, 1.71162, 1.71164, 1.71168, 1.71172, 1.71203, 1.71204, 1.71210, 1.71269, 1.71289, 1.71293, 1.71299, 1.71334,
 1.71337, 1.71343, 1.71357, 1.71358, 1.71367, 1.71371, 1.71374, 1.71380, 1.71402, 1.71410, 1.71414, 1.71425, 1.71426, 1.71427, 1.71429, 1.71430, 1.71446, 1.71474,
 1.71477, 1.71518, 1.71521, 1.71558, 1.71587, 1.71588, 1.71617, 1.71620, 1.71624, 1.71626, 1.71629, 1.71635, 1.71644, 1.71654, 1.71655, 1.71658, 1.71661, 1.71664,
 1.71689, 1.71700, 1.71712, 1.71718, 1.71727, 1.71752, 1.71769, 1.71775, 1.71780, 1.71782, 1.71786, 1.71792, 1.71795, 1.71797, 1.71798, 1.71801, 1.71815, 1.71827,
 1.71832, 1.71835, 1.71841, 1.71869, 1.71895, 1.71908, 1.71951, 1.71984, 1.71992, 1.72008, 1.72086, 1.72132, 1.72147, 1.72204, 1.72208, 1.72212, 1.72215, 1.72227,
 1.72230, 1.72233, 1.72234, 1.72336, 1.72374, 1.72378, 1.72381, 1.72405, 1.72454, 1.72464, 1.72477, 1.72488, 1.72541, 1.72553, 1.72562, 1.72588, 1.72625, 1.72651,
 1.72653, 1.72671, 1.72679, 1.72685, 1.72720, 1.72783, 1.72849, 1.72852, 1.72854, 1.72925, 1.72927, 1.72938, 1.72953, 1.72956, 1.72960, 1.72970, 1.72975, 1.72979,
 1.72996, 1.73014, 1.73028, 1.73034, 1.73050, 1.73056, 1.73084, 1.73085, 1.73119, 1.73137, 1.73176, 1.73278, 1.73328, 1.73337, 1.73344, 1.73345, 1.73362, 1.73377,
 1.73385, 1.73399, 1.73401, 1.73405, 1.73425, 1.73432, 1.73445, 1.73446, 1.73447, 1.73451, 1.73458, 1.73468, 1.73491, 1.73512, 1.73515, 1.73516, 1.73537, 1.73545,
 1.73553, 1.73580, 1.73581, 1.73598, 1.73611, 1.73630, 1.73635, 1.73643, 1.73658, 1.73678, 1.73694, 1.73695, 1.73698, 1.73712, 1.73713, 1.73721, 1.73746, 1.73748,
 1.73750, 1.73751, 1.73781, 1.73782, 1.73789, 1.73821, 1.73843, 1.73845, 1.73854, 1.73857, 1.73858, 1.73861, 1.73874, 1.73892, 1.74003, 1.74060, 1.74062};

  CHashMap<double, int> Index; // Будем по double-ключу хранить int-значения.
  
  for (int i = ArraySize(Array) - 1; i >= 0; i--)
    Index.Add(NormalizeDouble(Array[i], 5), 0); // Каждую цену массива используем в качестве ключа.
    
  // Все это было подготовкой, чтобы продемонстрировать поведение ниже.
  
  const double Price = 1.75141; // Берем новую цену.
  
  if (Index.Add(Price, 0)) // Если получилось добавить ее в качестве ключа.
  {
    int Value = 0;

    Print(Index.TryGetValue(Price, Value)); // (false) Проверяем, получается ли посмотреть данные по этому ключу.
    
    if (Index.Add(Price, 0)) // Пробуем повторно добавить в качестве ключа
      Print(Index.TryGetValue(Price, Value)); // (true) Проверяем, получается ли посмотреть данные по этому ключу.
  }
}


false
true

看来,据说添加了一个钥匙,但无法从中读取任何东西。然而,只要我再次添加钥匙,它就变得可读了!这时,我就会发现,在我的电脑上,有很多东西都是可读的。

这是一个BAG吗?


如果你把例子中的价格1.75141 换成另一个价格,它就会正常工作。


没有调试的情况下,要在庞大的代码中发现这种行为,并创造这样一个简明的例子,简直是地狱般的困难。

 
Vasiliy Sokolov #:

只要有可能,总是用预先确定的元素数量来初始化集合。即使你不确切知道它们,也要给出一个大概的数字--这对算法会有很大帮助。

在上面的例子中,我试图通过构造函数来设置容量。从一定的容量值开始,该例子开始正常工作。

但我认为这是一个巧合。

 
fxsaber #:

我在CHashMap中发现了一个非常不寻常的行为。


看来,据说添加了一个钥匙,但无法从中读取任何东西。然而,只要再次添加钥匙,它就变得可读了!这就是为什么我们要把它称为 "可读"。

这是一个BAG吗?


如果你把例子中的价格1.75141 换成另一个价格,它就会正常工作。


没有调试的情况下,要在庞大的代码中发现这种行为,并创造这样一个简明的例子,简直是地狱般的困难。

已修复,将在今天的版本中出现。
 
MetaQuotes #:
已纠正,将在今天的版本中出现。

谢谢你!我看到了编辑。


 
fxsaber #:

在上面的例子中,我试图通过构造函数来设置容量。从一定的容量值开始,该例子开始正常工作。

但我认为这是一个巧合。

是的,有一个又一个的小故障。我强烈建议不要使用Generic。