해시 함수와 해시 테이블

해시 함수

---

문자열을 받아서 숫자로 반환하는 함수로 문자열에 대해 숫자를 할당(mapping)한다고 함.

 

해시 함수의 요건

1. 일관성이 있어 같은 문자열에 같은 숫자를 할당해야함.
2. 서로 다른 단어에 대해 서로 다른 숫자를 반환해야함.
   1. 서로 다른 단어에 대해 같은 숫자를 반환하면 이를 충돌이라고 하는데, 충돌이 많을 수록 좋은 해시 함수로 보기는 힘들다. 최대한 모두 다른 숫자를 반환하게 하여 충돌을 줄여야 함.

 

 

💡 충돌을 피하기 위한 방법
1.  낮은 사용률
       - 해시테이블의 사용률(사용하고 있는 인덱스/전체 배열 크기)이 낮으면, 충돌이 일어날 가능성이 적다.
2. 좋은 해시 함수
      - 해시 함수를 통해 반환되는 값이 고르게 분포되어 있어야 함.

 

 

해시 테이블 ( hash Table )

---

 

필요 배경

책으로된 사전 처럼 특정 단어에 대한 값을 탐색 할 일이 있을 때, 해당 사전이 정렬되어 있다면 이진 탐색을 통해 O(logN) 그렇지 않다면 첫 페이지부터 확인하여 O(N) 이 소요된다. 하지만 컴퓨터 사전에 검색을 통해 확인하게 되면 그 단어를 넣기만 하면 바로 그 값을 확인할 수 있다 O(1) 시간밖에 소요되지 않는다. 이와 같이 어떤 특정 키를 통해 단 번에 값을 확인할 수 있는 방법을 제공 하기위해 해시테이블이 필요하게 되었다.

 

해시 테이블이란?

• 해시 맵(hash maps), 맵(maps), 딕셔너리(dictionaries), 연관 배열(associative arrays) 이라는 이름으로 알려져있다.
• 해시 테이블은 배열을 통해 구현하는데, 해시 함수를 통해 반환한 수를 인덱스로 하여 해당 위치에 값을 저장한다. 해시 함수의 특성상 특정 키 값에는 항상 같은 인덱스 값이 반환되기 때문에 탐색에 있어서 O(1) 시간을 가질 수 있다.
  • 이 때 사용하는 해시 함수는 배열의 크기를 알고 있어, 유효한 인덱스만을 반환해야 한다.

장점

• 빠른 탐색이 가능하다.
• 중복을 막을 수 있다.
• 캐싱을 할 수 있다.

단점

• 해시 함수에 따라 충돌이 발생했을 때, 선형 시간<O(n)>이 걸릴 수 있다.
  • 해시 함수에 충돌이 발생하면, 해당 인덱스에 LikedList로 각 요소들은 연결한다. 충돌이 많아지면 해당 내용을 탐색하기 위해 O(n) 이 소요될 수 있다.