이전 예에서 해시 함수가 로드의 대부분을 차지한다는 것이 분명해졌습니다. 해시 함수는 최대한 빠르게 만들 수 있지만 이 경우 충돌 가능성이 매우 높습니다. 반대로 해시 함수는 충돌에 대해 가능한 한 저항력을 갖도록 만들 수 있지만 계산 복잡성은 수행 중인 작업에 부적절합니다. 두 가지 극단적인 예를 살펴보겠습니다. 예 1, 가장 빠른 해시 함수:
int GetHashCode( string word)
{
return0 ;
}
항상 같은 숫자를 반환합니다. 우리 사전이 단 하나의 단어만 저장한다면 그 작업으로 충분할 것입니다. 왜냐하면 이 단어는 인덱스 0에 있습니다. 그러나 10개의 단어가 있는 경우 10개 단어 모두 인덱스 0에 있습니다(배열 배열이 있다는 것을 잊지 마십시오).
두 번째 예로, 예를 들어 N 라운드 의 Feistel 네트워크를 기반으로 하는 가역 암호화로 전환합니다. 이것은 해시 함수가 아니며 충돌의 대상이 전혀 아닙니다. 저것들. 두 개의 다른 문자열에 대해 다른 숫자를 보장합니다. 결과 숫자의 길이는 문자열의 길이와 같습니다. 따라서 길이가 1000자인 문자열의 경우 차원이 1000인 uchar 배열을 얻습니다. 이 문자열을 요소 크기가 3개인 사전에 저장해야 하는 경우 이상하다는 데 동의할 것입니다. 이렇게 복잡한 코드를 계산하여 요소가 세 개뿐인 단어를 검색합니다.
따라서 우리는 항상 중간 지점을 찾아야 합니다(fxsaber가 올바르게 지적했듯이). 해시를 빠르게 계산하고 일반적 으로 충돌을 일으키지 않는 함수가 필요합니다. 이전 해시 함수의 충돌 확률을 추정해 보겠습니다.
int GetHashCode( string word)
{
int index = StringGetCharacter (word, 0 )- 'a' ;
}
알파벳은 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이 됩니다. 해시 함수를 계산하는 두 번째 변형의 복잡성은 선형으로 약 2배 증가한 반면 충돌에 대한 저항은 제곱으로 비선형적으로 증가했습니다.
두 번째 옵션의 경우 평균적으로 676단어마다 한 번의 충돌이 발생합니다. 우리의 경우 988 단어의 경우 인덱스당 988/676 = 1.4615 충돌이 발생합니다. 저것들. 각 색인은 평균적으로 한 단어 또는 두 단어를 포함합니다. 저것들. 평균적으로 검색이 전혀 없거나(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의 비율을 얻게 됩니다. 저것들. 배열 인덱스당 하나의 단어만 있을 것입니다. 따라서 사전은 인덱스 대신 키가 지정되는 배열의 특수한 경우라고 말할 수 있습니다.
문제는 사전의 크기를 알 수 없는 경우가 많다는 것입니다. 간단한 예를 들어 Expert Advisor가 있다고 가정해 보겠습니다. 완료된 거래를 추적합니다. 거래가 역사에 나타난 후에는 이 거래를 전문가의 마법과 연관시켜야 합니다. 이를 위해 사전을 사용하는 것이 논리적입니다. 거래번호를 키로 사용하고(고유식별자) 전문가의 매직넘버를 값으로 사용하는 경우. 문제는 어드바이저를 시작할 때 100개의 트랜잭션이 있는지, 1000개 또는 전혀 없는지 여부를 미리 결정하는 것이 불가능하다는 것입니다. 미리 할당한 메모리의 양에 관계없이 여전히 너무 적거나 너무 많습니다.
문제는 사전의 크기를 알 수 없는 경우가 많다는 것입니다. 간단한 예를 들어 Expert Advisor가 있다고 가정해 보겠습니다. 완료된 거래를 추적합니다. 거래가 역사에 나타난 후에는 이 거래를 전문가의 마법과 연관시켜야 합니다. 이를 위해 사전을 사용하는 것이 논리적입니다. 거래번호를 키로 사용하고(고유식별자) 전문가의 매직넘버를 값으로 사용하는 경우. 문제는 어드바이저를 시작할 때 100개의 트랜잭션이 있는지, 1000개 또는 전혀 없는지 여부를 미리 결정하는 것이 불가능하다는 것입니다. 미리 할당한 메모리의 양에 관계없이 여전히 너무 적거나 너무 많습니다.
글쎄, 임무가 다른 것은 분명합니다.
하나의 인간 언어에 대한 편리한 사전을 만들어야 하는 문제를 해결했습니다. 내 배열의 크기는 정확하지 않지만 특정 언어의 단어 수에 맞추는 데 문제가 있습니까? 그는 거기에 쉽게 적응합니다.
예를 들어 러시아어. 10,000개의 기본 단어가 포함되어 있다고 가정해 보겠습니다. 이 모든 단어는 내 배열에 완벽하게 배치될 수 있습니다.
첫 번째 차원은 66자(작고 큰), 두 번째 차원은 단어의 문자 수(예: 최대 25개), 세 번째 차원은 첫 번째 문자와 문자 수 - 50에 대한 일치입니다.
전체 언어가 맞을 것입니다.
//------------------------
처음에는 이 문제를 정확히 해결했습니다. 당신은 이제 원래의 문제를 다른 문제로 바꾸고 해결책이 좋지 않다고 말합니다.
원칙적으로 해시 테이블과 해시의 올바른 버전은 있을 수 없습니다. 모두 특정 목표와 사용 조건에 따라 다릅니다. 마치 샌드위치를 만드는 것과 같습니다. 누군가 마요네즈나 케첩을 먹지 않거나 채식주의자일 수도 있습니다. 그러나 테이블에 케첩을 뿌리고 그 위에 빵을 깔고-이것이 아닌 것이 분명한 것 같습니다 ....
Mikhail Kurnosov, Associate Professor (Docent) Follow
www.slideshare.net
Лекция 6 Хеш-таблицы Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатик…
간단히 말해서 해시 함수가 먼저 작동해야 합니다. 빠르고, 두 번째입니다. 완전히 복잡한 것을 발명할 필요가 없습니다. 동일한 값의 모양은 일반적으로 직접 열거에 의해 사전 내부에서 확인됩니다. 가장 중요한 것은 너무 빈번한 충돌이 없다는 것입니다. 그게 전부입니다. 일반에서 HashFunction.mqh 파일의 함수 집합은 기본 유형의 함수 해시를 담당합니다. 모든 것이 간단한지 확인하기 위해 작동 방식을 살펴보겠습니다.
//+------------------------------------------------------------------+//| 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 ));
}
}
//+------------------------------------------------------------------+
정수 유형은 있는 그대로 반환되거나 짧은 정수 유형에 대해 간단한 비트 단위 변환 작업이 사용됩니다. 32비트에 맞지 않는 형식의 경우 배타적이거나 오른쪽 및 왼쪽 부분의 합집합이 뒤에 사용됩니다. 문자열의 경우 복잡하지 않은 해시도 직접 열거를 통해 계산됩니다. 실수의 경우 Union의 도움으로 비트 표현이 취해지며 이미 해시로 사용됩니다.
키가 고유하고 값이 고유하지 않은 키-값 쌍의 집합입니다. 일반에서는 CHashMap입니다.
고유한 값의 집합입니다. 일반적으로 이것은 CHashSet입니다.
CHashSet이란 무엇입니까? 이것은 각 요소가 고유한 컬렉션(본질적으로 배열)입니다. 예를 들어, 이러한 컬렉션에는 2,5,1,7,10,15,1024라는 숫자가 포함될 수 있습니다. 그러나 두 숫자가 같지 않습니다. 또한 문자열, 실수, 사용자 정의 복합 유형 (나중에 자세히 설명)을 포함할 수도 있습니다. 그러나 모든 유형에 대해 규칙은 동일합니다. 사전에는 이와 같은 것이 있을 수 없습니다.
CHashMap이란 무엇입니까? 이것은 각 요소가 복잡한 키-값 유형인 컬렉션(본질적으로 배열이기도 함)입니다.
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;
};
이것은 CHashMap과 매우 유사한 구조를 가지고 있지만 두 세트를 매핑하여 세트 요소 1이 세트 2에 해당하도록 할 수 있습니다. 이것은 평균 O(1) 실행 시간으로 매우 효율적인 쿼리 알고리즘을 작성할 수 있게 해주는 매우 편리한 기능입니다.
나중에 예제를 사용하여 일종의 통신 구성을 분석할 것입니다.
흥미롭게도 모든 키-값 사전은 이러한 사소한 일대다 관계를 자연스럽게 설정합니다. 예를 들어, 역사적 주문과 이를 기반으로 실행된 거래가 있습니다. 각 트랜잭션은 하나의 주문에만 해당하지만 하나의 주문은 여러 트랜잭션에 해당할 수 있습니다. 이러한 관계의 사전은 거래 번호를 키로 저장할 수 있고 값으로 거래를 여는 데 사용된 주문 번호를 저장할 수 있습니다.
해시 함수 정보
이전 예에서 해시 함수가 로드의 대부분을 차지한다는 것이 분명해졌습니다. 해시 함수는 최대한 빠르게 만들 수 있지만 이 경우 충돌 가능성이 매우 높습니다. 반대로 해시 함수는 충돌에 대해 가능한 한 저항력을 갖도록 만들 수 있지만 계산 복잡성은 수행 중인 작업에 부적절합니다. 두 가지 극단적인 예를 살펴보겠습니다. 예 1, 가장 빠른 해시 함수:
항상 같은 숫자를 반환합니다. 우리 사전이 단 하나의 단어만 저장한다면 그 작업으로 충분할 것입니다. 왜냐하면 이 단어는 인덱스 0에 있습니다. 그러나 10개의 단어가 있는 경우 10개 단어 모두 인덱스 0에 있습니다(배열 배열이 있다는 것을 잊지 마십시오).
두 번째 예로, 예를 들어 N 라운드 의 Feistel 네트워크를 기반으로 하는 가역 암호화로 전환합니다. 이것은 해시 함수가 아니며 충돌의 대상이 전혀 아닙니다. 저것들. 두 개의 다른 문자열에 대해 다른 숫자를 보장합니다. 결과 숫자의 길이는 문자열의 길이와 같습니다. 따라서 길이가 1000자인 문자열의 경우 차원이 1000인 uchar 배열을 얻습니다. 이 문자열을 요소 크기가 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이 됩니다. 해시 함수를 계산하는 두 번째 변형의 복잡성은 선형으로 약 2배 증가한 반면 충돌에 대한 저항은 제곱으로 비선형적으로 증가했습니다.
두 번째 옵션의 경우 평균적으로 676단어마다 한 번의 충돌이 발생합니다. 우리의 경우 988 단어의 경우 인덱스당 988/676 = 1.4615 충돌이 발생합니다. 저것들. 각 색인은 평균적으로 한 단어 또는 두 단어를 포함합니다. 저것들. 평균적으로 검색이 전혀 없거나(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의 비율을 얻게 됩니다. 저것들. 배열 인덱스당 하나의 단어만 있을 것입니다. 따라서 사전은 인덱스 대신 키가 지정되는 배열의 특수한 경우라고 말할 수 있습니다.
배열의 크기는 사전의 크기에 맞게 쉽게 변경할 수 있습니다.
끝없는 옵션은 고려되지 않습니다.
문제는 사전의 크기를 알 수 없는 경우가 많다는 것입니다. 간단한 예를 들어 Expert Advisor가 있다고 가정해 보겠습니다. 완료된 거래를 추적합니다. 거래가 역사에 나타난 후에는 이 거래를 전문가의 마법과 연관시켜야 합니다. 이를 위해 사전을 사용하는 것이 논리적입니다. 거래번호를 키로 사용하고(고유식별자) 전문가의 매직넘버를 값으로 사용하는 경우. 문제는 어드바이저를 시작할 때 100개의 트랜잭션이 있는지, 1000개 또는 전혀 없는지 여부를 미리 결정하는 것이 불가능하다는 것입니다. 미리 할당한 메모리의 양에 관계없이 여전히 너무 적거나 너무 많습니다.
문제는 사전의 크기를 알 수 없는 경우가 많다는 것입니다. 간단한 예를 들어 Expert Advisor가 있다고 가정해 보겠습니다. 완료된 거래를 추적합니다. 거래가 역사에 나타난 후에는 이 거래를 전문가의 마법과 연관시켜야 합니다. 이를 위해 사전을 사용하는 것이 논리적입니다. 거래번호를 키로 사용하고(고유식별자) 전문가의 매직넘버를 값으로 사용하는 경우. 문제는 어드바이저를 시작할 때 100개의 트랜잭션이 있는지, 1000개 또는 전혀 없는지 여부를 미리 결정하는 것이 불가능하다는 것입니다. 미리 할당한 메모리의 양에 관계없이 여전히 너무 적거나 너무 많습니다.
글쎄, 임무가 다른 것은 분명합니다.
하나의 인간 언어에 대한 편리한 사전을 만들어야 하는 문제를 해결했습니다. 내 배열의 크기는 정확하지 않지만 특정 언어의 단어 수에 맞추는 데 문제가 있습니까? 그는 거기에 쉽게 적응합니다.
예를 들어 러시아어. 10,000개의 기본 단어가 포함되어 있다고 가정해 보겠습니다. 이 모든 단어는 내 배열에 완벽하게 배치될 수 있습니다.
첫 번째 차원은 66자(작고 큰), 두 번째 차원은 단어의 문자 수(예: 최대 25개), 세 번째 차원은 첫 번째 문자와 문자 수 - 50에 대한 일치입니다.
전체 언어가 맞을 것입니다.
//------------------------
처음에는 이 문제를 정확히 해결했습니다. 당신은 이제 원래의 문제를 다른 문제로 바꾸고 해결책이 좋지 않다고 말합니다.
미리 할당한 메모리의 양에 관계없이 여전히 너무 적거나 너무 많습니다.
권리.
모든 문제에 대한 보편적인 해결책이 없는 것도 사실입니다.
권리.
모든 문제에 대한 보편적인 해결책이 없는 것도 사실입니다.
절대적으로 부인할 수 없습니다.
조용한 동지. 아무도 실수로부터 면역이 없습니다. 당신도 마찬가지입니다. 그러므로 친절하고 부드러운 어조로 다른 사람의 잘못을 지적하십시오. 지금 수정하겠습니다.
그리고 올바른 옵션은 비밀로 남을 것입니다 ???
원칙적으로 해시 테이블과 해시의 올바른 버전은 있을 수 없습니다. 모두 특정 목표와 사용 조건에 따라 다릅니다.
마치 샌드위치를 만드는 것과 같습니다. 누군가 마요네즈나 케첩을 먹지 않거나 채식주의자일 수도 있습니다.
그러나 테이블에 케첩을 뿌리고 그 위에 빵을 깔고-이것이 아닌 것이 분명한 것 같습니다 ....
게으른 사람을 위한 주제에 대한 기본 사항:
https://www.slideshare.net/mkurnosov/6-32402313
실제로는 모든 것이 훨씬 더 복잡하며 관련 문헌이나 좋은 "알고리즘 및 데이터 구조" 과정에서 논의됩니다.
간단히 말해서 해시 함수가 먼저 작동해야 합니다. 빠르고, 두 번째입니다. 완전히 복잡한 것을 발명할 필요가 없습니다. 동일한 값의 모양은 일반적으로 직접 열거에 의해 사전 내부에서 확인됩니다. 가장 중요한 것은 너무 빈번한 충돌이 없다는 것입니다. 그게 전부입니다. 일반에서 HashFunction.mqh 파일의 함수 집합은 기본 유형의 함수 해시를 담당합니다. 모든 것이 간단한지 확인하기 위해 작동 방식을 살펴보겠습니다.
정수 유형은 있는 그대로 반환되거나 짧은 정수 유형에 대해 간단한 비트 단위 변환 작업이 사용됩니다. 32비트에 맞지 않는 형식의 경우 배타적이거나 오른쪽 및 왼쪽 부분의 합집합이 뒤에 사용됩니다. 문자열의 경우 복잡하지 않은 해시도 직접 열거를 통해 계산됩니다. 실수의 경우 Union의 도움으로 비트 표현이 취해지며 이미 해시로 사용됩니다.
사전 유형 알고리즘은 조건부로 두 부분으로 나뉩니다.
CHashSet이란 무엇입니까? 이것은 각 요소가 고유한 컬렉션(본질적으로 배열)입니다. 예를 들어, 이러한 컬렉션에는 2,5,1,7,10,15,1024라는 숫자가 포함될 수 있습니다. 그러나 두 숫자가 같지 않습니다. 또한 문자열, 실수, 사용자 정의 복합 유형 (나중에 자세히 설명)을 포함할 수도 있습니다. 그러나 모든 유형에 대해 규칙은 동일합니다. 사전에는 이와 같은 것이 있을 수 없습니다.
CHashMap이란 무엇입니까? 이것은 각 요소가 복잡한 키-값 유형인 컬렉션(본질적으로 배열이기도 함)입니다.
이것은 CHashMap과 매우 유사한 구조를 가지고 있지만 두 세트를 매핑하여 세트 요소 1이 세트 2에 해당하도록 할 수 있습니다. 이것은 평균 O(1) 실행 시간으로 매우 효율적인 쿼리 알고리즘을 작성할 수 있게 해주는 매우 편리한 기능입니다.
나중에 예제를 사용하여 일종의 통신 구성을 분석할 것입니다.
흥미롭게도 모든 키-값 사전은 이러한 사소한 일대다 관계를 자연스럽게 설정합니다. 예를 들어, 역사적 주문과 이를 기반으로 실행된 거래가 있습니다. 각 트랜잭션은 하나의 주문에만 해당하지만 하나의 주문은 여러 트랜잭션에 해당할 수 있습니다. 이러한 관계의 사전은 거래 번호를 키로 저장할 수 있고 값으로 거래를 여는 데 사용된 주문 번호를 저장할 수 있습니다.