[자바로 구현하고 배우는 자료구조] 3. 해시(Hash) (1)

3. 해시(Hash)

3-1. 해시 소개

 연결리스트는 연결리스트 내부의 요소를 확인할 때 모든 요소를 확인해야한다. 그래서 find()와 contain()메소드를 사용할 때 시간 복잡도가 O(n)이었다. 만약 n에 무한대를 대입한다면 그 시간 복잡도도 무한대가 되는 것이다. 이런 단점을 보완하기 위해 등장한 것이 해시(Hash)이다. 해시는 키와 값을 가져 어떤 요소를 찾을 때 키를 찾으면 된다. 아래 예시에서 학생의 성적을 알기 위해서는 학생의 아이디(키)를 알면 성적(값)을 쉽게 찾을 수 있다.

 해시는 크기를 확인하거나 비어있는지, 꽉 찼는지 확인할 때 상수값 1의 시간 복잡도를 갖는다. 물론 전체 요소나 키, 값을 확인하는 allEntires(), allKesys(), allValues() 메소드를 사용할 때는 θ(n)의 시간 복잡도를 갖는다. add, remove, lookup, change 메소드는 앞으로 수업을 진행하며 확인해봐야 한다. 

 

3-2. 해시 함수

 해시함수를 작성할 때 주의사항은 다음과 같다.

(1) 데이터의 속성 (Property of the data) : 해시함수는 정수형으로 반납해야한다. 위 그림의 학생 아이디의 경우 CSSC10에서 CSSC는 없애야 한다.

(2) 계산이 빨라야 한다(be fast to compute)

(3) 두 개체가 같다면 같은 값을 반환해야한다(If two things are 'equal', should return the same value)

(4) 하나의 코드를 실행하면 항상 같은 값을 반환해야 한다(Always return the same value during one run of the code).

(5) 따로 실행하면 하나의 개체에 다른 값이 반환될 수 있다(Possible to return different values for an object in seperate runs)

(6) 충돌을 최소화한다(minimize collisions).

 

3-3. 해시 충돌

 해시함수를 이용해 키로 전화번호를 입력하고, '맥주 같이 마시는 친구'로 데이터를 입력하려고 한다. '619-555-1212'는 너무 길어 '-'를 기준으로 나눠 세 값을 더했다. 이를 폴딩(Folding)이라 한다. 그리고 다음 번호를 입력하려고 보니 '619-550-1217'이다. 전화번호는 다르지만 폴딩 후 보니 2386으로 값이 같다. 이 경우 키 값이 같은 게 존재하므로 충돌이 발생한 것이다.

 

3-4. 해시 함수에서 문자열

'my name is Rob' 이라는 문자열에 해시함수를 이용하고자 한다. 그 전에 문자열을 정수로 출력할 수 있을까? 아래 코드를 실행하면 c는 'e', i는 101을 반환한다. 아스키코드 혹은 유니코드를 이용하면 문자열도 정수로 반환할 수 있다.

String s = "my name is Rob";
char c = s.charAt(6);
System.out.println(c);
int i = s.charAt(6);
System.out.println(i);

이를 이용해서 문자열도 해시함수를 이용할 수 있다. 하지만 'this'와 'hits'을 저장하려고 하면 충돌이 발생한다. 왜냐하면 두 키에 쓰인 알파벳이 모두 같기때문이다. 따라서 문자열은 순서에 값을 곱해 this와 hits을 다른 키로 저장할 수 있다.

public int hashCode(String s){
	int g = 31;
    int hash = 0;
    for(int i = 0 ; i<s.length-1 ; i++){
    	hash += Math.pow(g, i) * s.charAt(i);
    }
    return hash;
}

 강의의 댓글 내용에도 틀린 부분에 대한 정정이 올라왔는데 나도 그 부분을 반영하느라 코드가 강의 내용과 다르다. 강의에는 가장 큰 자리에 g^0을 곱하고 1의 자리에 가까워질 수록 g^(s의 길이-1)를 곱했는데 나는 반대로 1의 자리에 가장 g^0, 가장 큰 자리에 g^(s의 길이 -1)를 곱해줬다. 그리고 hash = 으로 두면 결국 가장 마지막 값만 hash에 대입되는 것 같아 +=로 바꿨다. 틀릴 수 도 있다. 아무도 오지 않는 블로그이지만 혹시나 틀린걸 발견하시는 분은 댓글 달아주세요. 

 

3-5. 해시 크기 최적화

충돌을 피하기 위해 해시 크기는 다음의 조건을 갖춰야 한다. 

(1) 테이블의 크기는 홀수여야 한다(odd sized table).

(2) 테이블의 크기는 소수로 설정한다(table size is a prime number).