📝Hash란?

Hash Function을 통해 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수

Hash -> 다시 굽는다는 의미(해시 브라운의 해시이다.)

📝Hash Table이란?

효율적으로 데이터를 저장하고 빠르게 탐색하기 위한 자료구조로 key, value 형태로 데이터를 입력받아 저장하는 자료구조 이다.

• 등장 배경 - Direct address Table(직접 주소화 테이블)을 사용했을 때 키값을 그대로 데이터의 index값으로 사용했다. 하지만 키값들의 숫자 차이가 크면 데이터 사용이 비효율 적이고, 숫자가 아닌 문자를 사용할 경우 사용이 제한되기 때문에 나온 다른 방법이 "해싱"이다.(키 값을 해시값으로 매핑하는 과정)

• 특징 - 해시함수를 통해 key값을 해시화 시켜 테이블에 index key-value 형태(slot)로 데이터를 저장하는 자료구조를 해시테이블이라 한다. 하지만 해쉬함수의 key값이 다르더라도 해싱한 데이터가 collision(충돌: index 값이 중복되는 경우)이 발생할 수 있기 때문에 크게 2가지 방법 open addressing, seperating chaning을 통해 해결한다. 해시테이블은 기본적으로 데이터 축약을 위해 쓰이지만, 키값과 해시값에 연관이 없다면 보안 기능으로도 사용가능하다. 기본적으로 데이터 검색, 저장, 삭제 시간복잡도는 O(1)이다. 저장공간이 부족해서 collision이 많이 발생하면 시간복잡도는 O(n)까지 느려질 수 있다.
  (모든 h(key)값이 같은경우 O(n))

🔑Collision 해결 방법

Open Addressing

open addressing은 collision 이 발생할 경우 미리 정해놓은 규칙에 따라 비어있는 slot을 찾는다.(probing: 탐사) 이 때 규칙의 종류는 다양하며 각 probing의 시간복잡도는 collision에 따라 결정되며 O(1)~O(n)를 갖는다.

• ex1) Linear Probing -> collsion된 해시값에서 일정 값만큼 건너뛰어 데이터를 저장하는 방식.
• ex2) Quadratic Probing -> 원리는 Linear랑 같으나 Linear는 데이터가 특정 영역에 몰리는 클러스터링 현상이 나타나 평균 탐색시간이 증가할 수 있다. 따문에 이를 방지하기 위해 제곱수 값으로 건너뛰너 데이터를 저장한다.
• ex3) Double Hashing -> Quadratic또한 probing 간격이 일정해 클러스터링이 일어날 수 있으므로 h1, h2 의 두개의 해시함수로 해시값을 도출해 사용하는 방식. h1의 해싱값이 collision이 일어나면 h2를 적용해 해싱을 한다.

Seperating Chain

seperating chaining은 collision 이 발생할 경우 slot에 Linked List, Tree 형태로 노드를 추가해 데이터를 저장하는 방식이다. 삽입의 시간복잡도는 O(1) 조회,삭제는O(n)이다.

💡결론

- 해쉬 테이블은 데이터의 축약과 빠른 탐색을 위해 사용하는 자료구조이며

- Collision에 따라 시간복잡도가 늘어나기 때문에, collision이 최대한 발생하지 않도록 해야 가장 좋은 해쉬 함수를 사용했다고 볼 수 있다.