해쉬 자료구조에 대해서 알아보자 🤔

해쉬테이블 🤔

• 키에 데이터를 맵핑할 수 있는 데이터구조이다.
  • 키와 값을 어떻게 맵핑할까? → 해쉬 펑션에 키를 넣으면 키를 저장할 수 있는 주소를 리턴을 해준다.(인덱스) 해당 주소에 키에 해당하는 값을 저장한다.
  • 해시 펑션은 뭘까? → 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수이다. (데이터가 어떻든간에 고정된 길의의 값으로 리턴해준다.)
• 해쉬테이블에 저장한다면 어떤 키던간에 해시 펑션을 이용하면 해당 데이터의 위치를 리턴해주기 때문에 빠른 탐색 속도를 보여준다.
• 해쉬테이블 ⇒ 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 슬롯 : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간
• 전체적인 흐름 ? → 키와 데이터를 입력하면 해쉬 펑션은 입력된 키를 바탕으로 인덱스 번호를 반환해 해당 데이터가 저장될 수 있는 공간을 배열로 할당한 후, 키에 따른 데이터를 저장한다.
  • 탐색시에는 키를 입력하면 해쉬 펑션은 인덱스를 리턴해주기 때문에 불필요한 탐색을 할 필요 없이 데이터의 유무를 판단해 해당 인덱스의 데이터로 바로 접근이 가능하다.

해쉬 테이블의 장단점과 주요 용도 🤔

• 장점
  • 데이터 저장/읽기 속도가 빠르다.(처음부터 탐색할 필요 없이 해당 인덱스에 바로 접근이 가능하기 때문에)
  • 해쉬는 키에 대한 데이터가 있는지 확인이 쉽다.(중복 확인이 쉽다.)
• 단점
  • 일반적으로 저장 공간이 좀 더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
• 주요 용도
  • 검색이 많이 필요한경우
  • 저장,삭제,읽기가 빈번한경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문이다.)

해쉬 충돌(컬리젼)을 위한 알고리즘 (키는 다르지만 해쉬 펑션으로 인한 반환값이 같을때) 🤔

체이닝 기법 (순회를 하기 때문에 시간이 좀 걸린다.)

• 개방 해슁 또는 오픈 해슁 기법중 하나이다. (해쉬 테이블 저장공간 외의 공간을 활용하는 기법 /그래서 오픈이라는 개념을 가진다.)
• 충돌이 일어나면 링크드 리스트를 사용해서 데이터를 추가로 뒤에 연결시켜서 저장한다.
• 기존의 슬롯에 키와 연결용 next 객체를 새로 멤버변수로 선언해준다.
• 이미 해당 슬롯이 있다면? 해당 슬롯을 참조하는 prevSlot / findSlot 객체를 생성해 key가 같다면 벨류 값을 바꾸고, 다르다면 순회를 하면서 null을 찾을때까지 포인터를 연결 후 새로 슬롯을 생성해 데이터를 저장한다.

리니어 프로빙 기법

• 폐쇄 해슁 기법중 하나이다. (해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법이다. / 해쉬 테이블 저장공간 안에서 해결을 하기 때문에 폐쇄 라는 용어가 붙는다.)
• 충돌이 일어나면 해당 해쉬 어드래스의 다음 어드래스부터 맨 처음 나오는 빈 공간에 저장하는 기법이다.
  • 저장공간 활용도를 높이기 위한 기법이다.
• 마찬가지로 key를 함께 저장한다.
• 해당 슬롯에 데이터가 존재한다면? 계속 뒤 인덱스로 순회를 하면서 null이 나올때까지 탐색 후 null이 존재하지 않는다면 저장을 하지 않는다.

해쉬 테이블 시간복잡도 🤔

• 일반적인 경우 (컬리젼이 없다면) O(1)
• 최악의 경우 (컬리전이 모두 발생하는 경우) O(n)
• 리니어 프로빙, 체이닝 기법 둘 다 동일하다.

해쉬 테이블의 경우는 일반적인 경우를 기대하고 작성한다.

검색에서 해쉬 테이블의 사용 예

• 배열에 데이털르 저장하고 검색할때는 O(n) 이지만 이상적인 해쉬 테이블 케이스에서 데이터를 검색할때는 O(1)이다. → 배열은 무조건 반복문을 이용하지만 해쉬 테이블은 해쉬펑션이 인덱스를 리턴해주기 때문에 O(1)이다.

마무리 🤔

• 단순히 아무생각없이 사용하던 해쉬맵이 이름과 밸류를 통으로 저장해버리는 줄 알았는데 기본 원리는 키는 해쉬펑션으로 인하여 인덱스를 반환해주면 밸류를 가져오지만, 충돌이 일어날 시에 대비하기 위해서 키도 같이 저장하는구나! 를 알게되었습니다.
• 해쉬 테이블이 어떻게 동작하는지 알 수 있게 되었습니다.
• 단순히 해쉬 테이블 자료구조를 사용하는 API를 이용하는것이 아니라 적절한 사용이 맞는지 판단해 최대한 충돌이 일어나지 않는 상황에서 해쉬 자료구조를 택한다면 좋은 성능을 발휘할 것 같습니다.
• 체이닝 기법, 리니어 프로빙 기법이 해쉬 충돌 해결방안 이긴 하지만 전체적으로 돌아가는 구조를 보니 그냥 충돌 자체가 안나는게 최적의 상황인것 같습니다. 자주 충돌이 날 수 있는 상황이라면 다른 자료구조를 사용하는게.. 🤔
• 적절한 해쉬 펑션을 어떻게 만드는지가 가장 중요한것 같습니다. 해당 부분에 대해서 공부할 필요가 있다고 느껴졌습니다.