많은 답변이 있지만 그중 어느 것도 시각적이지 않으며 해시 테이블은 시각화 할 때 쉽게 “클릭”할 수 있습니다.

해시 테이블은 종종 연결된 목록의 배열로 구현됩니다. 사람들의 이름을 저장하는 테이블을 상상하면 몇 번의 삽입 후에 아래와 같이 메모리에 배치 될 수 있습니다. 여기서 ()-닫힌 숫자는 텍스트 / 이름의 해시 값입니다.

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

몇 가지 사항 :

• 배열 항목 (인덱스는 각각 [0], [1]…)를로 알려져 버킷 및 시작 – 비어 -의 연결리스트 값 (일명 요소 ,이 예에서 – 사람의 이름 )
• 각각의 값은 (예를 들어, "fred"해시가 42)에서 연결된 통 [hash % number_of_buckets]등 42 % 10 == [2]; %는 IS 나머지 연산자 버킷의 개수로 나눈 나머지는 –
• 복수의 데이터 값이있다 충돌 에서와 같은 통에서 연결되어, 주로 이들의 해시 값은 모듈로 연산 한 후 충돌 (예 있으므로 42 % 10 == [2], 및 9282 % 10 == [2]) 만, 해시 값이 동일 (예를 들어, 때때로 때문에 "fred"와 "jane"모두 해시 도시 42이상)
  • 대부분의 해시 테이블은 해시 대상 버킷의 링크 된 목록에서 이미 찾거나 삽입되는 값의 전체 값 (여기서는 텍스트)을 비교하여 성능이 약간 저하되었지만 기능적 혼란이없는 충돌을 처리합니다.

연결된 목록 길이는 값 수가 아닌로드 팩터와 관련이 있습니다.

테이블 크기가 커지면 위와 같이 구현 된 해시 테이블은 자체적으로 크기를 조정하는 경향이 있습니다 (즉, 더 큰 버킷 배열을 생성하고 그로부터 새로운 / 업데이트 된 링크 목록을 생성하고 기존 배열을 삭제) 버킷에 대한 값의 비율을 유지합니다 (일명 로드 계수 0.5 내지 1.0의 범위에서) 대체로.

Hans는 아래 주석에서 다른 부하 계수에 대한 실제 공식을 제공하지만, 표시 값에 대해서는 부하 계수 1 및 암호화 강도 해시 함수를 사용하여 버킷의 1 / e (~ 36.8 %)가 비어 있고 다른 1 / e (~ 36.8 %)는 1 / (2e) 또는 ~ 18.4 % 두 요소, 1 / (3! e) 약 6.1 % 세 요소, 1 / (4! e) 또는 ~ 1.5 % 네 요소, 1 / (5! e) ~ .3 %에는 5 개 등이 있습니다.-비어 있지 않은 버킷의 평균 체인 길이는 테이블에 몇 개의 요소가 있는지에 관계없이 ~ 1.58입니다 (즉, 100 개의 요소와 100 개의 버킷이 있는지 또는 1 억 개가 있는지) 조회 및 삽입 / 삭제가 O (1) 일정 시간 작업 이라고 말하는 이유 입니다.

해시 테이블이 키를 값과 연관시키는 방법

위에서 설명한 해시 테이블 구현을 고려할 때 필드 struct Value { string name; int age; };만 보며 name(연령 무시) 등호 비교 및 ​​해시 함수와 같은 값 유형을 작성하고 멋진 일이 발생 한다고 상상할 수 있습니다 . 테이블에서 Value와 같이 레코드 를 저장할 수 있습니다 {"sue", 63}그런 다음 나중에 나이를 모른 채 “고소”를 검색하고 저장된 값을 찾고 나이를 복구하거나 업데이트합니다.
생일 축하합니다-해시 값을 흥미롭게 변경하지 않으므로 Sue의 레코드를 다른 레코드로 옮길 필요가 없습니다. 버킷.

이 작업을 수행 할 때 해시 테이블을 연관 컨테이너 ( 일명 map )로 사용하며, 저장하는 값은 키 (이름)와 여전히 혼란스러워하는 하나 이상의 다른 필드 ( 값 ( 내 예에서는 나이 만). 맵으로 사용되는 해시 테이블 구현을 해시 맵이라고 합니다.

이것은 “sue”와 같은 불연속 값을 저장 한이 답변의 앞부분의 예와 대조됩니다.이 값은 자체 키로 생각할 수 있습니다. 이러한 종류의 사용법을 해시 세트라고 합니다.

해시 테이블을 구현하는 다른 방법이 있습니다

모든 해시 테이블이 별도의 체인으로 알려진 링크 된 목록을 사용 하는 것은 아니지만 주로 대체 주소 해싱 (일명 개방 주소 지정 ) , 특히 지우기 작업이 지원되는 경우 충돌이 발생하기 쉬운 키 / 해시 함수.

해시 함수에 대한 몇 마디

강력한 해싱 …

일반적으로 최악의 충돌을 최소화하는 해시 함수의 작업은 항상 동일한 키에 대해 동일한 해시 값을 생성하면서 해시 테이블 버킷 주위에 키를 무작위로 효과적으로 분사하는 것입니다. 키의 어느 곳에서든 1 비트 만 변경해도 결과 해시 값에서 비트의 절반 이상이 이상적으로 무작위로 플립됩니다.

이것은 일반적으로 수학에 너무 복잡하여 조정하기가 어렵습니다. 가장 확장 가능하거나 캐시 친화적이지 않지만 본질적으로 우아함 (일회용 패드를 사용한 암호화와 같은)을 이해하기 쉬운 방법에 대해 언급하겠습니다. 64 비트를 해싱한다고 가정 해보십시오. double각 256 개의 난수 (아래 코드) 각각에 8 개의 테이블을 만든 다음 각 double메모리 의 8 비트 / 1 바이트 슬라이스 를 사용하여 다른 테이블에 색인을 생성 할 수 있습니다. 당신이 찾는 임의의 숫자. 이 방법 double을 사용하면 테이블의 하나에서 다른 임의의 숫자가 조회되고 완전히 상관되지 않은 최종 값 이 결과의 임의의 위치에서 변경되는 이진 숫자 의미로 쉽게 볼 수 있습니다.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

약하지만 종종 빠른 해싱 …

많은 라이브러리의 해싱 함수는 변경되지 않은 ( 사소한 또는 신원 해시 함수 라고도 함) 정수를 전달합니다 . 위에서 설명한 강력한 해싱과는 다른 극단입니다. 신원 해시는 매우최악의 경우 충돌이 발생하기 쉽지만, 아마도 약간의 공백이있는 경향이있는 정수 키의 경우에는 임의의 해싱 잎보다 비어있는 채로 연속 버킷에 매핑됩니다 (우리의 ~ 36.8 앞서 언급 한로드 팩터 1에서의 %)에 의해, 랜덤 매핑에 의해 달성되는 것보다 충돌이 적고 충돌 요소의 링크 된리스트가 적어진다. 또한 강력한 해시를 생성하는 데 걸리는 시간을 절약하고 키를 순서대로 조회하면 메모리 근처의 버킷에서 발견되어 캐시 적중률이 향상됩니다. 키 가 잘 증가 하지 않으면 무작위로 배치되어 버킷에 배치를 완전히 무작위 화하기 위해 강력한 해시 기능이 필요하지 않을 것이라는 희망이 있습니다.

답변

uint slotIndex = hashValue % hashTableSize;

slotIndex = (remainder + 1) % hashTableSize;

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null