해시 테이블

해시테이블

 

 

 

#해시 : 키값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근

#해시테이블 : 값의 연산에 의해 직접 접근이 가능한 구조

#해싱: 해시테이블을 이용한 탐색

#해시의 용도: 해시테이블, 암호화, 데이터 축약

#해시함수

- 나눗셈법 : 주소=입력값%테이블크기(h(k) = k mod M)

- 자릿수 접기

 

 

해시충돌  해결기법

 

#해시충돌: 해시 함수가 서로 다른 입력값에 대해 동일한 해시 테이블 주소를 반환하는 현상

#개방주소법(Open Addressing) : 오버플로우 발생시 다른 데이터 주소로 다시 해시시키는 방법(반복 수행)

#폐쇄주소법(Closed addressing) : 같은 데이터 주소내에서 끝까지 해결하는 방법 >> 체인법

 

체이닝

#정의: 오버플로우 발생시 링크드 리스트로 해결

#특징: 해시테이블은 링크드 리스트에 대한 포인터 관리

 

 

 

개방주소법

#정의: 충돌 발생시 다른 주소를 사용할 수 있도록 허용하는 충돌해결 알고리즘

1. 선형탐사(Linear Porbing): 충돌시 현재 주소에서 고정폭으로 다음 주소 이동

2. 제곱탐사(Quadratic Probing) : 충돌시 이동폭이 제곱수로 이동

# 제곱탐사의 한계(2차 클러스터) : 같은 해시 값을 갖는 데이터에 대해서는 2차 클러스터 형성 문제

     >> 클러스터를 제대로 방지할 수 있는 방법은 탐사할 주소의 규칙성을 없애는 것

3. 이중해싱(Double Hashing) : 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을때 사용하고 다른 하나는 충돌이 일어났을때 탐사 이동폭을 얻기 위해 사용

#재해싱: 해시테이블의 크기를 늘리고, 늘어난 해시테이블의 크기에 맞추어 테이블내의 모든 데이터를 다시 해싱