🗄️ 해시(Hash)

해시(Hash)는 데이터를 효율적으로 검색하기 위한 자료구조 중 하나입니다.

해시는 데이터를 저장할 위치를 계산하는 데 사용하는 해시 함수와, 계산된 위치에 데이터를 저장하는 데 사용하는 배열로 이루어져 있습니다. 이렇게 함으로써 데이터를 빠르게 검색할 수 있습니다.

해시의 장점

특징	설명
빠른 검색 속도	해시 함수를 이용하여 데이터가 저장될 위치를 빠르게 계산하므로, 데이터를 빠르게 검색할 수 있다.
키-값 쌍으로 데이터 저장	해시 자료구조는 키(key)와 값(value)으로 이루어진 쌍으로 데이터를 저장한다.
공간 효율적	해시 함수를 통해 저장될 위치를 계산하므로, 미리 공간을 할당할 필요가 없다. 필요한 만큼의 공간만 사용하면 된다.

해시의 단점

특징	설명
키의 순서가 중요하지 않음	해시 자료구조는 키-값 쌍으로 데이터를 저장하는데, 이 때 키의 순서가 중요하지 않다. 따라서 정렬된 결과를 얻을 수 없다.
해시 함수의 성능에 따라 검색 속도가 달라짐	해시 함수의 성능이 좋지 않으면 충돌이 많이 발생하여 검색 속도가 느려질 수 있다.
충돌을 해결하기 위한 추가적인 처리 필요	충돌이 발생하면 해시 함수를 수정하거나, 데이터를 저장하는 방법을 변경하는 등의 추가적인 처리가 필요할 수 있다.

해시 테이블(Hash Table)은 해시 자료구조를 구현한 것으로, 해시 함수를 사용하여 데이터를 저장하고 검색합니다. 해시 함수를 사용하여 데이터를 저장할 배열의 인덱스를 계산하고, 해당 인덱스에 데이터를 저장함으로써 데이터를 빠르게 검색할 수 있습니다. 하지만 충돌 가능성이 있기 때문에, 충돌을 해결하기 위해 다양한 기법을 사용합니다. 예를 들어, 개방 주소법(Open Addressing)과 분리 연결법(Separate Chaining)이 있습니다. 개방 주소법은 충돌이 발생하면 다른 빈 공간을 차지할 때까지 다른 인덱스를 계산하여 저장하는 방식이며, 분리 연결법은 충돌이 발생하면 같은 인덱스에 있는 데이터를 연결 리스트로 관리하는 방식입니다.

해시 충돌 방안

• 분리 연결법(Separate Chaining)
  
  해시 충돌 방안 중 하나인 분리 연결법(Separate Chaining)은 해시 테이블에서 충돌이 발생했을 때, 같은 인덱스에 있는 데이터들을 연결 리스트로 관리하는 방식입니다.
  예를 들어, 해시 테이블의 인덱스 0에 데이터 A와 B가 저장되어 있을 때, 같은 인덱스에 데이터 C가 추가될 경우 충돌이 발생합니다. 이 때, 분리 연결법을 사용한다면, 인덱스 0에 연결 리스트가 생성되고, C가 리스트에 추가됩니다. 이후, 같은 인덱스에 데이터가 추가될 때마다 리스트에 데이터가 추가되며, 검색 시에는 해당 인덱스의 리스트를 탐색하여 원하는 데이터를 찾습니다.
  분리 연결법은 해시 충돌이 발생할 경우, 데이터를 연결 리스트로 관리하기 때문에 충돌이 많이 발생하더라도 검색 속도가 느려지지 않습니다. 하지만, 메모리를 많이 사용하게 될 수 있고, 연결 리스트를 탐색하는 과정에서 검색 속도가 느려질 수 있습니다.
  

• 개방 주소법(Open Addressing)
  
  개방 주소법(Open Addressing)은 해시 테이블에서 충돌이 발생했을 때, 다른 빈 공간을 차지할 때까지 다른 인덱스를 계산하여 저장하는 방식입니다. 예를 들어, 해시 테이블의 인덱스 0에 데이터 A와 B가 저장되어 있을 때, 같은 인덱스에 데이터 C가 추가될 경우 충돌이 발생합니다. 이 때, 개방 주소법을 사용한다면, 인덱스 1, 2, 3, ... 순서로 검색하여 빈 공간을 찾아 C를 저장합니다. 이후, 같은 인덱스에 데이터가 추가될 때마다 다른 빈 공간을 차지하며 저장하며, 검색 시에는 해당 인덱스의 데이터를 순서대로 탐색하여 원하는 데이터를 찾습니다.