[CS] Hash Table을 알아보자

Hash Table이란?

데이터를 효율적으로 저장하고 검색하는 데이터 구조

키와 값의 쌍으로 이뤄진 데이터를 저장하며, 각 키는 고유한 해시 값으로 매핑된다.

 

해시 테이블은 배열을 기반으로 구현되며 해시 함수를 사용해 키를 배열의 인덱스로 변환한다.

해시 함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수, 키의 고유한 해시 값을 계산하는 함수를 말한다.

 

해시 테이블에 저장하고자 하는 임의의 원소의 해시값을 해시 함수를 이용해 계산한다.

계산한 해시 값을 주소로 하는 위치에 원소를 저장하면, 검색을 할 때도 바로 이곳으로 이동할 수 있다.

 

해시 함수의 특징은 같은 입력값에 대해 같은 출력값을 보장한다(일관성)는 것이다.

그렇기에 서로 다른 입력값에 대해서는 동일한 출력값이 나올 확률이 희박해 입력값에 대한 무결성이 보장된다.

또 일방향성을 갖는다. 입력값 -> 해시값은 아래와 같은 알고리즘으로 만들기 쉽지만 해시값 -> 입력값으로 역추적하기는 매우 어렵다.

 

SHA256 Hash Generator Online

 

해시 알고리즘으로는 SHA가 많이 쓰이는데 256은 해싱(데이터를 해시 코드로 변환하는 과정)을 하면 2^256개의 해시 값 중 하나가 나타난다고 해서 256이라고 한다.

---

Hash Table의 특징

1. 빠른 검색/삽입/삭제

위에서 말한 것처럼 해시 값으로 저장된 위치를 찾을 수 있어서 검색/삽입/삭제 시 시간 복잡도는 O(1)이다.

하지만 해시 충돌(후술)이 발생하는 경우 Linked List나 트리에서 순차적인 작업이 필요할 수 있어 O(n)까지 걸린다.

 

2. 해시 충돌

서로 다른 키가 같은 해시 값으로 매핑되는 상황을 말한다. 

한 호텔에서 김씨, 이씨, 박씨 처럼 성씨에 따라 방을 제공하려고 한다.

그런데 김씨가 너무 많아서 K층에만 사람이 바글바글하다.

즉 서로 다른 이름의 투숙객들이 K라는 동일한 해시 값으로 매핑이 되어 있는 것이다.

 

원래는 김씨를 찾으려면 K층에서 어이 김씨 하면 바로 찾을 수 있었는데 이처럼 김뫄뫄, 김무무, 김땡땡처럼 김씨 이름을 가진 사람들이 많아지면 어이 김씨 해도 셋 다 나? 하고 혼란이 오는 것이다. 

 

이럴 때 어떻게 해야 하냐?

 

1) 체이닝

같은 주소로 해싱된 원소들을 모두 하나의 연결 리스트에 매달아서 관리한다.

[K층 - 김뫄뫄 - 김무무 - 김땡땡] 이렇게 묶어놨다. 

따라서 김아무개를 찾으려면 K층의 연결 리스트를 모두 순회해야 한다.

이러면 같은 층에 할당된 원소들을 결국 모두 순회해야 하기 때문에 효율성이 좋지 않게 된다.

 

자바 스크립트의 경우에는 이렇게 배열을 넣어서 표현한다. 이 인덱스 4에서 선형 검색을 하는 것.

 

2) 개방 주소법

체이닝과 달리 어떻게든 주어진 테이블 공간에서 해결한다.

모든 원소가 반드시 자신의 해시값에 해당된다는 보장이 없다.

무슨 말이냐면 현재 K층은 바글바글한데 L층, P층은 사람이 없다.

그럼 K층에 있는 사람들을 L층, P층, C층 등 비어 있는 다른 층으로 보내는 것이다.

 

이렇게 다른 층으로 보내는 것도 여러 방법이 있다.

 

선형 조사는 충돌이 발생한 층의 다음 층부터 순차적으로 검색해 빈 층을 찾아 거기에 데이터를 저장하는 방법이다. 단 클러스터라고 하는 문제점이 발생한다. 클러스터란 예를 들어 K층이 꽉 차서 L층으로 내렸는데, L층도 꽉 차버린 것이다. 그럼 P층으로, C층으로 점점 내려 보내야 하는데 L, P, C층이 꽉 찬다면 계속 이 쪽들을 지나서 가야 하므로 불필요한 중복 스텝이 이어지는 것이다.

 

이차 조사는 충돌이 발생한 층에서 일정한 간격을 두고 이차 함수를 이용해 다음 층을 찾는다. 클러스터 현상을 완화할 수 있지만 동일한 해시 값에 대해 같은 층을 반복적으로 조사해야 하는 문제가 있다. 

이런 식으로 같은 층을 반복하고 있다.

 

이중 해싱은 두 개의 함수를 사용한다. 하나의 함수로는 최초의 해시값을 얻고 다른 하나의 함수로는 해시 충돌이 일어났을 때 이동할 폭을 구할 때 사용한다. 따라서 첫 번째 함수에서 얻은 최초의 해시값이 같더라도 두 번째 해시값까지 같을 확률은 매우 작아 서로 다른 보폭으로 점프를 하게 된다.

---

자바 스크립트에서는?

직접 해시 테이블을 짤 필요가 없다.

해시 테이블과 유사한 기능을 하는 객체(Object)가 있기 때문! 

객체는 중괄호를 써서 생성하고, 키-값 쌍을 프로퍼티라고 한다.

(**객체 뿐만 아니라 Map으로도 구현할 수 있다.)

 

let hash = {}; // 빈 해시 생성

// 키-값 쌍 추가
hash['key1'] = 'value1';
hash['key2'] = 'value2';

console.log(hash['key1']); // 'value1' 출력
console.log(hash['key2']); // 'value2' 출력

console.log(hash.key1); // 'value1' 출력
console.log(hash.key2); // 'value2' 출력

해시에 있는 값을 검색하려면 해당 키를 사용해 접근할 수 있다.

또 해시에서 키는 고유해야 하기 때문에 중복된 키를 쓰면 마지막에 추가된 값으로 갱신된다.

저렇게 []로 접근하는 방법도 있고, Dot Natation이라고 점 표기법으로 접근할 수도 있다.

 

자바 스크립트에서는 insert(키를 해시테이블에 삽입), search(키를 해시테이블에서 검색), remove(키를 해시테이블에서 삭제)와 같이 명시적인 메서드가 제공되지 않는다. 대신 위에서 쓴 것처럼 키를 사용해서 값을 검색하고, delete를 써서 값을 삭제한다.

---

곧 스터디에서 팀원 분이 해시에 대해 설명을 해주시기로 했는데, 그 전에 문제도 좀 풀어보고 해시에 대해 공부를 해봐야겠다 싶어 오늘 공부를 해봤다. 그런데 구현하는 예시도 그렇고 원리도 그렇고, 대부분 자바에 초점을 맞춘 강의라서 자바 스크립트 유저로서 자바 스크립트에서는 어떻게 쓰이는 건지 궁금했다. 결국 내장이 되어 있어서 자바 스크립트에서 내가 직접 해시 테이블을 만들고 할 일은 없는 것 같지만, 그래도 어떤 원리로 돌아가는지 기본적인 내용은 알아야 할 것 같았다. 자바 스크립트는 알면 알수록 참 신기하고 사용자 친화적인 언어구나.

 

**참고