해쉬(2)

Java 자료구조 해쉬 

public class MyHash {
	
//	해쉬 테이블
//	키(key)에 데이터(value)를 매핑할 수 있는 데이터 구조
//	해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산
//	Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라진다.
//	미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원
	
//	해쉬 함수 (Hash Function) : 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수(키를 넣으면 값을 반환)
//	해쉬 (Hash), 해쉬 값(Hash Value), 또는 해쉬 주소(Hash Address) : 해싱함수를 통해 리턴된 고정된 길이의 값
//	해쉬 함수는 사용자 정의함수이다. 사용자가 원하는 기능으로 만든다.
	
//	해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 
//	슬롯(Slot) : 해쉬 테이블에서 한 개의 데이터를 저장할 수 있는 공간
	
//	해쉬 테이블의 장단점과 주요 용도
//	장점 :
//		1) 데이터 저장/읽기 속도가 빠르다(검색 속도가 빠르다)
//		2) 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
//	단점 :
//		1) 일반적으로 저장공간이 좀 더 많이 필요하다.
//		2) 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
//	주요 용도
//		1) 검색이 많이 필요한 경우
//		2) 저장, 삭제, 읽기가 빈번한 경우
//		3) 캐쉬 구현시(중복 확인이 쉽기 때문)
//		
//	충돌(Collision) 해결 알고리즘(쫗은 해쉬 함수 사용하기):
//		해쉬 테이블의 가장 큰 문제는 충돌의 경우이다. 이 문제를 충돌(Collision) 또는 해쉬 충돌(HashAttributeSet Collision)
//		이라고 부른다.
	
//	충돌 해결 기법
	
//	Chaining 기법
//		개방 해슁 또는 Open Hashing 기법 중 하나 : 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
//		충돌이 일어나면, 링크드 리스트라는 자료구조를 사용해서, 링크드 리스트로 데이터를 추가해서 뒤에 연결시켜서 저장하는 기법
	
//	Linear Probing 기법
//		폐쇄 해슁 또는 Close Hashing 기법 중 하나 : 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
//		충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 
//		-> 저장공간 활용도를 높이기 위한 기법
	
	// hash table 클래스 만들기
	public Slot[] hashTable;
	
	public MyHash(Integer size){
		this.hashTable = new Slot[size];
	}
	public class Slot{
		String value;
		Slot(String value){
			this.value = value;
		}
	}
	
	// 해쉬 함수 만들기
	//Key가 문자열일 때, 문자열의 앞 글자를 숫자로 변환해서, Division 기법을 사용하여 , Key에 대한 주소(인덱스 번호) 계산
	//Division 기법 : 가장 간단한 해쉬 함수 중 하나로 , 나누기를 통해, 나머지 값을 사용하는 기법
	public int hashFunc(String key){
		return (int)(key.charAt(0)) % this.hashTable.length;
	}
	
//	객체 배열
//	객체 베열 선언시 , 각 배열의 아이템은 각 객체를 참조할 수 있는 주소를 담을 수 있는 공간만 할당
//	-각 아이템 생성시, 별도로 각 객체를 생성해줘야 한다.
//	-즉, 객체 배열 선언시, 각 생성할 객체를 가리킬 주소만 저장할 공간을 배열로 만드는 것
	
	//저장 성공유무 반환 및 값을 저장하는 메서드
	public boolean saveData(String key, String value){
		Integer address =this.hashFunc(key);
		if(this.hashTable[address]!= null ){
			this.hashTable[address].value = value;
		}else{
			this.hashTable[address] = new Slot(value);
		}
		return true;
	}
	
	//특정 key에 대한 데이터를 가져오는 메서드
	public String getData(String key){
		Integer address =this.hashFunc(key);
		if(this.hashTable[address] != null){
			return this.hashTable[address].value;
		}else{
			return null;
		}
	}
	
	public static void main(String[] args) {
		//테스트 : 값 저장후 , 출력
		MyHash mainObject = new MyHash(20);
		mainObject.saveData("DaveLee","01022223333");
		mainObject.saveData("fun-coding","01033334444");
		System.out.println(mainObject.getData("fun-coding"));
		System.out.println("##################################");
		
		//기존 알고리즘의 문제점 (앞의 문자가 똑같으면 저장 주소가 똑같아 충돌하게 된다)
		MyHash mainObject1 = new MyHash(20);
		mainObject1.saveData("DaveLee", "01022223333");
		mainObject1.saveData("fun-coding", "01033334444");
		mainObject1.saveData("David", "01044445555");
		mainObject1.saveData("Dave", "01055556666");
		System.out.println(mainObject.getData("David"));
		
		

	}
	
}

