Hash

나는 Hash를 생각하면 항상 떠오르는 단어가 있다. 

바로 해시포테이토!! 

Hash의 뜻은 으깨다인데 해시포테이토도 생각해보면 으깬감자를 양념해서 뭉쳐놓은 것이다.

컴퓨터쪽으로 생각해보면 원본데이터를 으깨서 일정한 크기의 비트나열로 만든 것이 된다. 

잘 이해하기 힘들었던 Hash의 정의를 위와같이 풀어서보면 좀 쉽게 이해할 수있을 거 같아서 적어봤다.

 

Hash

단반향 암호화기법으로 해시함수를 이용해서 고정된 길이의 암호화된 문자열로 바꾸는 것을 의미한다.

원본데이터의 수는 무한대이며 어떤 데이터든 상관이 없다.(정수, 실수, 문자, 문자열 뭐든지!)

매핑전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(Hash Value) 또는 해시코드 라고 하며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing) 이라고 한다.

 

해시함수(Hash Function)

해시함수는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

그렇기에 책줄거리를 넣던 짧은 단어를 넣든 똑같은 길이의 해시값이 리턴된다. 하지만 입력된 값이 조금이라도 변경이 있다면 다른 해시값을 출력하며 같은 입력값에는 항상 같은 해시값을 출력한다.

 

해시테이블(Hash Table)

키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. 즉, 키(key)와 배열의 인덱스(index)를 이용하여 키를 저장하는 자료구조이다. 

해시 테이블은 키를 해시 함수(hash function) 로 계산하여 그 값을 배열의 인덱스로 사용한다. 이때, 해시 함수에 의해 반환된 데이터의 고유 숫자 값을 해시값 또는 해시코드 라고 한다. 즉, key 값을 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다.

원래 데이터의 값(Key) -> Hash Function -> Hash Function의 결과 = Hash Code

-> Hash Code를 배열의 Index 로 사용 -> 해당하는 Index에 data 넣기

https://hee96-story.tistory.com/48

 

이런식으로 데이터를 저장하다 보면 계산된 인덱스 값이 중복될 수가 있다. 예를 들어 저장하고자 하는 키가 정수이고 hash_function이key%10이다. 전체 사이즈가10일때, key 1,11,21은 같은 인덱스 값을 가지게 된다. 충돌 (collision) 이라고한다.

 

해시충돌(Hash Collision)

해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 

해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 해시 충돌은 항상 존재한다.

그래서 충돌을 줄여주는 좋은 해시 함수를 사용하는 것이 좋다. 왜냐하면 충돌이 많아질 수록 탐색의 시간 복잡도가 O(1)에서 O(n)에 가까워지기 때문이다. 

 

해결방법

• Separating Chaining - Linked List, Tree(Red-Black Tree)
• Open addressing - Linear Probing, Quadratic Probing, Double hashing

 

Separating Chaining

JDK내부에서도 사용하고 있는 충돌 처리 방식인데, 버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다.

Separating Chaining - Linked list

Separate changing  방식은 Linked List 구조를 사용하고 있기 때문에, 추가할 수 있는 데이타 수의 제약이 작다.
JDK 1.8의 경우에는 index에 노드가 8개 이하일 경우에는 Linked List를 사용하며, 8새 이상으로 늘어날때는 Tree구조(Red-Black tree)로 데이터 저장구조를 바꾸도록 되어있다.

Open addressing

index에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용하는 방법이다

Open addressing  방식은 Linear Probing, Quadratic Probing, Double hashing 등이 있다.

Open addressing - Linear Probing

Linear Probing방식은 인덱스가 중복되는 충돌이 발생할 때 인덱스 뒤에 있는 버킷중에 빈 버킷을 찾아서 데이터를 넣는다. 그림에서 Sandra(key)의 인덱스는 152이다. 하지만 키 John과 충돌이 나기 때문에 그 다음 인덱스인 153에 데이터를 넣는다.

Linear Probing방식에서의 탐색은 Sandra(key)에 대해서 검색을 하면, index가 152이기 때문에, key가 일치하지 않기 때문에 뒤의 index를 검색해서 같은 키가 나오거나 또는 Key가 없을때 까지 검색을 진행한다.

이러한 Open Addressing의 단점은 삭제가 어렵다는 것인데, 삭제를 했을 경우 충돌에 의해서 뒤로 저장된 데이타는 검색이 안될 수 있다.

단점

Resizing

Separate changing에 경우에도 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에, 검색 성능이 떨어지기 때문에 버킷의 개수를 늘려줘야 한다.
Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이타를 더 넣기 위해서는 배열을 확장해야 한다.

이를 Resizing이라고 하는데, Resizing은 별다른 기법이 없다. 더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 array에 hash를 다시 계산해서 복사해줘야 한다.

 

해시충돌이라는 단점에도 사용하는 이유?

1. 보안

2. 적은 리소스로 많은 데이터를 효율적으로 관리가능

3. index(색인)에 해시값을 사용해서 모든데이터를 보지않고도 삽입/삭제가 빠르게 수행

 

Java HashMap관련 읽기좋은 글

https://d2.naver.com/helloworld/831311

 

 

 

참고

https://bcho.tistory.com/1072 

https://hee96-story.tistory.com/48

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=taeil34&logNo=221212051907