해시 테이블

해시 테이블

자료구조 중에서 자료구조 그 자체 외에도 해시 함수라는 추가적인 논리구조를 가지는 첫 번째 자료구조다. hash maps, maps, dictionaries, associative arrays(연관배열)이라는 이름으로도 알려져 있다.

• 속도가 빠르다.
• 개발하면서 해시 테이블을 직접 구현할 일은 많지 않다. (대부분의 언어에선 이미 구현되어 있다)
• key와 value값을 가진다. 키에 대해 값을 할당한다.

### 예시
>>> book = dic()
book["apple"] = 0.34
book["milk"] = 1.49
book["avocado"] = 1.49
print book

{'avocado' : 1.49, 'apple' : 0.34, 'milk': 1.49}

특징

• 해시 테이블은 해시 함수와 배열을 결합해서 만든다.
• 정말 빠른 탐색, 삽입, 삭제 속도를 가진다.
• 값 조회. 어떤 것과 다른 것 사이의 관계를 모형화할 수 있다.
• 중복 항목 방지
• 해시 테이블을 캐시로 사용
  • 더 빠르면서도 서버의 부담을 줄일 수 있다. 작업 속도를 올리는 일반적인 방법이다.

해시 함수

문자열을 받아서 숫자를 반환하는 함수. 값이 저장된 위치를 정확하게 알려준다.
즉, 탐색을 할 필요가 전혀 없다.

특징

• 함수에 일관성이 있어야 한다.
• 다른 단어가 들어가면 다른 숫자가 나와야 한다.
• 서로 다른 단어에 대해 모두 서로 다른 숫자가 나와야 한다.
• 같은 이름에 대해서 항상 같은 인덱스를 할당한다.
• 해당 인덱스에 저장된 값을 즉시 가져온다.
• 해시 함수는 배열이 얼마나 큰지 알고 있어야 하며, 유효한 인덱스만 반환해야 한다.

충돌 (collision)

두 개의 키가 같은 공간에 할당되는 것. 해시 테이블의 성능을 이해하려면 충돌에 대해 이해할 필요가 있다.

해결방안

• 같은 공간에 여러개의 키를 연결 리스트로 만들어 넣는다. 그러나 연결 리스트가 길어질수록 느려지면서 해시 테이블의 장점이 사라진다. 이상적으로는 키를 해시 테이블 전체에 고르게 할당해야 한다.
• 좋은 함수는 충돌을 최소화 한다.

성능

평균적인 경우 해시 테이블은 테이블의 크기에 상관없이 모든 항목에 대해 O(1)시간이 걸린다. 탐색시엔 배열만큼 빠르고, 삽입 삭제 시에는 연결 리스트만큼 빠르다.

• 단순 탐색 - 선형 시간
• 이진 탐색 - 로그 시간
• 해시 테이블 - 상수 시간

그러나 최악의 경우 모든 항목에 대해 O(n)의 시간, 즉 선형 시간이 걸린다.

최악의 경우 & 충돌을 피하기 위한 조건

• 낮은 사용률(load factor)
  • 사용률 : 해시 테이블에 빈 공간이 얼마나 남아 있는가 측정
  • 사용률이 커지기 시작하면 해시 테이블의 공간을 추가해야한다. 이를 리사이징resizing이라고 한다.
  • 사용률이 낮을 수록 충돌이 적게 일어나고, 해시 테이블의 성능도 좋아진다.
  • 보통은 사용률이 0.7보다 커지면 리사이징 한다.
  • 리사이징은 cost가 많은 작업이기 때문에 자주 하는것은 좋지 않다. 하지만 해시 테이블은 리사이징을 해도 평균적으로 O(1)시간이 걸린다.
• 좋은 해시 함수
  • 좋은 함수란 배열에 값을 고루 분포시키는 함수이다.

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