[자료구조] Hash Table -1

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

해시테이블

• 이진탐색트리의 성능을 개선한 ACL 트리의 삽입과 삭제 연산의 수행시간은 각각 O(logN)
  

• 그보다 더 효율적인 연산을 위해, 키와 1차원 배열의 인덱스의 관계를 이용하여 키(항목)를 저장한다
  
  

• 키를 배열의 인덱스로 사용하면 메모리 낭비가 심해질 수 있음
  
• 문제해결을 위해 키를 변환하여 배열의 인덱스로 사용
  
• 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 해싱이라고 함
  
• 해싱에 사용되는 함수를 해시함수(Hash Function)라고 함
  
• 해시 함수가 계산한 값을 해시 값(Hash value) 또는 해시 주소라고 함
  

• 항목이 해시값에 따라 저장되는 배열을 해시 테이블(Hash Table)이라고 함
  
  

• 아무리 우수한 해시함수를 사용하더라도 2개 이상의 항목을 해시테이블의 동일한 원소에 저장하여야 하는 경우가 발생
  
• 서로 다른 키들이 동일한 해시값을 가질 때 충돌(Collision) 발생
  
  

해시함수

• 가장 이상적인 해시함수는 키들을 균등하게 해시테이블의 인덱스로 변환하는 함수
  
• 일반적으로 키들은 부여된 의미나 특성을 가지므로 키의 가장 앞 부분 또는 뒤의 몇 자리 등을 취하여 해시값으로 사용하는 방식의 해시함수는 많은 충돌을 야기시킴
  
• 균등하게 변환한다는 것은 키들을 해시테이블에 랜덤하게 흩어지도록 저장하는 것을 뜻함
  
• 해시함수는 키들을 균등하게 해시테이블의 인덱스로 변환하기 위해 의미가 부여되어 있는 키를 간단한 계산을 통해 ‘뒤죽박죽’ 만든 후 해시 테이블의 크기에 맞도록 해시값을 계산
  
• 하지만 아무리 균등한 결과가 보장하는 해시함수이더라도 함수 계산 자체에 긴 시간이 소요된다면 해싱의 장점인 연산의 신속성을 상실하므로 그 가치를 잃음
  
  

대표적인 해시함수

1. 중간제곱(Mid-square) : 키를 제곱한 후, 적절한 크기의 중간부분을 해시값으로 사용
   
   

2. 접기(Folding) 함수 : 큰 자릿수를 갖는 십진수를 키로 사용하는 경우. 몇 자리씩 끊어서 만든 숫자들의 합을 이용해 해시값을 만든다
   
   • 예를들어, 123456789012에대해서 1234+5678+9012 = 15924를 계산한 후에 해시테이블의 크기가 3이라면 15924에서 3자리 수만을 해시값으로 사용
     
     
3. 곱셉(Multiplicative 함수) : 1보다 작은 실수 w를 키에 곱하여 얻은 숫자의 소수 부분을 테이블 크기 M과 곱한다. 이렇게 나온 값의 정수부분을 해시값으로 사용
   
   • 예를들면, 테이블크기 M = 127이고 키가 123456789인경우, 123456789 * 0.61803 = 76299999.30567, 0.30567*127 = 38.82009 이므로 38을 해시값으로 이용
     
   • h(key) = (int)(key*w)%1 * M이다
     
     
4. 해시함수들의 공통점
   
   • 키의 모든 자리 숫자들이 함수 계산에 참여함으로써, 계산 결과에서는 원래의 키에 부여된 의미나 특성을 찾아볼 수 없게 된다는 점
     
   • 계산 결과에서 해시테이블의 크기에 따라 특정부분만을 해시값으로 활용한다는 점
     
     
5. 나눗셈(Division) 함수
   
   • 가장 널리 사용됨
     
   • 키를 소수 M으로 나눈 뒤, 그 나머지를 해시값으로 사용
     
   • h(key) = key % M이고, 따라서 해시테이블의 인덱스는 0에서 M-1이 됨
     
   • 여기서 제수로 소수를 사용하는 이유는 나눗셈 연산을 했을 때, 소수가 키들을 균등하게 인덱스로 변환시키는 성질을 갖기 때문
     
     

자바의 hashCode()

• 자바의 모든 클래스는 32비트 int를 리턴하는 hashCode()를 포함하고 있고, hashCode()는 객체를 int로 변환하는 메소드
  
• 자바의 hashCode()는 이론적으로 어떤 종류의 객체(사용자가 정의한 객체를 포함)라도 해싱을 할 수 있도록 지원
  
• hashCode()는 key1.equals(key2)가 true면, key1.hashCode() == key2.hashCode()가 성립한다는 조건 하에 구현되어 있음
  
• 2개의 키가 동일하면 각각의 hashCode 값도 같아야 함
  
  

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/C6wua2t6MV0