Java - 해시(hash)(2/2)

◎선형 탐사 / 제곱 탐사

선형 탐사:

데이터를 저장할 위치에 충돌이 발생하면, 비어있는 곳을 발견할 때까지 계속 +1 하여 찾는 것 (OpenHasing의 일종)

제곱 탐사:

데이터를 저장할 위치에 충돌이 발생하면, 비어있는 곳을 발견할 때까지 계속 이동수의 제곱수만큼 하여 찾는 것

(OpenHasing의 일종)

 

코드:

 

public class Main {
    
    public static void main(String[] args) {
        Contact person1 = new Contact("abc","010"); // 이름: abc, 연락처: 010
        Contact person2 = new Contact("akj","011"); // 이름: akj, 연락처: 011
        
        LinearHashTable hashtable = new LinearHashTable(26);
        hashtable.put(person1.getKey(), person1.getValue()); //hashtable에 값 넣기
        hashtable.put(person2.getKey(), person2.getValue()); //해싱함수에서 맨 앞자리 알파벳만 비교하므로 abc와 akj는 충돌한다
        
        System.out.println(hashtable.get("abc"));
        System.out.println(hashtable.get("akj"));
        
        
    }

}
class Contact {
    private String key;        //name
    private String value;     //phone number
    public Contact(String key, String value) {
        this.key = key;
        this.value = value;
    }
    public String getKey() {
        return key;
    }
    public void setKey(String key) {
        this.key = key;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
}


    
class LinearHashTable {
    
    public Contact[] data;; //array of Contact
    
    public LinearHashTable(int size) {
        data = new Contact[26];
    }
 
    int getHashCode(String key) {
        int hashCode = key.charAt(0)-'a'; //맨 앞자리만 비교
        return hashCode;
    }
    
    int convertToIndex(int hashCode) {
        return hashCode % 26;
    }
    
    public void put(String key, String value) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        //int i = 1; //제곱탐사 이동수
        while(this.data[index]!=null){
            index++; // 선형 탐사
            // index  = (index + i*i)%data.length;
            // i++; //제곱탐사
        }
        this.data[index] = new Contact(key,value);
        
        
    }
    
    public String get(String key) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        for(int i = index; i<data.length; i++){
            if(key.equals(this.data[i].getKey())){ //key값이 같지 않으면 index +1 탐색
                return data[i].getValue();
            }
        }
        return null;
    }
}

결과:

010
011

선형 탐사에 비해 제곱 탐사가 collision, cluster(군집화) 문제가 조금 덜하기는 하지만, 주소 이동 방식에 규칙성이 있기 때문에 계속해서 데이터를 넣을수록 문제가 심화된다.

---

◎이중 해싱(double hasing)

두 개의 해시함수를 이용하여 주소 이동 방식에 규칙성을 없앤 OpenHasing 방식이다.

1번 해시함수를 A: A(key) =  key%13;

2번 해시함수를 B: B(key) =  7-key%7;

이라고 하면, 이중 해싱의 index값은

(A(key) + j*B(key)) % data.length (j는 충돌 횟수, j>=0)

이다.

 

ex) key(22,55,35,49)를 크기가 13인 배열에 이중 해싱으로 저장

key	A(key)	B(key)	(A(key) + j*B(key)) % 13
22	9		충돌 x, 9
55	3		충돌 x, 3
35	9	7	충돌 1, j=0, 9	충돌 2, j=1, 3	충돌 x, j=2, 10
49	10	7	충돌 1, j=0, 10	충돌 x, j=1, 4

B의 해시값과 해시 테이블의 크기가 서로소 관계일 때 이중 해싱은 가장 좋은 성능을 보인다.

 

코드:

public class Main {
    
    public static void main(String[] args) {
        
        doubleHashTable hashtable = new doubleHashTable(13); //해시테이블 크기 13
        
        //입력되는 key-value값 서로 같다고 가정
        hashtable.put(22,22);
        hashtable.put(55,55);
        hashtable.put(35,35);
        hashtable.put(49,49);
        
        System.out.println(hashtable.get(49));
        System.out.println(hashtable.get(35));
        
        
    }

}

class doubleHashTable {
    
    public int[] data;; //array of int
    
