HashTable

이 글은 책 알고리즘 도감에서 HashTable 부분을 정리한 글입니다.

 

HashTable

HashTable

HashTable은 Key와 Value가 한 쌍을 이뤄서 Data를 저장하는 자료구조입니다.

일반적으로 Key는 Data 식별자이며, Value는 Data의 내용입니다.

Hash 함수와 함께 Data 검색을 효율적으로 사용되는 구조입니다.

HashTable은 내부적으로 배열을 사용하여 Data를 저장합니다.

Key값에 대한 Hash 함수를 적용해서 Index 값을 생성합니다.

생성한 Index에 해당 Key에 대한 Value값을 배열에 저장합니다.

Hash 함수

Hash 함수는 주어진 Data를 고정 길이의 불규칙한 숫자로 변환하는 함수이다.

불규칙한 숫자는 Data를 요약한 것으로 Hash 값이라 한다.

Hash 함수는 아래와 같은 특징이 있다.

• 어떤 Data가 주어져도 Hash 값의 길이는 일정하다
  • ex) abc -> 7f0579bc2d, abcdefghi -> 4f07fa9e12, 10자로 동일
• 같은 Data면 언제 Hash 함수를 사용해도 같은 Hash 값이 나온다.
• Data가 1bit라도 다른 값이면 Hash 값은 다르다.
• 다른 Data라도 낮은 확률로 같은 Hash 값이 나올 수 있다 -> Hash값 충돌

Hash 알고리즘에는 대표적으로 MD5, SHA-1, SHA-2 등이 있습니다.

현재는 SHA-2를 이용하는 것이 일반적이며 MD5, SHA-1는 안정성의 문제로 사용을 권장하지 않고 있다.

Hash 충돌

HashTable에서 Hash 충돌이 일어나면 하나의 index 공간에 복수의 Data가 들어온다.

이런 경우는 List 구조로 처음 들어간 Data에 연결(chaining)을 합니다.

그래서 HashTable의 배열의 크기가 너무 작으면 Hash 충돌이 많아져 선형탐색 빈도가 높아진다.

반대로 배열의 크기가 너무 크면 빈 공간이 생겨 Memory를 낭비하게 된다.