Hash 알고리즘

---

1. Hash 알고리즘

예를 들어 43, 36, 44, 21, 25, 30, 22, 17 이라는 데이터를 가지고 있고, h(k) = k % 10 이라는 함수가 있습니다. 위 데이터를 h(k) 함수에 대입하여 얻은 값을 테이블에 인덱스로 사용하고, 해당 튜플에는 위 데이터를 저장해두는 방식 입니다. 여기서 h(k)는 hash 함수 라고 하고, 테이블은 hash 테이블 이라고 합니다. 예를 들어 43 데이터를 h(k) = k % 10 이라는 hash 함수에 대입 하면 43 % 10 = 3이 됩니다. 따라서 hash 테이블의 인덱스 3의 43을 저장 합니다. hash 함수는 데이터의 특성에 따라 달라 질수 있고, 개발자가 정의 내릴수 있습니다. 충돌이 적은 함수가 좋은 hash 함수 입니다. 동일한 데이터라면 hash 함수에 대입시 동일한 hash 코드가 나옵니다. Hash 알고리즘은 충돌이 없다면 O(1)의 시간 복잡도를 가집니다.

​

정리를 하면

1. Hash 알고리즘은 데이터들을 어떤 함수에 의해서 상징적인 값으로 대체 하는 기법을 의미 합니다.

2. 데이터를 hash 함수에 대입하여 얻은 값을 hash 코드 라고 합니다.

3. hash 코드는 hash 테이블에 인덱스가 됩니다.

4. 동일한 데이터라면, hash 함수에 대입시 동일한 hash 코드가 나와야 합니다.

5. hash 함수는 개발자가 직접 정의 할수 있으면, 데이터에 특성에 따라 달라 집니다.

6. 충돌이 적은 함수가 좋은 hash 함수 입니다.

7. 충돌이 없다면, hash 함수만 연산하면 되기 때문에 O(1) 시간복잡도가 가능 합니다.

​

​

2. 충돌(Collision)

위에서 충돌이 적은 함수가 좋은 hash 함수라고 하였습니다. 따라서 충돌은 hash 알고리즘에서 아주 중요 합니다. 충돌은 서로 다른 데이터가 hash 함수에 대입하여 얻은 값이 같은 hash 코드가 나오면 이를 '충돌' 이라고 합니다. 충돌을 해결하는 방법은 2가지가 있습니다. Chaining, Open addressing 방법이 있습니다.

​

​

3. 충돌 해결 방법: Chaining

11과 41을 h(k) = k % 10 함수에 대입하면 나머지가 1이 되어 같은 hash 코드를 가집니다. 따라서 11과 41을 hash 테이블의 인덱스 1의 저장 해야 하므로 인덱스 1은 연결 리스트로 구현 합니다. 그리고 먼저 입력된 11을 저장 하고, 나중에 입력된 41을 그 다음 리스트에 저장 합니다. 이것이 Chaining을 이용한 충돌 해결 방법 입니다.

​

​

3. 충돌 해결 방법: Open Addressing

11과 41을 h(k) = k % 10 함수에 대입하면 나머지가 1이 됩니다. 충돌이 일어 납니다. 나중에 입력된 41은 그 다음 인덱스 2로 향합니다. 하지만 인덱스 2도 32가 이미 저장 되어 있습니다. 따라서 그 다음 비어 있는 인덱스 3의 41을 저장 합니다. 이것이 open addressing을 이용한 충돌 해결 방법 입니다.