[자료구조] Hash

🎯 Hash

---

해시(Hash)는 데이터를 저장하고 검색하기 위한 자료구조 중 하나입니다. 해시는 데이터의 고유한 특정 값(키, Key)을 해시 함수(Hash Function)를 사용하여 계산한 후, 그 결과값을 배열의 인덱스로 사용해 데이터를 저장합니다. 이렇게 저장된 데이터는 O(1)의 시간 복잡도로 검색할 수 있으므로 매우 빠른 검색이 가능합니다.

해시 충돌(Hash Collision)

---

해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리며, 따라서 해시 함수는 해시 충돌이 자주 발생하지 않도록 구성되어야 한다. 암호학적 해시 함수의 경우 해시 함수의 안전성을 깨뜨리는 충돌 공격이 가능할 수 있기 때문에 의도적인 해시 충돌을 만드는 것이 어렵도록 만들어야 한다.

• 비둘기집 원리
  • 비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, '서랍과 양말'로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙이라고 부르기도 하며 구두 상자의 원리라고도 한다.

⭐️ 해시 충돌을 처리하는 방법

1. 분리 연쇄법(Separate Chaining)
   • 해시 충돌이 발생하면 해당 인덱스에 연결 리스트(Linked List)를 만들고, 연결 리스트에 데이터를 추가하는 방식입니다. 이 방법은 각 인덱스마다 연결 리스트를 만들어야 하므로 메모리 공간을 많이 사용하지만, 해시 충돌이 발생해도 데이터를 저장할 수 있어 매우 유용합니다.
2. 개방 주소법(Open Addressing)
   • 해시 충돌이 발생하면 다른 빈 인덱스를 찾아 데이터를 저장하는 방식입니다. 이 방법에는 선형 조사(Linear Probing), 이차원 조사(Quadratic Probing), 더블 해싱(Double Hashing) 등 다양한 방법이 있습니다. 개방 주소법은 해시 테이블의 크기를 작게 유지할 수 있어 메모리 공간을 적게 사용하지만, 해시 충돌이 발생할 경우 더 많은 계산이 필요하므로 처리 속도가 느려질 수 있습니다.

Hash 장단점

---

⭐️ Hash 장점

1. 빠른 검색 속도
   • 해시 함수를 이용하여 데이터를 저장하므로, 검색 시간이 O(1)에 가까워 매우 빠릅니다. 이는 데이터의 크기에 관계 없이 일정한 시간 내에 데이터를 검색할 수 있으므로, 대규모 데이터의 검색에 유용합니다.
2. 고유한 값으로 데이터를 저장
   • 해시 함수를 이용하여 데이터를 저장하면, 고유한 값으로 데이터를 저장할 수 있습니다. 이를 통해 중복 데이터를 제거하거나, 데이터의 유일성을 보장할 수 있습니다.
3. 쉬운 구현
   • 해시 함수를 이용하여 데이터를 저장하면, 코드의 구현이 간단해집니다. 이는 다른 자료구조와 비교했을 때 구현이 쉽고 유지보수가 용이하다는 장점이 있습니다.

💀️ Hash 단점

1. 해시 충돌
   • 해시 충돌이 발생할 경우, 검색 속도가 느려질 수 있습니다. 이를 해결하기 위해 충돌 처리 알고리즘이 필요하며, 이에 따른 추가적인 공간이 필요합니다.
2. 순서가 보장되지 않음
   • 해시 함수를 이용하여 데이터를 저장하면, 데이터의 순서가 보장되지 않습니다. 따라서 정렬된 데이터의 검색에는 적합하지 않습니다.