[코드잇-자료구조1 : 기본 자료구조들] 5. 해시 테이블

본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 첫번째 주제인 '기본 자료구조들'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/data-structure-basics?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz

---

1. key - value 데이터

지금까지는 데이터를 순서대로 저장해주는 배열과 링크드 리스트에 대해 배웠음. 하지만 모든 데이터에 순서 관계가 있는 것은 아님

 

key - value : 순서가 아니라 이미 알고 있는 정보를 이용해서 저장한 정보를 검색할 수 있는 데이터 유형

- 호수를 이용해서 입주민을 알아내는 것과 비슷함

 

key - value 쌍

- 즉, 각 호수별로 사는 사람을 바꿀수는 있어도 여러개가 있으면 안됨

2. Direct Access Table

배열을 이용하면 원하는 인덱스에 O(1)으로 접근할 수 있음

인덱스 : 데이터의 순서에 해당하는 정보(0부터 배열의 크기 -1까지의 자연수)

- 인덱스를 순서가 아니라 키라고 생각하면 직관적으로 키-밸류 쌍을 저장할 수 있음

예시를 통한 설명

 

- 가장 큰 호수를 마지막 인덱스로 갖는 배열

- 이 아파트의 가장 큰 호수는 942니까 크기가 943인 배열을 만드는 것

- 그 다음에는 인덱스를 호수라고 생각하고 데이터를 저장

- 인덱스 101에는 최지웅, 711호에는 김현승, ...

 

저장한 키-밸류 데이터를 가지고 오고 싶다면?

- 101호에 누가 사는지 알고싶으면배열의 인덱스 101에 접근하면 된다.

 

즉, 호수를 인덱스로 사용하면 입주민 이름을 항상 O(1)으로 갖고올 수 있음. 직관적이고 효율적이게 저장한 데이터에 접근할 수 있는것

Direct Access Table

Direct Access Table

- 위의 호수 예시처럼 배열 인덱스를 키로 이용해서 데이터를 저장하고, 갖고오는 방식

- 단, 공간을 너무 많이 낭비함

- 키가 될 수 있는 값의 범위가 너무 커지면 낭비하는 공간도 너무 커진다.

3. 해시 테이블 개념

해시 함수

- 아파트 호수 데이터가 있다고 가정. 이 호수를 0부터 100까지의 자연수로 바꿔주는 해시 함수에 넣으면 기존 호수 값이 0부터 100사이의 자연수로 바뀜

- 키가 아무리 커도 상관없음

해시 테이블

해시 테이블

- 해시 함수와 배열을 같이 사용하는 자료구조

- 키를 바로 인덱스로 사용하지 않고 해시 함수에 넣어서 리턴된 값을 인덱스로 사용

 

해시테이블 생성 과정

먼저 원하는 크기의 배열을 만든다. 아래 예시는 크기가 100인 배열을 만듦

 

- '711호 - 김현승' 키-밸류 쌍을 저장하고 싶으면 우선 키인 711을 해시 함수에 넣는다.

- 이때 30이 리턴됐다고 하면, 배열의 인덱스 30에 키,밸류 모두 저장 → 해시테이블에서는 한 인덱스에 키, 밸류 모두 저장

※ Direct Access Table에서는 인덱스가 키 자체였기 때문에 인덱스에 밸류만 저장했음

- 저장한 데이터를 갖고 올 때에도 똑같이 하면됨

- 711호에 사는 입주민의 이름을 알고 싶으면 해시함수에 711을 넣음. 이러면 30이 리턴되며, 배열의 인덱스 30에 접근한다.

- 그리고 저장된 입주자 이름을 갖고온다.

정리 : 해시 테이블 (Hash Table)