Algorithm - Hashing(해싱 알고리즘)

Hash?

- 해시에는 크게 Hash, Hash function, Hashing, Hash table 이렇게 네가지로 나뉘어짐.

 

ㆍHash :

해시는 데이터를 다루는 기법 중의 하나로 검색과 저장을 아주 빠르게 하는 자료구조이다. 데이터를 저장할때 Key, Value 형태로 데이터가 존재하고, Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장을 빠르게 할 수 있음.

 

ㆍHash function과 Hashing

Hash function은 Key값을 고정된 길이의 hash로 변환하는 역할을 함. Hash function에서 Key값을 hash로 변환하는 과정을 hashing이라고 한다. Hash function에서는 Key값을 해싱 과정을 통해 Hash value(해시 값) 또는 Hash code로 변경하며, 이 해시 값이 저장위치가 됨. 서로 다른 key가 같은 해시가 되는 경우는 Hash collision이라고 함. Hash collision을 일으키는 확률을 최대한 줄이는 함수를 만드는것이 중요!

- 해시 함수는 입력값이 조금만 변해도 결과가 크게 달라지는 특징도 있는데, 이를 눈사태 효과라고 함. 의외로 중요한 특징인데, 시저 암호같은 고대 암호는 알파벳의 특정 빈도수, 미리 해석한 반복되는 문장 패턴 등을 대입해 부분적인 해독을 할 수 있었음. 그러나 해시는 입력한 데이터 전체를 한번에 암호화 시키므로 이런 전략이 통할 수 없다. 체크섬이 이를 이용한 방식인데, 해커가 아무리 악성 코드를 숨겨놓아도 원본에서 단 1글자라도 바뀐다면 체크섬이 완전히 달라짐. 패턴도 결함도 없기 때문에 방법은 찍는것 뿐이다. 이때 GPU를 몇십개씩 쌓아두고 하나씩 대입해가며 찍는게 브루트 포스, 남들이 일일히 삽질한 데이터로 뚫어보는 방식이 레인보우 테이블 전략이라함.

- 해시 함수가 이용되는 분야 : 자료구조(Hash table, Hash set, Bloom filter), 캐시, 중복 레코드 검색, 유사 레코드 검색, 유사 부분 문자열 검색, 기하학적 해시, 변조 탐지/에러 검출

 

ㆍHash table

Hash table은 연관 배열구조(key를 통해 연관되는 value를 얻을 수 있는 자료구조/ 키와 값이 주어졌을 때, 연관 배열에 그 두 값을 저장하는 명령 지원/ 키가 주어졌을 때, 연관되는 값을 얻는 명령 지원/ 키와 새로운 값이 주어졌을 때, 원래 키에 연관된 값을 새로운 값으로 교체하는 명령 지원/ 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 명령 지원)를 이용하여 데이터를 Key와 Value로 저장하는 자료구조이다. Hash table은 Hash function을 사용하여 index를 bucket이나 slot의 배열로 계산한다.

장점 : 중복을 제거할 수 있음/ 데이터 캐싱이나 보안에 주로 사용됨/ 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠름.

단점 : 공간 복잡도가 커짐/ 충돌이 발생할 수 있음(충돌 발생시 시간복잡도는 O(n)에 가까워짐)/ 순서가 있는 배열에는 어울리지 않음.

 

Hash table 과 Hash map 차이

- Java의 경우, 해시 테이블은 동기화 지원해주고 Null 허용을 안함. 해시 맵은 동기화 지원안해주고 Null 허용함. 이 차이를 제외하고는 사용법 동일함. 

 

Collision(충돌)

Collision이란 서로 다른 문자열이 해시 함수를 통해서 해싱한 해시값이 중복인 경우를 말함. 충돌이 많아질수록 탐색의 시간 복잡도가 O(1)에서 점점 O(n)에 가까워지게 됨. 그래서 충돌을 줄여주는 해시 함수를 사용하는 것이 좋음.

충돌을 해결해주는 방법 :

ㆍSeparate chaining

- Linked List, Tree(Red-Black Tree)

- JDK 내부에서 사용하는 충돌 처리 방식으로, Linked List나 Red-Black Tree를 사용하는 방식임. 두 개의 기준은 data가 6개 이하면 Linked List를, 8개 이상이면 tree를 사용함. 기준이 6과 8인 이유는 바꾸는데 오버헤드가 있기 때문.

- Linked List를 사용할 경우, 인덱스 충돌이 났을 때 인덱스가 가리키고 있는 Linked List에 노드를 추가하여 삽입한다. 데이터를 탐색할 때는 키에 대한 인덱스가 가리키고 있는 Linked List를 Linear search하여 해당 키에 대한 데이터를 반환함. 삭제하는 것도 마찬가지로 노드 삭제. -> Separate Chaining 방식은 Linked List 구조를 사용하므로 추가할 수 있는 데이터 수의 제약이 작음.

ㆍOpen addressing 

- Linear Probing, Quadratic Probing, Double hashing

- 인덱스에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리를 사용하지 않고, Hash table array의 빈 공간을 사용하는 방법. Separate chaining 방식에 비해 메모리를 덜 사용함. 

- 인덱스가 중복되는 충돌이 발생할 때 인덱스 뒤에 있는 버킷 중 빈 버킷을 찾아 데이터를 삽입함.

Resizing :

- Separate Chaining의 경우, 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에 검색 성능이 떨어지게 되므로 버킷의 개수를 늘려줘야 함. 

- Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장해 줘야함.

- 보통 두배로 확장하는데, 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor라고 불림. resizing은 더 큰 버킷을 가지는 array를 새로 만든 다음, 기존 array의 hash를 다시 계산해서 복사해줘야함.

 

보안 분야에서 해시를 사용하는 이유 :

- 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시 값만 가지고 키를 복원하기 어려움.

- 해시 함수의 결과물은 고정된 길이의 숫자이므로, 원래의 정보는 손실되므로 원데이터를 알 수 없음.

 

유명한 해시 알고리즘 Message-Digest Algorithm(MD), Secure Hash Algorithm(SHA)

- MD5 : 길이를 임의의 값을 입력받아서 128비트 길이의 해시값을 출력하는 알고리즘. MD5는 단방향 암호화이기 때문에 출력값에서 입력값을 복원하는것은 할 수 없음. 같은 입력값이면 항상 같은 출력 값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮음. 패스워드 암호화에 많이 사용되고, 패스워드를 MD5로 해시해서 나온 값을 저장해 두는 것. 현재는 MD5 알고리즘을 보안 관련 용도로 쓰는 것을 권장하지 않으며, 심각한 보안 문제를 야기할 수 있다함.

- SHA : 1993년부터 미국 NSA가 제작하고 미국 국립표준기술연구소(NIST)에서 표준으로 채택한 암호학적 해시 함수. 1992년 SHA-0부터 시작해서 해시 충돌을 이용한 위험성이 발견될 때마다 버전을 개선해서 제작한다함. 해시 길이가 길수록 더 안전. 대한민국 인터넷 뱅킹은 SHA-256사용.