[자료구조&알고리즘] 해시, 해시법(체인법, 오픈주소법)

728x90

1. 해시

데이터의 추가와 삭제를 효율적으로 수행할 수 있는 방법
String 기반으로 정보를 기록하고 관리할 때 사용

1. 전화번호부와 같음
2. key가 String인 경우가 대부분
3. put / get / getOrDefault

1.1. 해시법 (hashing)

데이터를 저장할 위치(인덱스)를 간단한 연산으로 구현하는 것
표에 정리한 값을 해시 값(hash value)이라고하며, 데이터에 접근할 때 사용
해시 테이블의 요소 = 버킷

인덱스	0	1	2	3	4	5	6	7	8
키 값	5	6	14	20	29	34	37	51	-
해시 값	5	6	5	2	2	7	1	6	-

해시값 = 각 요소의 값을 배열의 사이즈로 나눈 나머지 변경

인덱스	0	1	2	3	4	5	6	7	8
키 값1	-	37	29	-	-	14	51	34	-
키 값2	-	-	20	-	-	5	6	-	-

기존의 배열에 값을 추가하는 방법

1. 이진검색법으로 삽입할 위치 조사

2. 그 위치 이후의 모든 요소를 하나씩 뒤로 이동시킴

3. 삽입할 위치에 값을 추가

요소 이동과 삭제에 필요한 복잡도: O(n)

1.2. 충돌

위의 표처럼 저장할 버킷이 중복되는 현상 (위의 표는 체인법 사용)
가능한 해시는 값이 치우지지 않도록 고르게 분포된 값을 만들어야 함

2. 체인법, 오픈 해시법

같은 해시 값을 갖는 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법
해시 값(인덱스) 0, 3, 4, 8처럼 데이터가 하나도 없는 버킷의 값 = null

2.1. 버킷용 클래스 Node

Node<K,V> 클래스는 a, b의두 메서드 모두 사용 가능


      
      
      
    
    
      <java />
    
//해시를 구성하는 노드
	class Node<K,V> {
		private K key;
		private V data;
		private Node<K,V> next; //다음 노드에 대한 참조
		
		//생성자
		public Node(K key, V data, Node<K, V> next) {
			super();
			this.key = key;
			this.data = data;
			this.next = next;
		}
		
		//키 값 반환
		K getKey() {
			return key;
		}
		
		//데이터 반환
		V getValue() {
			return data;
		}
		
		//키의 해시 값 반환
		public int hashCode() {
			return key.hashCode();
		}
	}//end Node

제네릭 클래스 Node<K,V>가 전달받는 매개변수 자료형은 K, V이고, 이들은 독립적인 참조
키, 값, 다음 노드 참조 필드와
키, 데이터, 키의 해시 값 반환하는 메서드가 있음

2.2. 해시 클래스 ChainHash


      
      
      
    
    
      <java />
    
	private int size; //해시 테이블 크기
	private Node<K,V>[] table; //해시 테이블
	
	//생성자 - 비어있는 해시 테이블 생성
	public ChainHash(int capacity) {
		try {
			table = new Node[capacity];
			this.size = capacity;
		} catch (OutOfMemoryError e) { //테이블 생성X
			this.size = 0;
		}
	}
	
	//해시 값을 크기로 나눈 나머지를 구하는 메서드
	public int hashValue(Object key) {
		return key.hashCode() % size;
	}

hash class에는 위의 노드 클래스와 테이블, 사이즈 필드가 있고
생성자 - 비어있는 해시 테이블을 생성
hashValue 메서드 - 해시 값을 크기로 나눈 나머지를 구함, 키를 해시 테이블의 인덱스로 매핑하기 위해

2.2.1. 해시와 해시 함수 - 수정

충돌을 피하기 위해 해시 함수는 해시 테이블 크기 이하의 정수를 되도록 한쪽에 치우지지 않고 고르게 만들어 내야함
그래서 해시 테이블 크기는 소수가 좋음
키 값이 정수가 아닌 경우 해시 값을 구할 때는 좀 더 신경을 써 방법을 모색해야 함

2.2.2. search

1. 해시 함수가 키 값을 해시 값으로 변환
2. 해시 값을 인덱스로 하는 버킷 선택
3. 선택한 버킷을 돌면서 키 값과 같은 값을 찾으면 검색 성공


      
      
      
    
    
      <java />
    
