해시(Hash)

해시(hash)

시간복잡도 : 평균 O(1)

데이터를 해시테이블에 key-value형태로 저장, 관리하며 동적으로 크기가 증가하는 자료구조

내부적으로 배열을 사용하며, 고유한 해시값을 index로 사용하므로 삽입, 삭제 시 데이터 이동이 필요 없고 검색이 빠름

 

 

해시 함수(hash function) 및  해싱(hashing)

• 해시 함수
• 임의의 값 key를 고정 길이의 해시 값(hase value)으로 매핑하는 함수
• 해시함수에 따라 충돌 발생할 수 있음
• 해시 값을 고정 길이로 생성하는 이유 : key값을 그대로 색인에 사용할 경우, key값의 길이만큼 저장 공간을 마련해야 하기 때문
• 단방향 암호화의 대표적인 예(해시값으로부터 원본데이터를 추출할 수 없음)
• key : 매핑 전 원본 데이터
• 해시 값 : 매핑 후 데이터로, 데이터의 저장 위치 역할
• 해싱 : key값을 해시 값으로 변환하는 과정, 매핑

 

해시 테이블(Hash Table)

연관 배열구조를 이용해 데이터를 key-value 형태로 저장하는 자료구조

키를 해시 값으로 매핑하고, 해시값을 주소삼아 value를 key와 함께 저장

* 연관 배열구조 : 자료구조의 일종. 하나의 key와 하나의 value가 연관되어 있으며, key를 통해 value를 구할 수 있음

value가 저장되는 곳을 버킷(buckets) 혹은 슬롯(slot)이라고 함

 

충돌(Collision)

입력값의 범위보다 출력값의 범위가 좁은 경우 다른 key값을 입력해도 동일한 해시 값을 갖게 되는 경우가 있는데, 이처럼 서로 다른 key가 같은 해시값을 갖게 되어 사용하고자 하는 버킷이 동일한 경우를 충돌이라 함

이를 방지하기 위해 중복값을 갖게 되는 확률을 최대한 줄이는 함수를 만드는 것이 중요

관련 알고리즘으로는 MD5, SHA, RIPEMD, CRC32 등이 있음

* MD5의 경우 해시값 구글링해서 원본 값을 구할 수도 있다고 함. 지양하는 추세인 듯함

* SHA-1, SHA-256, SHA-512는 충돌 가능성이 있다는 의견이 제시됨

* 2014년 기준 충돌 문제가 제기되지 않은 해시 표준은 SHA-3

 

 

충돌 처리 방식

• 분리 연결법(Separate Chaining)

• 해시 테이블의 크기를 유연하게 만드는 데 중점을 둠
• 충돌 발생 시 버킷을 연결 리스트 구조로 하여 데이터를 연결하는 방식
• 최악의 경우 모든 데이터가 같은 해시값을 가져 시간복잡도 O(n)이 될 수 있음

• 개방 주소법(Open Addressing)

• 해시 테이블의 크기는 고정시키고, 저장할 위치를 적절히 물색하는 데 중점을 둠
• 충돌 발생 시 빈 공간을 물색하여 데이터를 저장
• 때문에 모든 데이터가 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음
• 정해진 버킷의 개수 이상은 저장 불가
• 연속된 공간에 데이터를 저장하므로 Seperate Chaining에 비해 캐시 효율이 높은 편 → 데이터 개수가 적다면 Open Addressing이 효율적이나, 데이터가 많아질수록(즉, hash table의 크기가 커질수록) 효율이 낮아짐

 

• 기타
• 리스트 크기 재배열, 해시 테이블 확장, 해시 비트 수 늘리기(Consistent Hashing) 등

 

 

해시 사용 예

• 비밀번호 저장
• 복제문서 판별(모든 단어를 비교하기에 오래 걸리므로, 문자열을 축소하는 해시함수를 사용하여 보다 빠르게 비교 가능)
• 검색

 

장점

• 중복 제거 가능
• key를 이용해 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠름

 

단점

• 공간 복잡도 증가
• 충돌 발생할 수 있음

 

 

---

참고

https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C

[알고리즘] 해시(Hash)

https://yjshin.tistory.com/entry/%EC%95%94%ED%98%B8%ED%95%99-%ED%95%B4%EC%8B%9C-%ED%95%A8%EC%88%98-%EC%9E%91%EC%84%B1-%EC%A4%91

[암호학] 해시 함수, 해시 알고리즘, 해시 충돌, 해시 자료구조

https://siahn95.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9CHash%EB%9E%80-2-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94%EC%97%90%EC%84%9C-%EC%B6%A9%EB%8F%8C-%EC%B2%98%EB%A6%AC-%EB%B0%A9%EC%8B%9D

[자료구조] 해시(Hash)란? - (2) 해시 테이블에서 충돌 처리 방식