Hash | 악어새62

개요

해시라는 것은 일정한 규칙 없이 조작하거나 변환한다는 의미로 우리에게 익숙한 해시는 해시 브라운(감자를 잘게 썰어 조리한다.)이 있다. “잘게 자르다”라는 뜻의 고어에서 유래했다고 한다.

오늘은 해시 함수에 대해 알아보자.

해시 함수

해시 함수는 쉽게 말하면 임이의 길이를 가진 데이터를 입력받아 고정된 길이의 값인 해시값을 출력하는 함수다.

간단히 예를 들면 다음과 같다.

int hashFunction(int key) {
  return  key % 10;
}

키 값을 입력받아 10으로 나눈 나머지를 반환하고 이 값은 데이터가 저장될 테이블의 인덱스로 사용될 수 있다.

예를 들어 입력값이 123인 경우 해시값은 3이다. 이 3을 해시 테이블의 인덱스에 저장한다. 그리고 3의 인덱스는 특정 데이터를 가리키게 만든다.

123 -> 3 -> "Apple"

나중에 123을 찾으려면 123을 해시함수에 넣어 인덱스 값을 알아내어 바로 “Apple”에 접근하여 시간복잡도 O(1)로 찾아낼 수 있다.

해시 함수는 특히나 암호학 분야에서 중요한 개념이다. 다양한 방식의 해시함수들이 존재하고 블록체인 분야에서도 널리 쓰인다.

어떻게 암호화 알고리즘으로 쓰일 수 있을까? 굉장히 간단해보이는데 하고 생각할 수도 있겠다.
위에서 본 예제는 굉장히 단순하여 입력 데이터에서 해시값으로 변환하기 위해 한 번의 역산만 거치면 되지만 실제 해시 알고리즘은 굉장히 복잡하여 해시값에서 원래 데이터로의 역변환은 거의 불가능하다.

이게 해시 함수의 특징중 하나인 단방향성이다.
역변환이 어려운 정도를 의미하는 역상 저항성은 해시함수가 특정한 값을 출력하는 입력값을 찾기 어려움을 의마한다.

위의 예제를 보면 10으로 나눈 나머지를 해시값으로 사용하고있는데 10으로 나눴을 때 나머지가 3인 경우는 굉장히 많다. 정확한 키 값이 아닌 다른 값을 대입해도 해시 값이 같기 때문에 키 값으로 의미가 없지는 않을까??

여기에는 해시 충돌이라는 개념이 있다. 단방향성과 같이 해시 충돌도 해시 함수의 중요한 특징이다.

이를 의미하는 단어가 바로 충돌 저항성이다. 충돌 저항성이 높다는 것은 어떤 해시 함수가 충돌하는 서로 다른 두 입력값을 찾기 어려움을 의마한다.

이를 막기 위한 방법은 체이닝과 개방 주소법이 있다.

체이닝 방식은 충돌이 발생할 경우 해시 테이블의 각 인덱스에 연결리스트를 사용하여 여러 개의 값을 저장하는 방식이다. 하나의 인덱스에 다수의 키-값 이 저장되는 것이다.

예를 들어 3 -> (123, “Apple”) -> (133. “Banana”)와 같은 식이다.

개방 주소법은 해시 테이블 내부에서 빈 슬롯을 찾아 충돌을 해결하는 방식으로 데이터는 해시 테이블의 내부 슬롯에 저장되며 충돌이 발생했을 때는 다른 빈 슬롯을 탐색해 데이터를 저장한다. 3 -> (123, “Apple”) 충돌 발생! 4 -> Null

3 -> (123, “Apple”) 4 -> (133, “Banana”)

또 다른 중요한 특성은 고정된 결괏값의 길이다.
해시 함수는 항상 일정한 길이의 결괏값을 출력한다.

이 것이 중요한 이유는 여러가지 이유가 있다.
우선 고정된 길이의 해시 값은 충돌 가능성을 줄이는 데 중요한 역할을 한다. 예를 들어 해시가 너무 짧으면 충돌이 빈번하게 발생하고 해시가 너무 길면 메모리 낭비가 될 수 있다. 따라서 고정된 길이의 해시를 사용하면 이를 균형있게 다룰 수 있게 된다.

해시 테이블은 고정된 크기의 배열로 이루어져있다. 해시 함수는 이 배열에서 데이터를 저장할 인덱스를 찾아준다. 그리고 해시 함수가 고정된 길이의 결과 값을 반환함으로써 테이블의 크기도 정해진다.

해시 맵

해시 맵은 시간 복잡도가 O(1)인 것으로 유명하다. 해시 맵이란 해시 함수를 사용하여 데이터를 저장할 위치를 계산하고 그 위치에 데이터를 저장하고 빠르게 찾을 수 있는 자료구조다.

위에서 살펴본 것과 동일한다.

해시 맵은 내부적으로 다음과 같은 방식으로 동작한다.

키와 값을 저장
해시 함수 실행
해시 테이블에 저장
충돌 처리

HashMap<String, Integer> map = new HashMap<>();
map.put("Apple", 1);

int value = map.get("Apple");

위와 같은 코드가 있다고 했을 때 우선 키를 해시 함수에 전달하여 해시 값을 계산하고 해시 값을 기반으로 배열의 특정 인덱스를 찾아 그 위치에 키와 값을 저장한다.
검색시 키를 해시 함수에 전달하여 해당 키의 해시 값을 계산하고 계산된 해시 값에 해당하는 인덱스로 이동하여 값을 찾는다.
이러한 원리로 해시 맵은 시간복잡도 O(1)로 데이터를 찾을 수 있는 것이다.