//키 값 key를 갖는 요소의 검색(데이터를 반환)
	public V search(K key) {
		int hash = hashValue(key); //검색할 데이터의 해시 값
		Node<K,V> p = table[hash]; //선택 노드
		
		while(p != null) {
			if(p.getKey().equals(key))
				return p.getValue(); //검색 성공
			p = p.next; //다음 노드에 주목
		}
		return null; //검색 실패	
	}

2.2.3. add

같은 키 값이 있는지 검색 후, 없으면 노드를 새로 생성 후 삽입
1. 해시 함수가 키 값을 해시 값으로 변환
2. 해시 값을 인덱스로 하는 버킷 선택
3. 선택한 버킷을 돌면서 키 값과 같은 값을 찾으면 추가 실패, 못 찾으면 리스트의 맨 앞 위치에 노드를 삽입


      
      
      
    
    
      <java />
    
//키 값 key, 데이터 data를 갖는 요소의 추가
	public int add(K key, V data) {
		int hash = hashValue(key); //추가할 데이터의 해시 값
		Node<K,V> p = table[hash]; //선택 노드
		
		while(p != null) {
			if(p.getKey().equals(key)) //이 키 값을 이미 등록됨
				return 1;
			p = p.next; //다음 노드에 주목
		}
		
		Node<K,V> temp = new Node<K,V>(key, data, table[hash]);
		table[hash] = temp;  //노드를 삽입
		return 0;
	}

2.2.4. remove


      
      
      
    
    
      <java />
    
	//키 값 key를 갖는 요소의 삭제
	public int remove(K key) {
		int hash = hashValue(key); //삭제할 데이터의 해시 값
		Node<K,V> p = table[hash]; //선택 노드, 첫번째 노드를 가리킴
		Node<K,V> pp = null; //바로 앞의 선택 노드
		
		while(p != null) { //노드가 존재하고
			if(p.getKey().equals(key)) { //찾으면
				if(pp == null) //삭제하려는 노드가 첫 번째 노드인 경우
					table[hash] = p.next;
				else //삭제하려는 노드가 첫 번째 노드가 아닌 경우
					pp.next = p.next;
				return 0;
			}
			//못 찾으면 다음 노드 확인
			pp = p;
			p = p.next; //다음 노드를 가리킴
		}
		return 1; //키 값이 없음
	}

2.2.5. dump

해시 테이블을 통째로 출력하는 메서드


      
      
      
    
    
      <java />
    
//해시 테이블을 덤프
	public void dump() {
		for(int i = 0; i < size; i++) {
			Node<K,V> p = table[i];
			System.out.printf("%02d ", i);
			
			while(p != null) {
				System.out.printf("→ %s (%s)  ", p.getKey(), p.getValue());
				p = p.next;
			}
			System.out.println();
		}
	}

2.3. 전체 코드

ChainHash.java


      
      
      
    
    
      <java />
    
package chap11_1;

//체인법 - 해시
public class ChainHash<K,V> {
	//해시를 구성하는 노드
	class Node<K,V> {
		private K key;
		private V data;
		private Node<K,V> next; //다음 노드에 대한 참조
		
		//생성자
		public Node(K key, V data, Node<K, V> next) {
			super();
			this.key = key;
			this.data = data;
			this.next = next;
		}
		
		//키 값 반환
		K getKey() {
			return key;
		}
		
		//데이터 반환
		V getValue() {
			return data;
		}
		
		//키의 해시 값 반환, 키가 가지고 있는 해시코드
		public int hashCode() {
			return key.hashCode();
		}
	}//end Node
	
	private int size; //해시 테이블 크기
	private Node<K,V>[] table; //해시 테이블
	
	//생성자 - 비어있는 해시 테이블 생성
	public ChainHash(int capacity) {
		try {
			table = new Node[capacity];
			this.size = capacity;
		} catch (OutOfMemoryError e) { //테이블 생성X
			this.size = 0;
		}
	}
	
	//해시 값을 크기로 나눈 나머지를 구하는 메서드
	public int hashValue(Object key) {
		return key.hashCode() % size;
	}
	
