[C++] 해시 테이블

 

 

 

 

해시 테이블

특정 값을 찾고자 할 때 사용한다. 검색을 위한 자료구조

기본적으로 선형 리스트 구조로 구성되어 있다.

해싱을 통해 배열의 인덱스 값을 구하고자 할 때 사용한다.

인덱스 값을 반환하기 때문에 입력, 검색, 삽입, 삭제 O(1)의 시간이 소요된다.

(항상 정렬되어 있어야 한다 : 이진검색트리 / 데이터만 저장되어 있으면 된다 : 해시 테이블)

유저 데이터 또는 업데이트 정보 등 고유한 값이 필요할 때 사용할 수 있다.

 

해싱(hashing)

어떤 입력이 주어지든 고정된 길이의 출력으로 바꾸는 것

입력 크기에 상관 없이 일정 크기의 값으로 변환하는 것

이에 사용되는 함수를 해시 함수라 한다.

 

해시함수 테스트 (joongbu.ac.kr)

해시함수 테스트

SHA256 : 256bit(64개의 16진수)의 값으로 표현된다 (0 ~ 2^255)

 

 

해시 테이블의 3가지 성질

1) 균일성

충돌(서로 다른 값이 같은 해시값을 생성한 것)이 적은 것

비트수에 따라서 데이터를 표현하는 범위가 정해지는데  데이터가 범위에 고루고루 퍼지게 해야한다.

 

 

2) 효율성

해시값을 계산하기 쉬워야 한다.

 

 

3) 결정적

같은 입력에는 같은 값을 반환해야 한다.

 

 

충돌 처리

1) 선형 개방 주소법 or 선형 조사법

충돌이 발생하면 빈 공간을 찾아서 넣는다.

 

 

2) 체이닝

충돌이 발생하면 리스트로 여러 값을 저장하게 한다.