해시 테이블 (맵)은 메모리에 어떻게 저장됩니까?

Question

이 질문은 해시 테이블을 대상으로하지만 링크 된 목록이나 트리와 같은 다른 데이터 구조도 포함 할 수 있습니다. 만약 구조체가 있다면

예를 들어, 다음과 같이

struct Data 
{ 
    int value1; 
    int value2; 
    int value3; 
} 

을 각각 정수 4 바이트 정렬 메모리에 순차적으로 저장되고, 순차적으로뿐만 아니라 저장된 해시 테이블의 키 값은 무엇입니까? 다음을 고려한 경우 :

std::map<int, string> list; 
list[0] = "first"; 

첫 번째 요소는 다음과 같이 표시됩니까?

struct ListNode 
{ 
    int key; 
    string value; 
} 

와 키 값과

경우는 4 바이트 정렬되고 순차적으로 저장되고, 그 다음 문제 쌍 저장 않는 경우?

링크 된 목록의 노드는 어떻습니까?

이 개념을 시각화하고 메모리 저장에 대한 동일한 지침이 열린 주소 해시 (로드가 1 미만) 또는 체인 해시 (로드가 중요하지 않음)에도 적용되는지 확인하십시오.

Answer 1

구현에 따라 다릅니다. 그리고 컴파일러, CPU 아키텍처 및 ABI뿐 아니라 해시 테이블 구현에 대해서도 언급하고 있습니다. 일부 해시 테이블은 추측 한 것처럼 키와 값을 서로 포함하는 구조체를 사용합니다. 다른 것들은 하나의 키 배열과 하나의 값 배열을 가지므로 values[i]은 keys[i]에있는 키와 연관된 값입니다. 이는 "열린 주소 지정 대 별도의 연결"질문과는 독립적입니다.

Answer 2

해시는 데이터 구조 자체입니다. 여기에 귀하의 비쥬얼입니다 :

http://en.wikipedia.org/wiki/Hash_table

http://en.wikipedia.org/wiki/Hash_function

해시 함수를 사용하여 (langauge 별), 키는 장소로 전환되고, 값이 배치됩니다

(배열).

연결된 목록 나는 확실하지는 않지만 순차적으로 만들어지면 순차적으로 저장됩니다. 물론 노드가 크기를 늘리면 포인터를 움직여 포인터를 그 지점으로 다시 정의해야합니다.

Answer 3

값이 큰 (int)를하지 보통은 함께 키 (기본적으로 너무 큰해서는 안 함)로 그룹에 최선의 방법은, 그렇지 않으면 만에 포인터가 유지됩니다.