충돌을 막기 위해 사용하는 Linear Probing 기법, HashMap 클래스 

//Java HashMap 클래스 
import java.util.HashMap; // 해쉬맵 클래스 import

public class MyHash2 { //Linear Probing 기법
	
//	충돌(Collision) 해결 알고리즘(쫗은 해쉬 함수 사용하기):
//		해쉬 테이블의 가장 큰 문제는 충돌의 경우이다. 이 문제를 충돌(Collision) 또는 해쉬 충돌(HashAttributeSet Collision)
//		이라고 부른다.
	
//	충돌 해결 기법
	
//	Chaining 기법
//		개방 해슁 또는 Open Hashing 기법 중 하나 : 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
//		충돌이 일어나면, 링크드 리스트라는 자료구조를 사용해서, 링크드 리스트로 데이터를 추가해서 뒤에 연결시켜서 저장하는 기법
	
//	Linear Probing 기법
//		폐쇄 해슁 또는 Close Hashing 기법 중 하나 : 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
//		충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법 
//		-> 저장공간 활용도를 높이기 위한 기법
	
	// hash table 클래스 만들기
	public Slot[] hashTable;
	
	public MyHash2(Integer size){
		this.hashTable = new Slot[size];
	}
	  public class Slot {
	        String key;
	        String value;
	        
	        Slot(String key, String value) {
	            this.key = key;
	            this.value = value;
	        }
	    }
	
	// 해쉬 함수 만들기
	//Key가 문자열일 때, 문자열의 앞 글자를 숫자로 변환해서, Division 기법을 사용하여 , Key에 대한 주소(인덱스 번호) 계산
	//Division 기법 : 가장 간단한 해쉬 함수 중 하나로 , 나누기를 통해, 나머지 값을 사용하는 기법
	public int hashFunc(String key){
		return (int)(key.charAt(0)) % this.hashTable.length;
	}
	
//	객체 배열
//	객체 베열 선언시 , 각 배열의 아이템은 각 객체를 참조할 수 있는 주소를 담을 수 있는 공간만 할당
//	-각 아이템 생성시, 별도로 각 객체를 생성해줘야 한다.
//	-즉, 객체 배열 선언시, 각 생성할 객체를 가리킬 주소만 저장할 공간을 배열로 만드는 것
	
	//저장 성공유무 반환 및 값을 저장하는 메서드
	public boolean saveData(String key, String value) {
        Integer address = this.hashFunc(key);
        if (this.hashTable[address] != null) { //저장할 데이터가 이미 있다면 
            if (this.hashTable[address].key == key) { //만약 키가 같다면 
                this.hashTable[address].value = value; //데이터 업데이트 
                return true;
            } else { //키가 존재하지 않으면 
                Integer currAddress = address + 1; //인덱스 +1번 배열 번호를 저장 
                while (this.hashTable[currAddress] != null) { //다음 슬롯에 자리가 있다면 반복문 실행
                    if (this.hashTable[currAddress].key == key) { //만약 다음 슬롯과 키가 같다면 
                        this.hashTable[currAddress].value = value; //데이터 업데이트 
                        return true;
                    } else { //다음 슬롯과 키가 다르다면 
                        currAddress++; //인덱스번호 1 증가 시킨다 .
                        if (currAddress >= this.hashTable.length) { //만약 인덱스 번호가 해쉬테이블의 길이를 넘어가면
                            return false;
                        }                        
                    }
                }
                this.hashTable[currAddress] = new Slot(key, value); //반복문을 빠져나간 후 데이터 삽입 
                return true;
            }
        } else { //저장할 데이터가 중복이 아니라면 
            this.hashTable[address] = new Slot(key, value);
        }
        return true;
    }
	
