Hash 자료구조 이해하기

Hash(해시)

Hash란?

Hash가 무엇일까? 사전에서 Hash의 뜻을 보면 다음과 같다.

Hash
1. 해시(고기와 감자를 잘게 다져 섞어 요리한것) -> 아마 해시브라운 같은것일까??
2. 전화기에서의 우물정자(#) -> 해시테그 여기에서 나온것!!

그냥 일반적인 뜻으로는 전혀 컴퓨터와 관련이 없을것 같다. 하지만 숙어를 살펴보면 대략 감을 잡을 수 있다.

- make a hash of something
  : ~를 엉망으로 하다

뭔가를 엉망으로 만든다! 그렇다 해시함수는 들어온 입력에 대해서 출력을 엉망으로 만들어버린다.
해시는 암호화 기법중 한가지이다. 그래서 원래 정보를 잘 숨겨야 하는데 이를 엉망으로 만들어 알아 볼 수 없게 만든다면 보다 암호화 하는데 용이할 것이다.

간결하게 해시를 표현한다면 다음과 같다.

• 단방향 암호화 기법이다!
• 해시함수(해시 알고리즘)를 이용하여 고정된 길이의 문자열로 반환한다.
• 특정입력에 대해서 항상 같은 값을 return 한다.

사진을 보면 조금더 이해가 쉬울 것 같다.
이처럼 해시함수는 'Apple'을 알아볼 수 없도록 바꾼다. 이러한 과정을 'Hashing'이라고 한다.
Hash Value 만으로는 원래 값을 알 수 없기 때문에 암호화 하는데 사용되곤 한다.

해시 알고리즘의 종류는 다양하다. 알고리즘 마다 Return 겂이 다르며 현재 오픈된 알고리즘도 있다.

해시 충돌

해시 값은 항상 고정된 길이의 값을 리턴하기 때문에 중복된 해시 값이 발생할 수 있다. 이를 '해시 충돌' 이라고 한다.

우리는 해시 충돌 문제를 해결하기 위해 충돌 처리를 진행 할 수 있다.
충돌 처리의 종류에 여러가지가 있지만 몇개만 살펴보도록 하자!

• 분리된 체인
  연결 리스트를 이용하는 방법이다. 체인이 길어지면 속도가 떨어지고 추가적인 메모리가 필요하다는 단점이 있다.

• 오픈(개방) 해시
  해시 테이블에는 보통 빈공간이 많이 존재한다. 오픈해싱은 이 빈 공간을 사용하는 해시이다.
  추가적인 메모리가 필요없다는 장점이 있지만 주소를 다른 데이터들에게 공개하고 있다.
  오픈 해시의 종류로는 선형해시, 제곱조사, 이중해시 등이 있다.

• 선형해시
  충돌이 발생했다면 다음 테이블에 저장하는 방식이다. 단순한 방법이지만 충돌의 군집화가 생길 수 있다.
  총돌이 군집되어 있기 때문에 삭제하기가 다소 복잡하다.

• 제곱조사
  선형해시와 비슷하지만 폭을 제곱해서 늘리면서 저장한다. 충돌의 군집화 문제를 해결한 방법이다.

• 이중해싱
  해싱함수를 2개 만들어서 충돌시 2번째 함수를 이용하는 방식이다.
  제곱조사보다 발전한 방법이다.

정리하면서

해시를 제대로 공부하기 전에는 단순히 Key와 Value값을 가지고 있는 자료구조로만 생각했다. 딕셔너리가 해시인줄 알았다.
반은 맞고 반은 틀린 생각이었지만 암호화에 사용되는지는 생각하지 못했다. 덕분에 보안 문제에 대한 관심도 생겼다.
좋은 SW 개발자로 성장하기 위해 더 열심히 공부해겠다.

내용 출처
https://comdoc.tistory.com/entry/17-해싱hashing-파이썬
https://medium.com/@yeon22/crypto-해시-hash-란-6962be197523