    public doubleHashTable(int size) {
        data = new int[13];
    }
 
    int getHashCodeA(int key) {
        int hashCode = key%13; //1번 해시함수 A
        return hashCode;
    }
    
    int getHashCodeB(int key) {
        int hashCode = 7-key%7; //2번 해시함수 B
        return hashCode;
    }
    
    int convertToIndex(int hashCodeA, int hashCodeB , int j) {
        return (hashCodeA + hashCodeB*j) % 13;
    }
    
    public void put(int key, int value) {
        
        int hashCodeA = getHashCodeA(key);
        int hashCodeB = getHashCodeB(key);
        int j = 0;
        int index = convertToIndex(hashCodeA,hashCodeB,j);
        while(this.data[index]!=0){
            j++; //충돌 횟수 증가
            index = convertToIndex(hashCodeA,hashCodeB,j);
        }
        this.data[index] = value;
        
        
    }
    
    public int get(int key) {
        
        int hashCodeA = getHashCodeA(key);
        int hashCodeB = getHashCodeB(key);
        int j = 0;
        int index = convertToIndex(hashCodeA,hashCodeB,j);
        while(this.data[index]!=key){ //key 같지 않으면 충돌하여 다른 곳에 위치하였다고 판단
            j++; //충돌 횟수 증가
            index = convertToIndex(hashCodeA,hashCodeB,j);
        }
        return this.data[index];
    }
}

결과:

49
35

---

◎뻐꾸기 해싱(Cuckoo hasing)

뻐꾸기는 다른 새의 둥지에 알을 낳는 탁란이라는 행위를 생존전략으로 사용한다. 탁란 된 알은 둥지 주인 새의 알보다 빠르게 부화하고 덩치도 크게 자라, 둥지 주인 새의 새끼들을 다 밀어 죽여버린다. 뻐꾸기 해싱은 이를 모방한 해싱 방법이다.

 

뻐꾸기 해싱은 2개의 해시 테이블을 사용하여 해싱을 구현한다.

h해시함수로 만들어진 해시 코드로 데이터를 저장하는 해시테이블을 htable,

d해시함수로 만들어진 해시코드로 데이터를 저장하는 해시 테이블을 dtable이라고 하면,

 

-뻐꾸기 해싱의 작동원리

1) h해시함수로 만들어진 해시코드 i 생성 (h(key)=i)

2) htable[i]에 데이터(key) 저장

3) htable[i]가 비어있으면: 삽입 종료

htable[i]가 비어있지 않으면, htable[i]에 원래 저장되어있던 key를 내쫓고 htable[i]에 현재 key 저장

4) 3)에서 내쫓긴 key를 oldkey라고 하자. oldkey가 htable에서 내쫓겼으므로, d해시함수로 만들어진 해시 코드 j를 생성한다. (d(oldkey)=j)

5) dtable[j]가 비어있으면: 삽입 종료

dtable[j]가 비어있지 않으면, dtable[j]에 원래 저장되어있던 key를 내쫓고 dtable[j]에 현재 key(oldkey) 저장

6) 5)에서 내쫓긴 key를 oldoldkey라고 하자. oldoldkey가 dtable에서 내쫓겼으므로, h해시함수로 만들어진 해시 코드 k를 생성한다. (h(oldoldkey)=k)

7) 반복..

 

-뻐꾸기 해싱의 장점

최대 2회의 해시함수 계산(htable이나 dtable에 데이터가 있을 것이므로)으로 테이블 원소를 찾을 수 있다.

즉, 탐색과 삭제를 높은 확률로 O(1) 시간에 수행 가능하다.

 

코드:

public class CuckooHasing {

	private int[] F1;
	private int[] F2;

	CuckooHasing() {
		this.F1 = new int[6]; //크기 6짜리 해시테이블 F1
		this.F2 = new int[6];//크기 6짜리 해시테이블 F2
	}

	public void print() {
		System.out.print("F1: ");
		for(int i : F1) {
			System.out.print(i);
			System.out.print(" ");
		}
		System.out.println("");
		
		System.out.print("F2: ");
		for(int i : F2) {
			System.out.print(i);
			System.out.print(" ");
		}
		System.out.println("");
	}
	
