해시(Hash)

내가 이해한대로 작성하는 해시 개념

자료구조의 중요성

자료구조를 잘 선택하면 사용되는 메모리를 최소화 할수 있으며 공간적으로 효율성을 확보할 수 있다

해시함수 or 해시 알고리즘

해시 함수 또는 해시 알고리즘은 임의의 데이터(key)를 고정된 길이의 데이터(hash value)로 매핑하는 함수이다

• 해시 함수는 입력 값에 관계 없이 고정된 길이의 해시를 반환한다
• 반환 결과를 토대로 입력값을 유추할 수 없다

(입력된 자료의 길이에 관계없이 해시값의 길이는 일정한걸 볼수있다)

해시 테이블

• 해시 테이블은 key와 hash value를 같이 저장하는 자료구조이다
• 파이썬 에서의 딕셔너리 구조와 유사하다
• 다만 해시테이블 구조는 value에 여러형태를 저장할 수 있다

해시테이블의 장점과 단점

장점

• 해시 테이블은 O(1)의 시간 복잡도를 가지고 있다
• 모든 데이터 타입을 처리할 수 있다
• 키와 해시값 사이에 연관성이 없어서 보안이 좋다
• 중복 제거에 유용하다

단점

• 해시 테이블은 O(n)의 시간 복잡도를 가지고있다
• 해시 충돌이 일어날 수 있다
• 공간 복잡도가 커진다
• 순서가 있는 배열에는 어울리지 않는다
• 해시 함수 의존도가 높아진다

해시 충돌

해시 테이블의 장점은 O(1)의 시간 복잡도를 가지는 것이다
하지만 단점은 O(n)의 시간 복잡도를 가지는 것이다
이 말이 이상해 보인다
O(1)의 시간복잡도는 이상적인 해시테이블의 경우이다
이상적인 해시테이블은 충돌이 일어나지 않는 경우이다
해시테이블은 해시 충돌이 일어나는 단점이 있다
충돌에 대한 알고리즘 처리가 부족하다면 시간복잡도가 O(n) 으로 늘어나는것이다

해시 충돌이란

키A와B를 해시함수로 해시값을 얻었는데 해시값이 같다면 서로 다른 키가 같은 공간에 저장이 되므로 1:1 대응이 되지않는다 해시 충돌은 필연적이다
해시 충돌이 일어나면 인덱스로 한번더 탐색을 진행하기 때문에 성능이 하락한다

해시 충돌의 해결법

1.체이닝(chaining)

체이닝은 저장소(bucket)에서 충돌이 일어나면 기존값과 새로운 값을 연결 리스트로 만드는 방법이다

체이닝의 장점

체이닝은 충돌이 일어나면 그때 공간을 만들어서 연결을 해주기에 충돌을 대비해서 미리 공간을 많이 만들어 놓을 필요가 없다

체이닝의 단점

같은 해시에 자료들이 많이 연결되면 검색시 효율이 떨어진다

2.개방 주소법

• 개방주소법은 충돌이 일어나면 비어있는 해시에 데이터를 저장하는 방법이다
• 개방주소법은 해시와 벨류가 1:1 관계를 유지한다
  

(위의 그림에서 John과 Sandra의 해시가 동일해서 충돌이 일어난다 Sandra는 바로 다음 비어있는 153번에 저장이되고 Ted는 153번이 채워져 있기에 154번에 저장된다)

2-1.선형 탐색

해시값에서 고정폭으로 건너 뛰면서 탐색하다 비어있는 해시를 발견하면 저장하는 방식이다

선형탐색의 장점

• 구조가 간단하고 캐시의 효율이 높다

선형탐색의 단점

• 고정폭이 좁으면 특정 해시값의 주변 버킷이 모두 채워져 있는 군집 문제에 취약하다
• 고정폭이 크면 공간을 많이 확보해둬야 한다

2-2.2중 해시

해시 충돌이 일어나면 다른 해시 함수를 적용한 결과를 해싱 하는방법

2중 해시의 장점

• 군집 문제에 거의 영향을 받지않는다

2중 해시의 단점

• 캐시의 효율이 떨어진다
• 가장 많은 연산량을 요구한다

2-3.2차 검색법

선형탐색의 단점을 보완한 검색법
다음 해시를 검색해 봤을때 채워져 있다면 고정값만큼 내려가면서 탐색

2차 검색법의 특징

• 캐시 효율과 밀집문제 방지 측면에서 선형 검색법과 2중해시의 중간정도의 성능

체이닝과 선형탐색의 비교

• 체이닝 : 복잡한 계산식을 개방주소법에 비해 적게 사용
  해시테이블이 채워질수록 성능 저하가 선형적으로 발생

• 개방주소법 : 포인터가 필요 없고 지정한 메모리 외 추가적인 저장공간도 필요 없다 삽입, 삭제시 오버헤드가 적고, 저장할 데이터가 적을 때 유리

리사이징

새로운 배열에 기존의 배열의 키를 새롭게 재해싱 하는 방법

개방주소법에선 사용되는 고정크기의 배열이 가득차거나 체이닝의 연결 리스트가 길어지면 검색효율이 떨어지기 때문에 버킷의 갯수를 늘려주는 방법

해시에 대해 정리하고 공부 하다 보니 시간복잡도와 공간 복잡도 개념이 있어서 다음은 이에 대해 정리함