array와 hash function을 사용하여 map을 구현한 자료구조이다.

만약에 어떤 사람이 내 채널에 유튜브 동영상을 다운받아서 그 사람 채널에 그대로 올리면 "이 동영상은 중복되는 동영상" 입니다 라는 에러 메세지가 노출된다. 전 세계 유튜브 동영상이 얼마나 많은가? 동영상 파일이 또 엄청 크다. 유튜브는 그 사람이 내 채널에 동영상을 가지고 자기 채널에 업로드 시 그 순간 바로 알려준다. 이걸 어떻게 하는 걸까? 이 방법은 바로 Hash Table 이다.

검색하고자 하는 키 값을 입력 받아서 해시 함수를 돌려 반환 받은 해쉬코드(해쉬주소)를 배열의 인덱스로 환산을 해서 데이터에 접근하는 방식의 자료구조이다. 여기서 사용하는 키 값은 문자열이 될 수도 있고 숫자나 파일 데이터도 될 수 있다. 해쉬 함수는 어떤 특정한 규칙을 이용해서 입력받은 키 값으로 그 키값이 얼마나 큰지의 상관없이 동일한 해쉬코드를 만들어 준다. 암호화폐의 핵심기술인 블록체인에서도 각 사용자들의 공공장부를 비교할 때 해쉬코드를 이용한다. 그럼 이제 해쉬 테이블의 구조를 살펴보자.

Hash Structure

• Hash Table : Key에 Value를 저장하는 Data Structure
  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
• Hash
  • 임의 값을 고정 길이로 변환하는 것(어떠한 데이터도)
  • Hash Function을 통해 나온 값
• Hash Table
  • 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• Hashing Function
  • Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
  • 즉, 임의의 데이터를 정수로 변환하는 함수
• Hash Value == Hash Address
  • Key를 Hashing Function으로 연산해서 해쉬 값을 알아내고, 이를 기반으로 Hash Table에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있는 것을 뜻함
• Slot 또는 Bucket
  • 한 개의 데이터를 저장할 수 있는 공간

*저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

해시테이블의 장점은 검색속도가 굉장히 빠르다. 하지만 해시테이블도 고민이 있다. 해쉬코드를 구하는 알고리즘이 좋지 않으면 한 방에 데이터가 여러개 들어가기 때문에 충돌현상이 일어난다 해서 Collison이 일어난다.

해시테이블은 보통 O(1)의 복잡도를 가지고 있지만 Collison이 많은 경우에는 O(n)까지 걸릴 수 있다.

그래서 해시함수의 입력받은 키를 가지고 얼마나 골고루 잘 분배를 해주냐에 따라 좋은 알고리즘이냐가 결정이 된다. 해쉬함수는 때로 서로 다른 키값으로 동일한 해쉬코드를 만들어 내기도 한다. 그 이유는 키값은 문자열이고

그 가지수가 무한한데, 해시코드는 정수개 밖에 제공을 못하기 떄문에 알고리즘이 아무리 좋아도 어떤 키들은 중복되는 해시코드를 가질 수 밖에 없다. 그리고 때로는 해시 알고리즘이 서로 다른 해시코드를 만들어 냈는데 배열방이 한정되어 있으니까 같은 방에 배정받는 경우도 있다. 이런 경우는 모두 Collsion(충돌)이라고 한다.