[자료구조] Hash Table

✅ 해시 테이블 (Hash Table)

❕ 기본 개념 

- 키(Key)와 값(Value) 한 쌍의 형태로 데이터를 저장하는 자료구조

- 해시함수를 사용하여 키를 해시값으로 매핑한 후, 이 해시값을 인덱스 혹은 주소로 삼아 데이터 값을 키와 함께 저장함

- 해시값이 충돌할 때는 연결리스트를 사용하여 유연하게 데이터를 저장할 수 있음

- 검색을 빠르게 할 수 있기에 배열 내의 특정 데이터에 빠르게 접근할 수 있음

- 데이터 검색 시 시간복잡도: 평균 O(1), 최악의 경우 O(n)

 

- 해시 테이블에 사용하는 배열의 크기를 적절히 설정하는 것이 중요함

- 배열의 크기가 너무 작으면 충돌이 많아지고 선형 탐색의 빈도가 높아짐

- 반대로 배열의 크기가 너무 크면 데이터가 빈 곳이 많아져서 메모리를 낭비하게 됨

 

 

❕ 작동 방식 

총 6명의 사람들에 대해 이름을 Key로, 성별을 Value로 저장하는 경우에 대해서 알아보자.

 

 

이 데이터들을 단순 '배열'에 저장했을 때 Ally의 성별을 알고 싶다고 가정해보자.

 

 

Ally가 배열의 몇 번째 인덱스에 저장돼있는지 모르므로,

Ally의 정보를 찾을 때까지 맨 앞에서부터 차례대로 선형 탐색을 해야한다.

선형 탐색은 데이터양에 비례해서 계산 시간이 늘어나기 때문에, 배열은 빠른 탐색에 적합하지 않은 구조라는 것을 알 수 있다.

 

이 문제를 해결해주는 것이 해시 테이블이다.

 

먼저, 데이터를 저장하기 위한 배열을 준비한다. (여기서는 길이 5의 배열을 만들었음)

 

 

이 배열에 Joe의 데이터를 추가해보자.

1. 해시 함수를 이용해서 Joe의 key인 문자열 "Joe"에 해당하는 해시값을 계산한다. ☜ 4928
2. 구한 해시값을 배열의 길이로 나누어 나머지를 구한다. (mod 연산 사용) ☜ 4928 mod 5 = 3
3. 배열의 인덱스 값이 mod 연산 결과값과 일치하는 곳에 Joe의 데이터를 저장한다. ☜ array[3]에 Joe 데이터 저장

위의 1~3 과정을 반복해서 다른 사람들의 데이터도 하나씩 채워준다.

 

 

데이터 저장 위치가 겹치는 충돌이 일어나게 된다면 연결리스트 구조로 기존 데이터와 연결하여 저장한다.

 

 

이제 여기서 Ally의 정보를 다시 찾아보자.

Ally가 몇 번째 index에 저장돼있는지 알기 위해서 "Ally"의 해시값을 배열의 길이 5로 mod 연산을 해준다.

mod 연산 결과가 3이 나옴에 따라 배열의 3번 index에 저장된 값을 확인한다.

하지만 3번에 저장된 데이터의 키는 "Joe"이지 "Ally"가 아니다.

 

 

Joe의 데이터를 선두로 해서 만들어진 리스트를 대상으로 Ally를 찾을 때까지 선형 탐색을 실시한다.

"Ally"라는 key를 가진 데이터를 발견하면 그 value를 추출하여 Ally의 성별을 확인할 수 있다.

 

 

✔ 활용 예시 

- 파일 시스템 ☜ 파일명 - 파일 경로 매핑

- 로그인 시 비밀번호 암호화 ☜ 서버로 로그인 정보 전송 시 plain text로 보내지 않고 해시값으로 전송

- Pattern Matching ☜ 문자열 속의 패턴을 찾는 알고리즘(표절 검사기에 사용되는 알고리즘) 구현에 해시가 사용됨.

- 많은 프로그래밍 언어의 기본 데이터 타입, 내장 라이브러리 등이 해시 테이블로 구현됨 (ex. Python의 dictionary / Java의 HashMap)

 

 

참고자료

「알고리즘 도감」 中 1-6 해시 테이블

https://comscigate.com/ciips/niemann/s_has.htm

https://afteracademy.com/blog/applications-of-hash-table