[CS] 해시(Hash)

해시(Hash)

Array로 되어있는데 index값을 몰라?!?!?

그럼 key값을 해시함수로 돌려서 index를 찾아내! (무조건 정수값)

임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 것

원본 데이터를 키(Key), 매핑 과정을 해싱(Hashing), 결과물로 나온 데이터를 해쉬값(Hash value), 데이터를 해싱하는 함수를 해시함수(Hash function) 라고 한다.

 

예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.

이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다.

 

 

특징

1. 임의 길이의 데이터로부터 고정된 길이의 해시값을 계산한다.

2. 해시값을 고속으로 계산할 수 있다.

3. 단방향성을 갖기 때문에 해시값으로부터 key를 역산할 수 없다.

4. key가 다르면 해시값도 달라져야 한다. (서로 다른 key가 같은 해시값을 갖는 경우 충돌(collusion)이라고 한다.

 

 

충돌 문제 해결

1. 체이닝 : 연길리스트로 노드를 계속 추가해나가는 방식

• 충돌을 허용하되, 최소화하는 방식에 가깝다.
• key값을 포인터로 이어서 연결
• 최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도를 가짐
• JDK 라이브러리에 구현된 HashMap 은 chaining 방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될수 있다

 

2. Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용한다.

• 모든 데이터를 테이블에 저장하는 방법
• 사용하려는 해시 버킷(테이블)이 이미 사용중인 경우 다른 버킷을 사용
• 포인터를 쓰지 않아 오버헤드를 방지할 수 있고 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높다
• 포인터가 필요없어 구현이 훨씬 용이해졌으며, 포인터 접근에 필요한 시간이 없어졌기 때문에 큰 성능향상이 있다.
• 하지만 테이블의 크기가 커질수록 장점이 사라진다
• Linear Probing
  • 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음인덱스에 저장

 

3. 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피한다.

 

 

해시 함수

1. MD-5

Message Digest, 입력된 데이터를 각 512bit의 블록들로 나누어 처리하여 128bit 길이의 해시값을 출력하는 함수

현재는 보안을 위해 사용하는 것이 권장되지 않는다.

2. SHA

Secure Hash Algorithm, 입력 데이터를 나누는 블록의 크기, 계산되는 해시값의 크기, 최대 입력 데이터 길이, 단계 수 등이 다른 여러 버전이 있다.

SHA-1는 보안상 취약점이 발견되어 사용을 지양하고, SHA-256, SHA-512 사용이 권장된다.

https://passwordsgenerator.net/sha256-hash-generator/

해시함수 사용해볼 수 있는 사이트

 

같은 key에 대해 항상 동일한 해시값을 계산해내기 때문에 무결성 점검, 소프트웨어 변형 검출, 메시지 인증 코드, 전자서명 등에 사용된다.

 

 

 

 

https://runa-nam.tistory.com/84

https://steemit.com/kr/@ohrak22/hash

https://ablue-1.tistory.com/68

https://mangkyu.tistory.com/102

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/