	//키 값 key를 갖는 요소의 검색(데이터를 반환)
	public V search(K key) {
		int hash = hashValue(key); //검색할 데이터의 해시 값
		Node<K,V> p = table[hash]; //선택 노드
		
		while(p != null) {
			if(p.getKey().equals(key))
				return p.getValue(); //검색 성공
			p = p.next; //다음 노드에 주목
		}
		return null; //검색 실패	
	}
	
	//키 값 key, 데이터 data를 갖는 요소의 추가
	public int add(K key, V data) {
		int hash = hashValue(key); //추가할 데이터의 해시 값
		Node<K,V> p = table[hash]; //선택 노드
		
		while(p != null) {
			if(p.getKey().equals(key)) //이 키 값을 이미 등록됨
				return 1;
			p = p.next; //다음 노드에 주목
		}
		
		Node<K,V> temp = new Node<K,V>(key, data, table[hash]);
		table[hash] = temp;  //노드를 삽입
		return 0;
	}
	
	//키 값 key를 갖는 요소의 삭제
	public int remove(K key) {
		int hash = hashValue(key); //삭제할 데이터의 해시 값
		Node<K,V> p = table[hash]; //선택 노드, 첫번째 노드를 가리킴
		Node<K,V> pp = null; //바로 앞의 선택 노드
		
		while(p != null) { //노드가 존재하고
			if(p.getKey().equals(key)) { //찾으면
				if(pp == null) //삭제하려는 노드가 첫 번째 노드인 경우
					table[hash] = p.next;
				else //삭제하려는 노드가 첫 번째 노드가 아닌 경우
					pp.next = p.next;
				return 0;
			}
			//못 찾으면 다음 노드 확인
			pp = p;
			p = p.next; //다음 노드를 가리킴
		}
		return 1; //키 값이 없음
	}
	
	//해시 테이블을 덤프
	public void dump() {
		for(int i = 0; i < size; i++) {
			Node<K,V> p = table[i];
			System.out.printf("%02d ", i);
			
			while(p != null) {
				System.out.printf("→ %s (%s)  ", p.getKey(), p.getValue());
				p = p.next;
			}
			System.out.println();
		}
	}
	
}

ChainHashTester.java


      
      
      
    
    
      <java />
    
package chap11_1;

import java.util.Scanner;

import chap10_1.BinTree;

//체인법에 의한 해시의 사용 예
public class ChainHashTester {

	static Scanner scan = new Scanner(System.in);

	// 데이터(회원번호 + 이름)
	static class Data {
		static final int NO = 1;
		static final int NAME = 2;

		private Integer no;
		private String name;

		// 키 값
		Integer KeyCode() {
			return no;
		}

		// 문자열을 반환합니다.
		public String toString() {
			return name;
		}

		// 데이터를 입력
		void scanData(String guide, int sw) {
			System.out.println(guide + "할 데이터를 입력하세요.");

			if ((sw & NO) == NO) {
				System.out.print("번호: ");
				no = scan.nextInt();
			}

			if ((sw & NAME) == NAME) {
				System.out.print("이름: ");
				name = scan.next();
			}
		}
	} // end Data class

	// 메뉴 열거형
	enum Menu {
		ADD("삽입"), REMOVE("삭제"), SEARCH("검색"), DUMP("표시"), TERMINATE("종료");

		private final String message; // 출력할 문자열

		static Menu MenuAt(int idx) { // 서수가 idx인 열거를 반환
			for (Menu m : Menu.values())
				if (m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) { // 생성자
			message = string;
		}

		String getMessage() { // 출력할 문자열을 반환
			return message;
		}
	} // end enum

	// 메뉴 선택
	static Menu SelectMenu() {
		int key;

		do {
			for (Menu m : Menu.values()) {
				System.out.printf("(%d) %s  ", m.ordinal(), m.message);
				if ((m.ordinal() % 3) == 2 && m.ordinal() != Menu.TERMINATE.ordinal())
					System.out.println();
			}
			System.out.print("  : ");
			key = scan.nextInt();
		} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());
		return Menu.MenuAt(key);
	} // end SelectMenu

