HashTable

1. 정보를 담아 저장하는 서랍장에 비유할 수 있다.
   1. 예를 들어, 정보 A는 3번째 서랍에 저장하기로 정하고, B는 0번째에, C는 다시 3번째에, D는 4번째에 저장하는 식이다.
   2. 그러면 정보 C를 찾고 싶다면, C가 저장된 서랍 번호를 알아내, 저장된 3번째 서랍에 들어 있는 정보를 하나씩 비교해 C를 찾아내면 된다.
   3. 가장 핵심적인 과정은 각 정보를 몇 번째 서랍에 넣을지를 결정하는 것이다.
2. 정보 K(key 값)가 저장될 서랍장(slot) 번호를 계산하는 함수 f( )를 해시 함수(hash fuction)이라 한다.
   1. 예를 들어, 해시 테이블 H를 일차원 배열 int H[10]으로 선언해 사용한다고 하자.
   2. 해시 함수는 f(k) = k % 10로 정으된다고 하자.
   3. k = 28 : H[f(28)] 슬롯에 저장된다. 즉, H[8]에 저장된다.
   4. k = 61 :  H[f(61)] = H[1]
   5. k = 18 :  H[f(18)] = H[8]
      • 그런데, 이미 H[8]에는 28이 저장되어 있다.
      • 이 경우를 충돌(collision)이 발생했다고 한다.
   6. 충돌이 발생한 경우에, 18을 저장할 공간이 더 있으면 저장하면 되지만, 지금 예처럼 H[8]에 값 하나만 저장할 수 있는 경우엔 18을 다른 곳에 저장해야 한다. 다른 곳을 정하는 방법을 충돌해결방법(collision resolution methon)이라 부른다.