[ Open Data Structures ] - Hash Table ( Chaining )

* hash 함수는 다음에 배워 구현합니다. 이 챕터로써는 해시 함수를 포함한 코드를 실행시킬 수 없습니다.

(Random numbers plucked from the atmosphere (irishtimes.com)) -> Atmospheric noise

List로 구성된 배열을 Hash Table로 사용합니다

Add Operation

figure 1b

figure 1a

Hash table은 List를 요소로 갖는 배열 t로 구현을 합니다. 격납되어 있는 모든 요소의 수를 n으로 추적합니다. 

 

Remove Operation

Multiplicative Hashing

 

figure 1c. 반드시 기억해야 하는 것은 w=32, d=8일 때 결과 값이라는 사실입니다.

* C/C++기준입니다. 다른 프로그래밍 언어에서는 Undefined Behaviour일 수 있습니다. 또한, 여기서 등장하는 HashCode(x)와 Hash(x)상당히 혼란스럽습니다. Hash(x)는 x에게 부여된 어떤 수를 갖고 배열 t의 index를 불러 온다고 생각하면 편합니다. 

HashCode(x)는 x에 부여된 임의의 정수를 가리킵니다. 왜냐하면 요소 x는 정수일 수도 있으나 정수가 아닌 임의의 어떤 데이터일 가능성도 있기 때문입니다. 그래서 이 요소에 대해서 임의의 정수를 붙여준 것인데 이 임의의 수를 가리켜 HashCode라고 했습니다. 그리고 그 임의의 정수를 불러오는 것을 HashCode(x)가 수행합니다. 그래서 HashCode(x)를 통해 불러온 값에 적당한 연산을 해서 얻는 그 값이 배열 t index가 되는 것입니다.

HashCode(x)는 따로 섹터를 할애하여 공부하기 때문에 적당한 수를 반환하는 것으로 만족해야 합니다.

figure 1d. HashCode에 대한 이해는 다른 챕터에서 다룹니다. 현재는 적당한 수를 반환하는 것으로 만족해야 합니다

솔직히 Lemma1의 증명은 하나도 알아들을 수가 없습니다. 정말 간신히 번역만 한 정도입니다. 아직도 Hash(x)에서 모듈로 연산이 왜 코드에 반영이 안 된 것인지 설명할 수 없습니다. HashCode에 대한 부분을 살짝 엿보고 왔으나 답을 얻을 수 없었습니다.