해시 프로세스가 사전 <TKey, TValue>에서 어떻게 작동합니까?

Question

사전에서 해싱 프로세스가 어떻게 작동합니까? 나는 사전을 사용하여 더 빨리 찾아 볼 것을 읽었다. 그러나 어떻게 이해하지 못했습니까? 해시 및 색인에 대한 매핑은 어떻게됩니까? 좋은 참조를 찾을 수 없습니다.

편집 : 해싱 기능의 결과에서 객체가 저장된 실제 메모리 위치는 어떻게됩니까?

Answer 1

사전의 해싱 프로세스는 연결이라고하는 기술을 사용합니다. 체인을 사용하면 충돌을 방지하기 위해 보조 데이터 구조가 사용됩니다. 특히 Dictionary의 각 슬롯에는 버킷에 매핑되는 요소 배열이 있습니다. 충돌이 발생하면 충돌 요소가 버킷 목록에 추가됩니다.

자세한 내용은 MSDN의 this 문서를 참조하십시오.

Answer 2

Hash Map이라는 컴퓨터 과학 개념을 사용합니다. 이것은 목록을 검색하는 것보다 빠르게 작동합니다. 이는 일치하는 항목을 찾을 때까지 검색을 목록을 통해 반복 할 필요가 없도록 유지함으로써 작동합니다. 대신 키는 "hashed"이며 목록의 색인으로 사용됩니다. 이 해시 함수는 목록을 검색하는 것보다 (항상 여러 번 비교하여 반복하는 것보다) 빠릅니다.

Answer 3

일반적으로 해시 값 % 배열 크기를 사용하면 충돌이 발생할 수 있습니다.

Answer 4

사전에서 해시 키를 사용하여 my answer to your other question에서 설명하려고 했으므로 검색에 사용합니다. 그래서 키가 모두 사용자 지정 개체 형식이있는 경우 GetHashKey() 사용자 지정 개체 구현에 따라 다릅니다.

Answer 5

해시 테이블 또는 사전은 키 - 값 쌍을 저장하는 데이터 구조입니다. 해시 테이블의 장점은 해당 값을 찾는 키가 매우 빠르다는 것입니다. 단순화 된 해시 테이블에서 키 - 값 쌍을 찾는 시간은 테이블의 크기에 의존하지 않습니다. 키 - 값 쌍을 목록이나 배열에 저장하는 것과 비교하십시오. 키 - 값 쌍을 찾으려면 처음부터 일치하는 키가 발견 될 때까지 목록을 검색해야합니다. 목록이 길수록 키 - 값 쌍을 찾는 데 더 많은 시간이 걸립니다. big-O 표기법을 사용하면 선형 검색을 사용하여 목록에서 키를 찾는 동안 O (N) (단순화) 명령을 사용하는 반면 해시 테이블에서 키를 찾는 것은 O (1)라고 말할 수 있습니다.

해시 테이블에 키 - 값 쌍을 삽입하려면 먼저 키의 해시 코드를 계산해야합니다. .NET에서 모든 객체는 해당 객체에 대한 해시 코드 (32 비트 정수)를 반환하는 GetHashCode이라는 메서드를 가지고 있습니다. 동일한 객체가 동일한 해시 코드를 반환하는 것이 중요하지만 다른 객체가 다른 해시 코드를 반환하는 경우에도 매우 유용합니다. 다른 객체가 동일한 해시 코드를 반환 할 수 없다는 오해에 유의하십시오. 그러나 가능한 경우 충돌이 발생합니다 (아래 참조). 예를 들어

두 문자열의 해시 코드를 고려 : 문자열이 서로 다른 해시 코드가 매우 유사하더라도

 
"Boo" 0x598FD95A 
"Foo" 0x598FD8DE 

.

해시 테이블의 중요한 측면에 초점을 맞추기 위해 여기에 약간의 작업을 단순화했습니다. 이제는 내부적으로 Dictionary<TKey, TValue>이 키 - 값 쌍을 배열에 저장합니다. 키 - 값 쌍이 저장 될 배열에서이 인덱스를 찾으려면 배열의 크기를 기준으로 키의 해시 코드를 계산해야합니다.배열의 크기가 5 가정 :

 
Index("Boo") = 0x598FD95A % 5 = 4 
Index("Foo") = 0x598FD8DE % 5 = 0 

이이 내부 해시 테이블 배열로 연결 :

 
+---+---------+ 
| 0 | "Foo" | 
+---+---------+ 
| 1 | (empty) | 
+---+---------+ 
| 2 | (empty) | 
+---+---------+ 
| 3 | (empty) | 
+---+---------+ 
| 4 | "Boo" | 
+---+---------+ 

해시 테이블에 항목을 찾는 것은 매우 빠릅니다. 내부 배열의 크기를 기준으로 키의 해시 코드를 계산하고 해당 인덱스에서 문자열을 검색하면됩니다.

지금 키 "동물원"을 고려하십시오

 
Index("Zoo") = 0x598FDC62 % 5 = 0 

이 키 "우우"와 같은 인덱스를 가지고있다. 이로 인해 충돌이 발생합니다 (). 해시 테이블의 적절한 구현은 충돌을 처리해야하고 different strategies for doing that이 있습니다. 또한 내부 배열이 채워지면 배열에 빈 요소가 줄어들어 충돌 수가 증가합니다. 부하 계수은 사용 된 요소와 내부 배열의 전체 요소 사이의 비율입니다. 위의 예에서 부하 계수는 2/5 = 0.4입니다. 대부분의 해시 테이블 구현은로드 요소가 특정 임계 값을 초과 할 때 내부 배열의 크기를 증가시킵니다.

이러한 개념 중 일부에 대해 더 자세히 알고 싶다면 다른 대답에 링크되어있는 좀 더 포괄적 인 자료를 공부해야합니다.