728x90
해시
- 데이터의 추가와 삭제를 효율적으로 수행할 수 있는 방법
- String 기반으로 정보를 기록하고 관리할 때 사용
1. 전화번호부와 같음
2. key가 String인 경우가 대부분
3. put / get / getOrDefault
해시법 (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)
충돌
- 위의 표처럼 저장할 버킷이 중복되는 현상 (위의 표는 체인법 사용)
- 가능한 해시는 값이 치우지지 않도록 고르게 분포된 값을 만들어야 함
체인법, 오픈 해시법
- 같은 해시 값을 갖는 데이터를 쇠사슬 모양으로 연결 리스트에서 연결하는 방법
- 해시 값(인덱스) 0, 3, 4, 8처럼 데이터가 하나도 없는 버킷의 값 = null
버킷용 클래스 Node<K,V>
- Node<K,V> 클래스는 a, b의두 메서드 모두 사용 가능
//해시를 구성하는 노드
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이고, 이들은 독립적인 참조
- 키, 값, 다음 노드 참조 필드와
- 키, 데이터, 키의 해시 값 반환하는 메서드가 있음
해시 클래스 ChainHash<K,V>
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 메서드 - 해시 값을 크기로 나눈 나머지를 구함, 키를 해시 테이블의 인덱스로 매핑하기 위해
해시와 해시 함수 - 수정
- 충돌을 피하기 위해 해시 함수는 해시 테이블 크기 이하의 정수를 되도록 한쪽에 치우지지 않고 고르게 만들어 내야함
- 그래서 해시 테이블 크기는 소수가 좋음
- 키 값이 정수가 아닌 경우 해시 값을 구할 때는 좀 더 신경을 써 방법을 모색해야 함
search
1. 해시 함수가 키 값을 해시 값으로 변환
2. 해시 값을 인덱스로 하는 버킷 선택
3. 선택한 버킷을 돌면서 키 값과 같은 값을 찾으면 검색 성공
//키 값 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; //검색 실패
}add
같은 키 값이 있는지 검색 후, 없으면 노드를 새로 생성 후 삽입
1. 해시 함수가 키 값을 해시 값으로 변환
2. 해시 값을 인덱스로 하는 버킷 선택
3. 선택한 버킷을 돌면서 키 값과 같은 값을 찾으면 추가 실패, 못 찾으면 리스트의 맨 앞 위치에 노드를 삽입
//키 값 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;
}remove
//키 값 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; //키 값이 없음
}dump
- 해시 테이블을 통째로 출력하는 메서드
//해시 테이블을 덤프
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();
}
}전체 코드
더보기
ChainHash.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
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
}오픈 주소법 (open addressing)
- 닫힌 해시법 (closed hashing)
- 충돌 발생시 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법
버킷 클래스 Bucket<K,V>
해시 클래스 OpenHash<K,V>
전체 코드
더보기
OpenHash.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
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 |
