Hash

https://swexpertacademy.com/main/code/referenceCode/referenceCodeDetail.do?referenceId=HASH&category=undefined 

SW Expert Academy

값 2개를 같이 저장해야 하기 때문에 Hash라는 클래스를 따로 만들어준 후에 Hash 클래스를 요소로 갖는 배열을 만들어서 사용할 hashtable을 초기화해줘야 함.

1. Hash 클래스 선언

2. Hashtable 초기화 메서드

3. hashCode의 역할을 할 hash 메서드

4. key값으로 data를 찾는 메서드

5. key, data 저장하는 메서드

 

package DataStructure;

import java.util.Scanner;

class Hashtable{
	class Hash{
		String key;
		String data;
	}
	//Hashtable 크기
	int capacity;
	Hash table[];
	
	//Hashtable 초기화
	public Hashtable(int capacity) {
		this.capacity = capacity;
		table = new Hash[capacity];
		for(int i = 0; i < capacity; i++) {
			table[i] = new Hash();
		}
	}
	
	//hashCode메소드의 역할. private 선언
	private int hash(String str) {
		int hash = 5381;
		
		for(int i = 0; i < str.length(); i++) {
			int c = (int)str.charAt(i);
			//<<는 비트시프트 연산자
			hash = ((hash << 5) + hash) + c;
		}
		if(hash < 0)
			hash *= -1;
		//범위 내의 공간에 저장해야 하기 때문에 크기로 나눈 나머지를 리턴해줌
		return hash % capacity;
	}
	//key값으로 데이터 찾기
	public String find(String key) {
		int h = hash(key); //해당 키가 가리키는 주소값
		//테이블의 크기값 변수 저장
		int cnt = capacity;
		//저장소를 끝까지 살펴봄. 저장돼있는 data가 있는 key값만 확인하기. 
		while(table[h].key != null && (--cnt) != 0) {
			//같은 key == 같은 데이터
			if(table[h].key.equals(key))
				return table[h].data;
			//다음인덱스로 바꿔줌. hashing한 값이기 때문에 capacity로 나눈 나머지값을 사용해줘야 함.
			h = (h + 1) % capacity;
		}
		return null;
	}
	//데이터 추가
	boolean add(String key, String data) {
		//주소값 생성
		int h = hash(key);
		//같은 주소값에 데이터가 있을 때
		while(table[h].key != null) {
			//같은 key 값이면 추가할 수 없음
			if(table[h].key.equals(key))
				return false;
		}
		
		table[h].key = key;
		table[h].data = data;
		return true;
	}
}

public class DS_Hash {
	final static int MAX_TABLE = 4096;
	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		for(int t = 1; t <= T; t++) {
			Hashtable hashtable = new Hashtable(MAX_TABLE);
			
			int N = sc.nextInt();
			for(int i = 0; i < N; i++) {
				String key = sc.next();
				String data = sc.next();
				hashtable.add(key,  data);
			}
			System.out.printf("#%d\n", t);
			
			int Q = sc.nextInt();
			for(int i = 0; i < Q; i++) {
				String key = sc.next();
				String data = hashtable.find(key);
				if(data != null)
					System.out.printf("%s\n", data);
				else
					System.out.printf("not find\n");
			}
		}
		sc.close();
	}

}