[알고리즘지식] 해시, 해시충돌 그리고 해결법

프로그래머스에서 이번엔 해시를 해볼까? 하다가 알고리즘을 배운지 1년 여 되어가던 찰나라 다시한번 해시를 다시 간단하게 공부해보았습니다!! 알고리즘을 깊게 공부하는 것은 좋지만 정리/요약은 간단히 하는게 더 좋다고 생각해서 간단하게 했습니다 :)

1. Hash

1.1. Hash란?

Hash : 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환(매핑)하는 것

 

Hash Function : hash 기능을 수행하는 함수

     - 하나의 값은 동일한 결과를 가져온다.

     // 만약, 인풋으로 10가지의 경우가 들어갈 수 있는데 아웃풋으로 다섯개의 경우만 나올 수 있다면?

        -> 해시충돌!!이 발생할 수 있다.

 

1.2. Hash 충돌

해시 충돌 : 서로 다른 값을 인풋시켰음에도 같은 결과를 내는 경우

 

Hash 충돌의 해결

- Open Addressing : 해시 충돌 시, 새로운 값을 해당 인덱스에 넣고,  원래 있던 인덱스 값을 다른 인덱스로 밀어넣음. 

     >> 장점

          - 연속된 공간에 데이터를 저장함으로 캐시 효율이 좋다.

     >> 단점

          - 해시 충돌 시 인덱스 값이 바뀌기 때문에 충돌이 많아질 수록/데이터의 양이 많아질수록 성능이 급격히 저하

 

- Separate Chaining : 해시 충돌 시, 새로운값을 해당 인덱스의 연결리스트로 넣는다.

     >> 장점

          -  해시 충돌이 일어나도 연결리스트로 노드가 연결되어 인덱스에는 변함이 없다.

          -  데이터 개수의 제약이 거의 없다.

     >> 단점

          - 한 인덱스로 결과값이 쌓이게 되면 선형적으로 성능이 저하된다.