Chapter 13. 테이블(Table)과 해쉬(Hash)

#13-1. 빠른 탐색을 보이는 해쉬 테이블 1

탐색의 일종인 테이블 해쉬이다.

쉬어가는 페이지이다. 

key, value 쌍을 이루면 테이블이다!!

저장 형태가 key와 value이다!!

key는 사번이 될 수 있다. key를 만드는 공식이 필요하다. key는 중복되지 않음을 강조한다. 저장, 탐색, 삭제 의 핵심!!

key를 만드는 공식이 필요!! > 데이터를 기반으로 결정!(중복되지 않게!!)

key는 value에 해당된다. 

테이블 자료구조는 키만 있으면 담방에 찾을 수 있다. AVL 트리보다 성능이 엄청나다. 

연산이 필요하다. 메모리 적인 단점이 있다. 메모리 효율성이 AVL 트리보다 떨어진다. 적용할 수 있는 범위가 제한적이다. 

사전 구조 또는 맵(MAP)이라고도 불린다!!

#13-1. 빠른 탐색을 보이는 해쉬 테이블 2

테이블을 코드 레벨에서 살펴본다.

#13-1. 빠른 탐색을 보이는 해쉬 테이블 3

key > 사번, 나이..

배열을 하면 문제가 있다. 전산실 직원이 0에서 99까지만 한다면 문제가 될 것이다. 기업마다 인원수가 다를 것이기 때문에 메모리를 적절하게 이요하지 못 하는 문제점이 생긴다. 

키를 유호하게 만들어 주는 것을 해쉬값이라고 한다. 주솟값으로 활용을 한다. 유효값을 가지고 해쉬 값을 만들고 해쉬 알고리즘을 만든다. 모듈러 나누기 연산을 만들고 수행한다. 길이가 얼마가 되든 empNum%100 하면 0에서 99가 만들어 질 것이다. 키가 매칭이 된다. 

collision 해쉬 값의 충돌문제!!

#13-1. 빠른 탐색을 보이는 해쉬 테이블 4

#13-1. 빠른 탐색을 보이는 해쉬 테이블 5

MAP, TABLE 이라는 자료구조가 있다. 내부적으로 등록되어 있는 HASH FUNCTION 등 사용을 하게 된다. 

저장하는 데이터에 따라 달라진다. 일반화 시켜서 보편적인 HASH FUNCTION을 등록한다.

좋은 해쉬 함수의 조건 ? 저장하는 데이터의 특성에 따라 달라진다.

몰려져 있는 해쉬함수가 좋지 않다. 가급적 전체적으로 슬롯 사용상태가 분산되어 있어야 한다. 

키 전체를 참조하여 해쉬 값을 만들어 낸다.

1 2 3 4 5 6

2 7 | 3 4 | 1 9 

#13-2. 충돌(Collision) 문제의 해결책 1

선형 조사법(Linear Probing)

클러스터 현상(특정 영역에 데이터가 몰리는 형상)이 발생한다. 좋지 않은 방법이다.

오른쪽 오른쪽 으로 가서 빈 자리를 찾아가는 과정이다. 

선형조사법보다 개선 된..

2차조사법..

제곱을 한다. 이차 조사법에서의 빈자리 찾는 과정, 선형 조사법보다 멀리서 빈자리를 찾는다.

슬롯이 DELETED 상태 유효한 데이터가 있었고 해쉬 값이 2인 데이터 오른쪽 오른쪽 존재하고 있다고 알리는 상태이다.

슬롯의 딜리티드 상태 오른쪽을 검사하는 상태가 되는 것이다. 

이중 해쉬를 사용한다.

#13-2. 충돌(Collision) 문제의 해결책 2

이중해쉬를 사용하여 문제를 해결한다. 

위치

c를 소수로 결정하는 이유 : 클러스터 현상을 낮춘다는 통계를 근거로!!

건너 뛸 수 있다. 

#13-2. 충돌(Collision) 문제의 해결책 3

체이닝

지금은 닫힌 어드레싱 모델이다. 충돌난 곳 허용하지 않겠다. 

해쉬 값을 묶는데에 연결 리스트를 사용한다. 연결을 시켰다. 체이닝을 뛰었다. 

#13-2. 충돌(Collision) 문제의 해결책 4

각 해시의 모임은 배열로 선언이 된다. 

key는 한 개, 해쉬 값은 여러 개