- 글에 적은 내용 중 잘못된 부분은 댓글로 적어주시면 감사하겠습니다!
인스타그램이나 페이스북과 같은 SNS를 사용할 때, 해시태그를 이용해 본 적이 있을 것이다. 이번엔 그 해시태그와 관련된 해싱!
은 실은 헛소리고, 해시태그와 해싱은 아무런 관련이 없다. 😗
해시태그란 말을 많이 들어서 해싱과 연관이 있는 줄 알았는데, 해시태그는 해시(#)라는 기호와 관련된 용어이고 해싱은 조각내다, 잘게 썰다 등의 해시(hash)의 원어적 의미와 관련된 것이다.
해싱 (Hashing)
해싱은 해시 함수에 문자열 입력값을 넣어서 특정한 값으로 추출하는 것을 의미한다.
A -> 해시 함수 -> Alpha
B -> 해시 함수 -> Bravo
C -> 해시 함수 -> Cycle
위 예시에서 A라는 값은 해시 함수를 통해서 Alpha라는 값이 나오고, B와 C 각각에 대한 결과값이 따로 있다.
여기서 중요한 건 A는 해시 함수가 바뀌지 않는한 해싱 했을 때 Alpha라는 일정한 값이 나온다는 것 (충돌이 일어나는 특정한 경우를 제외하고)과 어떤 입력값이든 해싱을 통해서 나온 결과값은 모두 5글자의 영문이라는 것이다.
A를 여러 번 해싱 했을 때 Bravo나 Cycle이 나온다면 잘못된 해시 함수를 가졌다고 봐야한다.
해시 함수 (Hash Function)
그렇다면 해시 함수는 무엇일까?
나무위키의 정의를 가져와봤다.
해시 함수는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다.
처음 예시에서 임의의 데이터는 입력값이고 고정된 길이의 데이터는 결과값이라는 것을 알 수 있다.
여기서 또 한 가지 중요한 사실은 해시 함수는 단방향 함수 라는 것인데, 이건 결과값을 역으로 해시함수를 통해 입력값으로 바꿀 수 없다는 것이다. 들어올 때는 마음대로겠지만 나갈때는...
해시 함수 용도
단방향 함수라는 특징으로 다양한 분야에서 유용하게 사용된다.
- 자료 구조
- 해시 테이블 또는 해시 맵이라는 형태로 O(1)의 시간 복잡도로 접근하는데 사용된다.
- 특정 Key를 해싱해서 나오는 문자열에 Value들을 저장해놓음으로써 Key에 따라 바로 원하는 값을 찾을 수 있다.
- 프로그래밍 언어에서 제공되는 해시 함수
- Java : Hash Map
- Javascript : 객체 or Map
- Python : 사전(dictionary)
- 암호화
- 입력값을 해싱했을 때 출력값은 일정하다는 것을 근거로, 사용자의 비밀번호나 중요 정보의 내용을 해싱하여 복호화 할 수 없게 만드는 것이다.
해싱 구조
키 (Key)
해싱할 때 입력값을 키라고 한다. 키는 중복되지 않는 고유한 값이다.
해시 함수를 통한 키 값은 특정한 값으로 매핑(Mapping)되는데, 해시 함수에 따라서 2개 이상의 입력값이 하나의 값으로 매핑될 수 있다.
해시 테이블 (Hash Table)
해시 함수로 매핑한 키 값을 인덱스로 한 배열 혹은 객체이다.
📍 프로그래밍 언어에 따라서 다르게 불릴 수도 있으므로 이 글은 자바스크립트를 기준으로 설명한다.
해시 테이블은 키 값을 해싱해서 얻은 값을 주소로 만들어진 자료 구조다. 해시 테이블에서 행은 버켓 (Bucket)이라고 하며, 열은 슬롯 (Slot)이라 한다.
하나의 버켓에는 여러개의 슬롯이 있을 수 있다. 가장 좋은 방법은 하나의 버켓은 하나의 슬롯만 갖고 있는 것이지만, 현실적으로 모든 값이 하나의 해시 주소를 갖는 것은 어렵다.
충돌 (Collision)
위에서 언급했듯이 키 값을 해싱해서 얻은 값들이 모두 고유한 값은 아니다. 해시 함수에 따라서는 여러 키 값이 하나의 값으로 매핑될 수 있는데, 이런 경우를 해싱 충돌 이라고 한다.
해싱 충돌은 원치 않는 문제를 일으킬 수 있다. 특히 암호와 관련된 보안에서는 보안이 뚫리는 심각한 문제가 발생할 수 있으므로 대비할 필요가 있다.
해싱 기법
- 자료 구조
- 제산법 : 버킷 주소(인덱스) = 키 % 버킷 크기
- 중간 제곱법 : 키 값을 제곱한 후 결과 값의 중간 부분에 있는 비트만 선택해서 버킷 주소로 사용
- 보안
- MD5 : 충돌 회피성의 문제로 현재는 사용 중지
- SHA : 현재 가장 많이 사용되는 해싱 암호화
자바스크립트에서는 해시 함수를 아주 많이 사용하고 있다. 대표적으로 사용되는 해싱이 바로 객체(Object)이다.
물론 Map이나 Set과 값은 해싱 테이블을 명시한 자료 구조가 있지만, 객체의 프로퍼티를 검색할 때 Key(문자열)을 통해 Value를 조회하는 것이므로 해싱이라 볼 수 있다.
& 참고 자료
