Hash 해시, 해시 메커니즘, 중복 Key는?, 충돌

해시

해시는 Key-Value 쌍으로 저장되는 자료구조를 말한다. 자바에서는 hashMap이 Collections에 구현되어 있다.

 

 

이때 주의해야 할 점이 있는데, key는 반드시 중복되지 말아야 한다는 것이다.

 

해시 메커니즘

기본적인 해시는 위 그림과 같이 Hash function을 통해 만ㄷ르어 진다. Key-Value가 function을 거쳐 어떤 주소를 참조하게 된다.

기본적으로 인덱스 주소를 가지고, 그 주소에 value값이 링크되어 있다.

 

중복 key는?

해시 Key가 중복되면 어떤값이 나올까?

정답은 나중에 지정된 해시값이 나온다. 즉, 덮어쓰게 된다. 이를 충돌이라고 말한다. 기본적으로 인덱스는 value를 링크드 리스트로 포인트하고 있다. 같은 key를 가진 value가 들어오게 되면 value에 링크되면서 덮어씌어지게 된다.

충돌의 경우 해시의 시간복잡도는 비약적으로 늘어난다.

• 충돌이 일어나지 않은 경우

  • 탐색 : O(1)
  • 삽입 : O(1)
  • 삭제 : O(1)

• 충돌이 나는 경우

  • 탐색 : O(N) 인덱스 탐색 후 링크드리스트 순차 탐색
  • 삽입 : O(N) 탐색과 같은 이유
  • 삭제 : O(N) 탐색과 같은 이유

 

해시 테이블 정리

1. 기본적으로 O(1) 시간복잡도를 가진다.
2. Key가 중복되면 안된다.
3. Key를 알고 있으면 엄청나게 빠른 탐색 시간을 보장한다.
4. 중복을 막을 수 있다.