해시(Hash)

배열의 경우, 인덱스나 주소값을 통해서 한번에 해당값에 접근할수있다.

대신에 길이가 가변적이지 못하다.

링크드리스트의 경우, 길이가 고정되지 않는 대신 원하는 값을 찾기 위해 각 노드를 일일이 순회해야 한다. 최악의 경우 O(n)

해시 테이블(hash table)

: 키 값의 연산에 의해 직접 접근이 가능한 구조

: 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁금의 탐색 알고리즘

-> 탐색 성능이 향상됐지만 공간은 희생함

해싱(hashing)

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

: 자료를 검색할 때, 탐색이나 첨자가 아닌 내용에 의해 필요한 자료에 도달하는 기법

자료를 찾아주는 함수를 해싱함수라고 한다.

서로 다른 자료가 해싱 함수에 의해 같은 값을 생성하는 경우 충돌(Collision)이라고 한다.

탐색시간이 O(1)에 가깝다.

해싱함수(Hashing Function)

: 어떤 키 K에 대한 테이블의 주소를 계산하기 위한 방법

-> 주어진 키 값으로부터 원하는 자료가 저장되어 있는 주소를 산출해낼 수 있는 공식

- 충돌(Collision) : 해싱 함수 H(K)에 대해서 , H(K1) = H(K2)인 경우

    -> 즉 다른 자료가 같은 주소를 만들어 내는 경우

- 동의어(synonym) :  H(K1) = H(K2)인 경우, K1과 K2는 동의어이다.

 => 즉, 같은 주소를 만들어 내는 둘 이상의 자료

- 버킷(Bucket) : 하나의 주소를 갖는 한 구역

- 슬롯(Slot) : 하나의 레코드를 저장할수 있는 공간

- 오버플로(Overflow) : 한 홈 주소의 버킷 내에 더 이상의 레코드를 저장할 슬롯이 없는 상태

해싱 함수의 종류

1. 나눗셈 법

: 자료를 테이블의 크기로 나누고, 그 나머지를 테이블의 주소로 사용한다.

-> 주소 = 자료값 % 테이블의 크기

-> 테이블의 크기는 소수로 정하는 것이 좋다.

2. 자릿수 접기(접기법)

: 숫자의 각 자릿수를 더해 해시 값(주소)을 만든다.

->문자열을 키로 사용하는 해시 테이블의 경우 잘 어울림

ex) HELLO => 72(H) + 101(E) + 108(I) + 108(I) + 111(O) = 500

충돌 해결 방법

1. 체이닝(Chaning)

: 해시 테이블에 링크드리스트를 삽입하여 충돌이 일어난 자료를 저장

2. 개방 주소법(Open addressing)

(1) 선형 탐사 (Linear Probing)

: 충돌 발생 시, 정해진 칸수 다음에 저장

(2) 제곱 탐사(Quadratic Probing)

: 선형 탐사에서 정해진 칸 수가 제곱수로 늘어남

(3) 이중 해싱(Double Hashing)

: 2개의 해시함수를 사용, 하나는 최초의 주소를 얻기 위해 또 하나는 충돌시 탐사 이동폭을 얻기 위해

(4) 재해싱(Rehashing)

: 해시 테이블을 늘리고 늘어난 해시 테이블의 크기에 맞춰 자료를 다시 배열

◎ 체이닝(Chaining)의 장점 
 

 → 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.

 → 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다. 

 

◎ 개방주소법(Open Addressing)의 장점

 

 → 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.

 

 → 삽입,삭제시 오버헤드가 적다.

 → 저장할 데이터가 적을 때 더 유리하다.