[자료구조]해시(Hash)

Hashing

데이터를 고정된 크기의 값으로 변환하는 방법.
a → (Hash Function) → 2345
a : 데이터 ,Hash Function : 해시 함수 , 2345 : 해시값

해시 함수

임의의 크기의 데이터를 입력받아 고정 된 크기의 해시값을 반환한다.

이상적인 해시 함수는 입력이 다르면 해시값도 다르게 나오도록 설계되어야 하지만, 해시값이 같아지는 경우가 발생하는데 이런 경우를 해시 충돌 (Hash Collision)이라고 부른다. 충돌을 처리하는 방법으로는 Chaining(체이닝) 이나 Open Addressing(오픈 어드레싱) 방법 등이 활용된다.

• Chaining - 분리연쇄법
  동일한 해시값을 반환받은 데이터가 있는 경우, 기존 데이터와 리스트로 연결한다. 저장할 데이터의 수가 정해져 있지 않더라도 해당 방법을 사용하여 유연하게 대응할 수 있지만 리스트가 과도하게 많아질 경우 검색의 연산 시간이 점점 O(n)에 가까워지기 때문에 기존 해시의 계산 시간인 상수시간 O(1)의 이점을 갖기 어렵다.

• Open Addressing - 개방주소법
  충돌이 발생하면 다음 공간(배열상 위치)를 찾아 저장한다. 다음 공간에서도 충돌하면 그 다음 공간을 찾으며 충돌하지 않을 때까지 다음 공간을 찾는다. 이 공간을 찾는 방법에는 여러가지가 있는데 해시 함수를 여러 개 사용하거나, 단순히 선형 탐사를 사용하기도 한다.

해시 테이블에서 사용하는 배열의 크기가 너무 작으면 충돌이 많이 일어나고, 분리연쇄법이 많아지면서 선형 탐색이 많이 발생하게된다. 반대로 배열의 크기가 너무 크면 저장되지 않은 상자가 많아져 메모리 낭비로 이어지게된다.

해시 테이블

• 해시 함수를 활용하여 만든 데이터 구조로, 데이터를 효율적으로 검색할 수 있다.
• 해시 테이블은 키(Key)와 값(Value)를 하나의 쌍으로 저장하는 데이터 구조이다.

---