	//특정 key에 대한 데이터를 가져오는 메서드
	 public String getData(String key) {
	        Integer address = this.hashFunc(key);
	        if (this.hashTable[address] != null) { //슬롯에 데이터가 존재한다면 
	            if (this.hashTable[address].key == key) { //슬롯에 찾는 키와 일치하면 
	                return this.hashTable[address].value; //데이터 반환 
	            } else { //첫번쨰 슬롯과 일치하지 않으면 순회
	                                
	                // 예외 케이스로, 키에 해당하는 주소가 가장 마지막 슬롯일 경우, 
	                // this.hashTable[address + 1] 에 해당하는 배열은 없기 때문에, 
	                // 예외 케이스에서도 동작하도록 currAddress 는 address 만 대입하고 진행
	                Integer currAddress = address; // 수정 
	                while (this.hashTable[currAddress] != null) { //슬롯에 데이터가 존재할때까지 반복
	                    if (this.hashTable[currAddress].key == key) { //찾는 키가 맞다면 
	                        return this.hashTable[currAddress].value; //데이터 반환
	                    } else { //찾는키가 아니라면 
	                        currAddress++; //인덱스 1 증가
	                        if (currAddress >= this.hashTable.length) { //찾는 인덱스가 슬롯의 길이를 넘어가면 
	                            return null;
	                        }
	                    }
	                }
	                return null; //데이터 검색 실패
	            }
	        } else {
	            return null;
	        }
	    }
	 
//	 빈번한 충돌을 개선하는 기법
//	 	해쉬 테이블 저장공간을 확대 및 해쉬 함수 재정의 

//	HashTable의 시간복잡도
//	일반적인 경우(충돌이 없는 경우) O(1)
//	최악의 경우(충돌이 모두 발생하는 경우) O(n)
//	Linear Probing, Chaining 기법 둘 다 동일
//	-해쉬 테이블의 경우는 일반적인 경우를 기대하고 작성한다.
	
	
	public static void main(String[] args) {
		
		//기존 알고리즘의 문제점 해결 
		MyHash2 mainObject1 = new MyHash2(20);
		mainObject1.saveData("DaveLee", "01022223333");
		mainObject1.saveData("fun-coding", "01033334444");
		mainObject1.saveData("David", "01044445555");
		mainObject1.saveData("Dave", "01055556666");
		System.out.println(mainObject1.getData("David"));
		System.out.println("##################################");

		//HashMap 클래스 사용
		HashMap <Integer, String> map = new HashMap<Integer, String>();
		map.put(1, "원숭이");
		map.put(2, "코끼리");
		System.out.println(map.get(2));
		System.out.println("##################################");
		HashMap <String, String> map2 = new HashMap<String, String>();
		map2.put("DavaLee", "01022223333");
		map2.put("fun-coding", "01033334444");
		map2.put("David", "01044445555");
		System.out.println(map2.get("David"));
		
		
	}
	
}

충돌을 막기 위해 사용하는 Chaining 기법

public class MyHash3 { //Chaining 기법
public Slot[] hashTable;
	
	public MyHash3(Integer size){
		this.hashTable = new Slot[size];
	}
	public class Slot{
		String key;
		String value;
		Slot next;
		Slot(String key,String value){
			this.key =key;
			this.value = value;
			this.next = null;
		}
	}
	
	// 해쉬 함수 만들기
	//Key가 문자열일 때, 문자열의 앞 글자를 숫자로 변환해서, Division 기법을 사용하여 , Key에 대한 주소(인덱스 번호) 계산
	//Division 기법 : 가장 간단한 해쉬 함수 중 하나로 , 나누기를 통해, 나머지 값을 사용하는 기법
	public int hashFunc(String key){
		return (int)(key.charAt(0)) % this.hashTable.length;
	}
	

	public boolean saveData(String key, String value){
		Integer address = this.hashFunc(key); //저장할 배열인덱스를 얻어와서 
		if(this.hashTable[address] != null){ // 이미 인덱스에 데이터가 존재한다면 
			Slot findSlot = this.hashTable[address]; //현재 Slot 데이터 저장
			Slot prevSlot = this.hashTable[address]; //이전 Slot 데이터 저장
			while(findSlot != null){ //링크드 리스트 끝까지 순회 , 빠져나가면 슬롯이 모두 다른 데이타를 가지고 있다
				if(findSlot.key == key){ //현재Slot.key 와 저장할 키의 값이 같다면 
					findSlot.value =value; //새로운 value로 업데이트를 한다
					return true;
				}else{ //일치하는 key가 없다면  (순회)
					prevSlot =findSlot;
					findSlot = findSlot.next;
				}
			}
			prevSlot.next = new Slot(key, value); //이미 있던 링크드 리스트와 새로 연결해준다
		}else{
			this.hashTable[address] = new Slot(key, value);
		}
		return true;
	}
	
	//특정 key에 대한 데이터를 가져오는 메서드
	public String getData(String key){
		Integer address =this.hashFunc(key);
		if(this.hashTable[address] != null){
			Slot findSlot = this.hashTable[address];
			while(findSlot != null){
				if(findSlot.key == key){
					return findSlot.value;
				}else{
					findSlot = findSlot.next;
				}
			}
			return null;		
		}else{
			return null;
		}
	}
		
	public static void main(String[] args) {
		MyHash3 mainObject = new MyHash3(20);
		mainObject.saveData("DaveLee", "01022223333");
		mainObject.saveData("fun-coding", "01033334444");
		mainObject.saveData("David", "01044445555");
		mainObject.saveData("Dave", "01055556666");
		System.out.println(mainObject.getData("Dave"));
	}

}