	//데이터 삽입(push)
	public void push(int num) {
		int i = 1;
		int tmp;
		tmp = this.add(num,i);
		
		//해시테이블이 비어있지 않으면, 원래 있던 요소를 밀어내고,  밀려난 요소는 다시 해싱
		while(tmp!=0) {
			i++;
			tmp = this.add(tmp,i);
			if(i>6) {
				System.out.print("재해시가 필요합니다."); 
				//뻐꾸기해싱에서 cycle이 일어날경우 i가 계속해서 증가하므로, i가 일정수 이상 증가하면 cycle이 일어났다고 판단, 재해싱을 한다.
				break;
			}
		}
		
	}
	
	//push메서드에서 어디테이블에 넣어야하는지 결정하고, push메서드에서 호출한 add 메서드에서 데이터를 결정한 테이블에 넣는다.
	private int add(int num, int i) {
		int key;
		int oldnum;
		if (i % 2 == 1) {
			key = F1hashfunction(num);
			if (this.F1[key] == 0) {
				this.F1[key] = num;
				return 0;
			} else {
				oldnum = this.F1[key];
				this.F1[key] = num;
				return oldnum;
			}
		} else {
			key = F2hashfunction(num);
			if (this.F2[key] == 0) {
				this.F2[key] = num;
				return 0;
			} else {
				oldnum = this.F2[key];
				this.F2[key] = num;
				return oldnum;
			}
		}

	}
	
	//F1해시함수
	private int F1hashfunction(int key) { 
		return key % 6;
	}
	
	//F2해시함수
	private int F2hashfunction(int key) {
		return (key / 6) % 6;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int[] keytable = {77,53,44,37,24,55};
		CuckooHasing cuckoo = new CuckooHasing();
		
		for(int i : keytable) {
			cuckoo.push(i);
		}
		
		cuckoo.print();
	}

}

 

 

 

-뻐꾸기 해싱에서 사이클(cycle) 발생

 

뻐꾸기 해싱 cycle 발생 ,출처: https://m.blog.naver.com/beaqon/221300449001

표의 순서대로 10,20,45,32를 해시 테이블 h, d에 넣으면 왼쪽 그림처럼 20과 10이 쫓겨나서 htable에서 dtable로 넘어간다.

이때, 61를 집어넣으면, 

1) 61이 htable에 있는 32를 dtable로 내쫓는다.

2) 32가 dtable로 옮겨가면서 10을 htable로 내쫓는다.

3) 10이 htable로 옮겨가면서 45를 dtable로 내쫓는다.

4) 45가 dtable로 옮겨가면서 20을 htable로 내쫓는다.

5) 20이 htable로 옮겨가면서 61을 dtable로 내쫓는다.

6) 61가 dtable로 옮겨가면서 32를 htable로 내쫓는다.

7) 계속 반복.. 뻐꾸기 해싱이 끝나지 않고 다른 키를 내쫓고 내쫓기를 반복하며 끝나지 않는다.

 

이런 사이클이 일어난 경우 삽입에 실패한 것으로 간주하며 재 해싱을 한다.

 

---

◎재 해싱(rehashing)

재 해싱(rehashing)은 뻐꾸기 해싱(Cuckoo hasing)에서만 특별히 행하는 것이 아니다.

모든 해시 방법론에서 일정한 기준을 두고, 해시 방법론의 효율성을 보장하기 위해 해시 테이블에 일정한 양의 데이터가 적재되면 재 해싱을 한다. 일반적으로는 적재율(Load Factor)(해시 테이블의 크기 대비 키의 개수, 키의 개수가 k 해시 테이블의 크기가 n이면 적재율은 k/n이다. )이라는 개념을 도입하여, 적재율이 0.75를 초과하면 해시 테이블의 크기를 2배 늘리고, 0.25보다 작은경우 해시테이블의 크기를 반으로 줄인다.

 

해시테이블의 크기에 비해 적재된 데이터가 많으면, 충돌이 일어날 확률이 높아지므로 해시테이블의 크기를 키우고,

해시테이블의 크기에 비해 적재된 데이터가 적으면,

 

---

◎동적 해싱(Dynamic Hashing) / 정적 해싱(Static Hasing) /확장 해싱(Extendible Hasing)

--추후 포스팅