[PCCP] 자료구조 - 해시

1. 이론

- 해시(hash): 해시함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

- 해시 특징: 단방향 동작(키를 통한 값 탐색만 가능). 키가 값의 인덱스이므로 값을 찾기 위한 탐색과정이 없음. 값을 인덱스로 사용하려면 변환 과정이 필요

- 해시테이블: 키와 값이 저장되어 있는 공간

- 버킷: 해시테이블의 각 데이터

- 해시 ADT: 

 

(시간복잡도)

- 임의 접근(탐색): O(1)

- 삽입:

- 삭제:

 

(선택시 고려할 점)

- 단방향 검색이지만 빠른 검색이 필요한 경우

 

(해시함수 구현시 고려사항)

- 해시함수 변환값은 해시테이블의 크기보다 작아야함

- 변환값의 충돌이 최대한 적어야함

+) 충돌: 서로 다른 두 키에 값을 적용시 동일한 결과를 의미

 

(주요 해시함수)

- 나눗셈법: x mod k(m: 키값, k: 소수)

- 곱셈법: ((x*A)mod 1)*m(x: 키값, A: 황금비, 1: 소수부분 모듈러 연산, m: 최대 버킷 수)

- 문자열해싱: (s[0]%m + s[1]*p%m + s[2]*(p^2)%m + ... + s[n-1]*(p^(n-1))%m) mod m(p: 홀수이며 메르센소수 31)

+) 메르센소수: (2^N - 1) 중 소수

+) 문자열 해싱은 polynomial rolling method 이용

 

(충돌 처리기법)

- 체이닝기법: 값 충돌시 링크드리스트로 데이터 연결. 검색 성능 저하. 공간활용성 저하

- 개방주소법: 빈 버킷을 찾아 충돌값 삽입. 선형탐색법과 이중해싱방식

+) 클러스터: 충돌이 발생한 값끼리 모이는 영역

 

2. 프로그램 언어별 문법

- 해시 선언 및 초기화

- 해시 접근

- 해시 제어: 삽입, 삭제

 

<C언어>

 

 

<C++>

- 정렬된 해시: 트리 구조

#include <map>

/* 해시 선언 및 초기화 */
std::map<string, int> m;

/* 삽입 */


/* 삭제 */


/* 변경 */


/* 조회 */


/* 전체 조회 */


/* 기타 메서드 */

- 정렬되지 않는 해시: 해시 구조

#include <unordered_map>

/* 해시 선언 및 초기화 */
std::unordered_map<string, int> um;


/* 삽입 */


/* 삭제 */


/* 변경 */


/* 조회 */


/* 전체 조회 */


/* 기타 메서드 */

 

<C#>

 

 

<Java>

 

 

<Python>

# 해시 선언 및 초기화
dic = dict()
dic = {}
dic = {key: val, ...}

# 삽입 
dic[key] = val


# 삭제
del dic[key]

# 변경
dic[key] = val

# 조회
dic[key]

# 전체 조회
for k, v in dic.items():
    print(k, v)

# 기타 메서드
dic.keys()    # 딕셔너리의 키들의 집합
dic.values()  # 딕셔너리의 값들의 집합
dic.items()   # 딕셔너리의 키와 값쌍들의 집합

 

 

<JavaScript>

 

 

 

 

3. 추천 문제

(프로그래머스)

- Lv 1: 완주하지 못한 선수(42576) / 완주하지 못한 선수(42576) 해설
- Lv 2: 영어 끝말잇기(12981) / 영어 끝말잇기(12981) 해설 (JS X)
- Lv 2: 전화번호 목록(42577) / 전화번호 목록(42577) 해설 (Java/JS X)
- Lv 2: 할인 행사(131127) / 할인 행사(131127) 해설
- Lv 2: 오픈 채팅방(42888) / 오픈 채팅방(42888) 해설
- Lv 3: 베스트 앨범(42579) / 베스트 앨범(42579) 해설
- Lv 1: 신고 결과 받기(92334) / 신고 결과 받기(92334) 해설
- Lv 2: 메뉴 리뉴얼(72411) / 메뉴 리뉴얼(72411) 해설

- Lv 2: 의상(42578) / 의상(42578) 해설
- Lv 2: [3차] 압축(17684) / [3차] 압축(17684) 해설