해싱과 해시함수(hash function)

해싱이란?

자료구조를 공부하다 보면 보이는 HashMap Hashset 같은 것들이 있습니다. 여기서 Hash는 무엇이고 왜 이렇게 많이 쓰는 걸까요? 우선 해시는 데이터를 다루는 기술 중 하나입니다. 법원같이 여러 자료들을 정리해놔야 하는 곳은 그냥 어떤 규칙도 없이 마구잡이로 정리를 해놨을까요? 사건번호 같은걸 부여해 규칙에 맞게 정리했을 거라고 예상할 수 있습니다. 해싱이란 해시함수를 이용하여 데이터를 저장하고 검색하는 기법을 말합니다. 해시함수는 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수로 데이터가 저장되어 있는 곳을 알려주기 때문에 많은 데이터 중에서도 원하는 데이터의 위치를 빠르게 찾을 수 있어서 자주 이용됩니다. 여기서 만들어진 값을 저장하고 접근할 수 있는 구조로 있는 곳을 해시 테이블이라고 한다. 해시 테이블에서도 한 개의 데이터를 저장할 수 있는 공간을 슬롯이라고 한다.

 

 위에 사진처럼 해시함수가 앞에 2자리를 통해 테이블에 나눈다면 어떤 일이 벌어질까..? 만약 99년생의 주민번호가 추가가 된다면..? 충돌이 일어날 것이다 이미 99에는 값이 하나 들어가 있기 때문이다

이걸 우리는 해시 충돌이라고 하며 해결하는 방법에는 여러 가지가 있지만 대표적인 두 가지 방법을 알아보겠다.

 

1. 체이닝(Chaning)

버킷 내부를 LinkedList로 하여 데이터를 삽입하다 충돌이 발생하면 연결 리스트로 데이터를 연결하는 방식이다. 즉 버킷에서 데이터가 노드가되어 연결리스트로 연결되는 형태를 말한다.

 

2. 개방 주소법(Open Addressing)

체이닝의경우 버켓이 꽉 차더라도 연결 리스트로 계속 늘려가게 되면 O(1)의 시간 복잡도에서 점점 늘어나게 된다. 개방 주소법은 데이터를 연결하는 방식이 아닌 새로운 버켓을 만들어 삽입하는 방식을 말한다.