	public static void main(String[] args) {
		Menu menu;
		Data data; // 추가용 데이터 참조
		Data temp = new Data(); // 입력용 데이터

		ChainHash<Integer, Data> hash = new ChainHash<Integer, Data>(13);

		do {
			switch (menu = SelectMenu()) {
			case ADD:
				data = new Data();
				data.scanData("삽입", Data.NO | Data.NAME);
				hash.add(data.KeyCode(), data);
				break;

			case REMOVE:
				temp.scanData("삭제", Data.NO);
				hash.remove(temp.KeyCode());
				break;

			case SEARCH:
				temp.scanData("검색", Data.NO);
				Data t = hash.search(temp.KeyCode());
				if (t != null) {
					System.out.println("그 번호의 이름은 " + t + "입니다.");
				} else {
					System.out.println("해당 데이터가 없습니다.");
				}
				break;

			case DUMP:
				hash.dump();
				break;
			}
		} while (menu != Menu.TERMINATE);
	} // end main

}

3. 오픈 주소법 (open addressing)

닫힌 해시법 (closed hashing)
충돌 발생시 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법

버킷 클래스 Bucket<K,V>

해시 클래스 OpenHash<K,V>

3.1. 전체 코드

OpenHash.java


      
      
      
    
    
      <java />
    
package chap11_1;

//오픈 주소법에 의한 해시
public class OpenHash<K, V> {
	// 버킷의 상태
	enum Status {
		OCCUPIED, EMPTY, DELETED
	}; // {데이터 저장, 비어 있음, 삭제 마침}

	// 버킷
	static class Bucket<K, V> {
		private K key;
		private V data;
		private Status stat; // 상태

		// 생성자
		Bucket() {
			stat = Status.EMPTY; // 버킷은 비어있음
		}

		// 모든 필드에 값 설정
		void set(K key, V data, Status stat) {
			this.key = key;
			this.data = data;
			this.stat = stat;
		}

		// 상태 설정
		void setStat(Status stat) {
			this.stat = stat;
		}

		// 키 값 반환
		K getKey() {
			return key;
		}

		// 데이터 값 반환
		V getValue() {
			return data;
		}

		// 키의 해시 값을 반환
		public int hashCode() {
			return key.hashCode();
		}
	} // end class Bucket

	private int size; // 해시 테이블의 크기
	private Bucket<K, V>[] table; // 해시 테이블

	// 생성자
	public OpenHash(int size) {
		try {
			table = new Bucket[size];
			for (int i = 0; i < size; i++)
				table[i] = new Bucket<K, V>();
			this.size = size;
		} catch (OutOfMemoryError e) { // 테이블 생성 불가
			this.size = 0;
		}
	}

	// 해시 값을 구함
	public int hashValue(Object key) {
		return key.hashCode() % size;
	}

	// 재해시 값을 구함
	public int rehashValue(int hash) {
		return (hash + 1) % size;
	}

	// 키 값 key를 갖는 버킷의 검색
	private Bucket<K, V> searchNode(K key) {
		int hash = hashValue(key);
		Bucket<K, V> p = table[hash];

		for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
			if (p.stat == Status.OCCUPIED && p.getKey().equals(key))
				return p;
			hash = rehashValue(hash); // 재해시
			p = table[hash];
		}
		return null;
	}
	
	//키 값 key를 갖는 요소의 검색 (데이터를 반환)
	public V search(K key) {
		Bucket<K,V> p = searchNode(key);
		if(p != null)
			return p.getValue();
		else
			return null;
	}

	// 키 값 key, 데이터 data를 갖는 요소의 추가
	public int add(K key, V data) {
		if (searchNode(key) != null)
			return 1;

		int hash = hashValue(key);
		Bucket<K, V> p = table[hash];
		for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
			if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {
				p.set(key, data, Status.OCCUPIED);
				return 0;
			}
			hash = rehashValue(hash); // 재해시
			p = table[hash];
		}
		return 2; // 해시 테이블이 가득 참
	}

	// 키 값 key를 갖는 요소의 삭제
	public int remove(K key) {
		Bucket<K, V> p = searchNode(key); // 선택 버킷
		if (p == null)
			return 1;

		p.setStat(Status.DELETED);
		return 0;
	}

	// 해시 테이블을 덤프
	public void dump() {
		for (int i = 0; i < size; i++) {
			System.out.printf("%02d ", i);
			switch (table[i].stat) {
			case OCCUPIED:
				System.out.printf("%s (%s)\n",
									table[i].getKey(), table[i].getValue());
				break;
			case EMPTY:
				System.out.println("-- 미등록 --");
				break;
			case DELETED:
				System.out.println("-- 삭제 마침 --");
				break;
			} //end switch
		} //end for
	} //end dump

}

OpenHashTester.java


      
      
      
    
    
      <java />
    
package chap11_1;

import java.util.Scanner;

//오픈 주소법에 의한 해시 사용 예
public class OpenHashTester {
	
	static Scanner scan = new Scanner(System.in);

	// 데이터(회원번호 + 이름)
	static class Data {
		static final int NO = 1;
		static final int NAME = 2;

		private Integer no;
		private String name;

		// 키 값
		Integer KeyCode() {
			return no;
		}

		// 문자열을 반환합니다.
		public String toString() {
			return name;
		}

		// 데이터를 입력
		void scanData(String guide, int sw) {
			System.out.println(guide + "할 데이터를 입력하세요.");

			if ((sw & NO) == NO) {
				System.out.print("번호: ");
				no = scan.nextInt();
			}

			if ((sw & NAME) == NAME) {
				System.out.print("이름: ");
				name = scan.next();
			}
		}
	} // end Data class

	// 메뉴 열거형
	enum Menu {
		ADD("삽입"), REMOVE("삭제"), SEARCH("검색"), DUMP("표시"), TERMINATE("종료");

		private final String message; // 출력할 문자열

		static Menu MenuAt(int idx) { // 서수가 idx인 열거를 반환
			for (Menu m : Menu.values())
				if (m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) { // 생성자
			message = string;
		}

		String getMessage() { // 출력할 문자열을 반환
			return message;
		}
	} // end enum

	// 메뉴 선택
	static Menu SelectMenu() {
		int key;

		do {
			for (Menu m : Menu.values()) {
				System.out.printf("(%d) %s  ", m.ordinal(), m.message);
				if ((m.ordinal() % 3) == 2 && m.ordinal() != Menu.TERMINATE.ordinal())
					System.out.println();
			}
			System.out.print("  : ");
			key = scan.nextInt();
		} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());
		return Menu.MenuAt(key);
	} // end SelectMenu

	public static void main(String[] args) {
		Menu menu;
		Data data; // 추가용 데이터 참조
		Data temp = new Data(); // 입력용 데이터

		OpenHash<Integer, Data> hash = new OpenHash<Integer, Data>(13);

		do {
			switch (menu = SelectMenu()) {
			case ADD:
				data = new Data();
				data.scanData("삽입", Data.NO | Data.NAME);
				hash.add(data.KeyCode(), data);
				break;

			case REMOVE:
				temp.scanData("삭제", Data.NO);
				hash.remove(temp.KeyCode());
				break;

			case SEARCH:
				temp.scanData("검색", Data.NO);
				Data t = hash.search(temp.KeyCode());
				if (t != null) {
					System.out.println("그 번호의 이름은 " + t + "입니다.");
				} else {
					System.out.println("해당 데이터가 없습니다.");
				}
				break;

			case DUMP:
				hash.dump();
				break;
			}
		} while (menu != Menu.TERMINATE);
	} // end main
}

728x90

'Study > Data Structure&Algorithm' 카테고리의 다른 글

[코딩테스트] two pointer technique / 투 포인터 기법 (0)	2024.05.10
[자료구조&알고리즘] 트리, 이진 트리, 이진 검색 트리 (0)	2023.06.25
[자료구조&알고리즘] 리스트 (선형, 연결(포인터, 커서), 원형, 이중 연결) (0)	2023.06.07
[자료구조&알고리즘] 셸, 퀵, 병합, 힙, 도수(계수) 정렬 (0)	2023.06.02
[자료구조&알고리즘] 재귀 알고리즘(팩토리얼, 유클리드 호제법), 하노이의 탑, N퀸 문제 / 백트래킹 (0)	2023.05.08

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

1. 해시

1.1. 해시법 (hashing)

1.2. 충돌

2. 체인법, 오픈 해시법

2.1. 버킷용 클래스 Node

2.2. 해시 클래스 ChainHash

2.2.1. 해시와 해시 함수 - 수정

2.2.2. search

2.2.3. add

2.2.4. remove

2.2.5. dump

2.3. 전체 코드

3. 오픈 주소법 (open addressing)

3.1. 전체 코드

'Study > Data Structure&Algorithm' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

'Study > Data Structure&Algorithm' 카테고리의 다른 글

검색 태그

최근 댓글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역