160107P(목)

자료구조 Chapter12 - 해시

 

버블, 선택, 삽입, 퀵, 합병 등 여러가지 알고리즘은 성능이 아무리 좋더라도 자료의 크기가 커질수록 탐색시간이 증가

이와 같은 한계를 극복하기 위해서 해시가 도입되었다.

 

해시(hash)

해시 테이블

자료를 저장하는데 기본적으로 배열구조 사용

 

배열은 저장 위치를 알면 한번에 접근이 가능한 성질을 이용하여 자료 자체와 연관된 숫자를 만들어 낸 뒤 해시테이블의 해당 위치에 자료를 저장한다.

 

O(1)의 성능을 자랑한다!

 

해시 메소드

자료 자체에 연관된 숫자를 만들고 해시 테이블에 접근하는 메소드

해시 메소드에 따라서 성능차이가 많이난다.

 

해시 값

자료를 해시메소드에 입력해서 반환된 값

 

해시테이블 크기

크기에 따라서 성능 차이가 많이 나므로 신중하게 결정해야 한다.

 

충돌(collision)

자료가 저장되어야 할 위치에 이미 다른 자료가 저장되어 있는 현상

 

모듈러 연산자(%)를 사용한 해시 메소드는 해시 테이블 크기를 소수로 만들면 충돌이 적어진다.

ex)

data % hTableSize;

 

SimpleHash.java

public class Entry {

private int value;

 

public void setValue(int val) {

value = val;

}

 

public int getValue {

return value;

}

}

 

public class SimpleHash {

// 해시 테이블 크기

private int hTableSize;

private int Entry[] hTable;

 

public SimpleHash(int val) {

hTableSize = val;

 

hTable = new Entry[hTableSize];

}

 

public int hFunc(int val) {

return val % hTableSize;

}

 

public void insert(int data) {

int val;

Entry entry;

 

entry = new Entry();

entry.setValue(data);

 

val = hFunc(data);

if(hTable[val] == null) {

hTable[val] = entry;

 

System.out.print(data + " 입력\t");

}

 

// 충돌 시 대책없음

else {

System.out.print(data + " 입력실패\t");

}

}

 

public void showHashTable() {

for(int i = 0; i < hTableSize; i++) {

if(hTable[i] == null) {

System.out.print("_ ");

}

else {

System.out.print(hTable[i].getValue() + " ");

}

System.out.println();

}

}

 

자료를 숫자와 연관시키기

자료가 숫자가 아니라면 자료를 그와 관련된 숫자로 변환해야 한다.

 

고유번호 주기

주민등록번호나 학번 같이 각 개체당 고정된 크기의 고유한 번호를 주는 경우는 고유번호를 그대로 키값으로 사용가능

고유번호를 알아야만 자료에 접근할 수 있는 단점 존재

 

자료에서 숫자 추출

고유번호를 할당하는것이 어려울 경우 자료 자체에서 숫자를 추출한다.

ex)

a = 1

b = 2

c = 3

d = 4

.

.

.

x = 24

y = 25

z = 26

 

hash = (8 * 26^3 + 1 * 26^2 + 19 * 26^1 + 8 * 26^0) % hTableSize

 

  호너의 방법(Honer's method)

  = (((8 * 26 + 1) * 26 + 19) * 26 + 8) % hTableSize

 

충돌 해결 방법

1. 개방 주소법

ㄱ. 순차탐색

ㄴ. 지수탐색

ㄷ. 이중탐색

 

2. 분리 연결법

 

개방주소법(open addressing)

해시테이블의 해당 셀에 자료를 바로 입력하는 방법

 

순차탐색(linear probing)

충돌이 일어났을 경우, 해당 셀에서부터 차례로 셀을 검사한 뒤 비어있는 셀을 찾아서 빈 셀에 자료를 저장한다.

 

단점

자료가 들어가야할 셀과 전혀 관계없는 셀에 입력되므로 찾기 힘들다.

 

클러스터(cluster)

비어있는 셀 없이 차있는 셀로만 구성된 덩어리

클러스터가 커질수록 해시의 성능이 전반적으로 떨어진다.

 

LinearProbing.java

public class Entry {

private int value;

 

public void setValue(int val) {

value = val;

}

 

public int getValue {

return value;

}

}

 

public class LinearProbing {

// 해시 테이블 크기

private int hTableSize;

private int Entry[] hTable;

 

public LinearProbing(int val) {

hTableSize = val;

 

hTable = new Entry[hTableSize];

}

 

public int hFunc(int key) {

return key % hTableSize;

}

 

public getKey(int data) {

return data;

}

 

public Entry getEntry(int val) {

return hTable[val];

}

 

public void insert(int data) {

int key, hVal;

int point;

Entry entry;

 

key = getKey(data);

hVal = hFunc(key);

 

entry = new Entry();

entry.setValue(data);

 

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

hTable[point] = entry;

 

System.out.print(data + " 삽입 성공\t");

 

return 0;

}

else if(hTable[point].getValue() == '*') {

hTable[point] = entry;

 

System.out.print(data + " 삽입 성공\t");

 

return 0;

}

else {

point++;

}

 

if(point > hTableSize - 1)

point = 0;

}

System.out.print(data + " 삽입 실패\t");

 

return -1;

}

 

public int searchForDel(int data) {

int key, hVal;

in point;

 

key = getKey(data);

hVal = hFunc(key);

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

return -1;

}

else if(hTable[point].getValue() == '*') {

return -1;

}

else if(hTable[point].getValue() == data) {

return point;

}

else

point++;

 

if(point > hTableSize - 1) {

point = 0;

}

}

 

System.out.println("탐색 실패");

 

return -1;

}

 

public int search(int data) {

int key, hVal;

in point;

 

key = getKey(data);

hVal = hFunc(key);

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

System.out.print(data + " 탐색 실패\n");

 

return -1;

}

else if(hTable[point].getValue() == '*') {

System.out.print(data + " 탐색 실패\n");

 

return -1;

}

else if(hTable[point].getValue() == data) {

System.out.print(data + " 탐색 성공\n");

 

return point;

}

else

point++;

 

if(point > hTableSize - 1) {

point = 0;

}

}

 

System.out.println("탐색 실패");

 

return -1;

}

 

public int delete(int data) {

int find;

 

if(find = searchForDel(data) == -1) {

System.out.print(data + " 자료가 존재하지 않습니다.\t");

 

return -1;

}

else {

hTable[find].setValue('*');

 

System.out.print(data + " 삭제 성공\t");   

 

return 0;

}

}  

 

public void showHashTable() {

for(int i = 0; i < hTableSize; i++) {

if(hTable[i] == null) {

System.out.print("_ ");

}

else if(hTable[i].getValue() == '*') {

System.out.print("* ");

}

else {

System.out.print(hTable[i].getValue() + " ");

}

System.out.println();

}

}

 

지수 탐색(quadratic probing)

순차탐색이 클러스터가 커질 때 입력 효율이 떨어지는 것을 보완

 

탐색 단위(step size)

원하는 셀이 비어있지 않으면 4번째, 9번째, 16번째, 25번째 등 순서로 셀을 탐색한다.

 

이중해싱(double hashing)

탐색하는 순서가 똑같아서 클러스터 크기는 여전히 커진다는 단점을 보완

 

QuadraticProbing.java

public class Entry {

private int value;

 

public void setValue(int val) {

value = val;

}

 

public int getValue {

return value;

}

}

 

public class QuadraticProbing {

// 해시 테이블 크기

private int hTableSize;

private int Entry[] hTable;

 

public QuadraticProbing(int val) {

hTableSize = val;

 

hTable = new Entry[hTableSize];

}

 

public int hFunc(int key) {

return key % hTableSize;

}

 

public getKey(int data) {

return data;

}

 

public Entry getEntry(int val) {

return hTable[val];

}

 

public void insert(int data) {

int key, hVal;

int point;

Entry entry;

 

key = getKey(data);

hVal = hFunc(key);

 

entry = new Entry();

entry.setValue(data);

 

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

hTable[point] = entry;

 

System.out.print(data + " 삽입 성공\t");

 

return 0;

}

else if(hTable[point].getValue() == '*') {

hTable[point] = entry;

 

System.out.print(data + " 삽입 성공\t");

 

return 0;

}

else {

point += (2 * i + 1);

}

 

// point = 0;

// point를 2 * i + 1만큼 늘려서 삽입하므로 지수단위로 초기화 해줘야 한다고 생각한다.

if(point > hTableSize - 1)

point = point - hTableSize;

}

System.out.print(data + " 삽입 실패\t");

 

return -1;

}

 

public int searchForDel(int data) {

int key, hVal;

in point;

 

key = getKey(data);

hVal = hFunc(key);

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

return -1;

}

else if(hTable[point].getValue() == '*') {

return -1;

}

else if(hTable[point].getValue() == data) {

return point;

}

else

point += (2 * i + 1);

 

if(point > hTableSize - 1) {

point = point - hTableSize;

}

}

 

System.out.println("탐색 실패");

 

return -1;

}

 

public int search(int data) {

int key, hVal;

in point;

 

key = getKey(data);

hVal = hFunc(key);

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

System.out.print(data + " 탐색 실패\n");

 

return -1;

}

else if(hTable[point].getValue() == '*') {

System.out.print(data + " 탐색 실패\n");

 

return -1;

}

else if(hTable[point].getValue() == data) {

System.out.print(data + " 탐색 성공\n");

 

return point;

}

else

point += (2 * i + 1);

 

if(point > hTableSize - 1) {

point = point - hTableSize;

}

}

 

System.out.println("탐색 실패");

 

return -1;

}

 

public int delete(int data) {

int find;

 

if(find = searchForDel(data) == -1) {

System.out.print(data + " 자료가 존재하지 않습니다.\t");

 

return -1;

}

else {

hTable[find].setValue('*');

 

System.out.print(data + " 삭제 성공\t");   

 

return 0;

}

}  

public void showHashTable() {

for(int i = 0; i < hTableSize; i++) {

if(hTable[i] == null) {

System.out.print("_ ");

}

else if(hTable[i].getValue() == '*') {

System.out.print("* ");

}

else {

System.out.print(hTable[i].getValue() + " ");

}

System.out.println();

}

}

 

이중해싱(double hashing)

지수탐색에서 탐색단위가 고정되어 클러스터 크기가 여전히 커지는 단점을 보완

 

첫번째 해싱

자료를 입력할 셀을 찾는 해싱

 

두번째 해싱

f2val - (key % f2val);

충돌이 일어났을 경우에만 탐색단위 계산

탐색단위는 절대 0이 되어서는 안된다.

탐색단위로 셀에 접근했을 때 모든 셀에 접근할 수 있어야 한다. = 해시 메소드에 사용되는 값(f2val)과 해시테이블 크기가 서로소

 

DoubleHashing.java

public class Entry {

private int value;

 

public void setValue(int val) {

value = val;

}

 

public int getValue {

return value;

}

}

 

public class DoubleHashing {

// 해시 테이블 크기

private int hTableSize;

private int Entry[] hTable;

 

public DoubleHashing(int val) {

hTableSize = val;

 

hTable = new Entry[hTableSize];

}

 

public int hFunc1(int key) {

return key % hTableSize;

}

 

public int hFunc2(int key) {

int f2val = 7;

 

return f2val - (key % f2val);

}

 

public getKey(int data) {

return data;

}

 

public Entry getEntry(int val) {

return hTable[val];

}

 

public void insert(int data) {

int key, hVal;

int point;

Entry entry;

 

key = getKey(data);

hVal = hFunc(key);

 

entry = new Entry();

entry.setValue(data);

 

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

hTable[point] = entry;

 

System.out.print(data + " 삽입 성공\t");

 

return 0;

}

else if(hTable[point].getValue() == '*') {

hTable[point] = entry;

 

System.out.print(data + " 삽입 성공\t");

 

return 0;

}

else {

point += hFunc2(key);

}

 

// point = 0;

// point를 2 * i + 1만큼 늘려서 삽입하므로 지수단위로 초기화 해줘야 한다고 생각한다.

if(point > hTableSize - 1)

point = point - hTableSize;

}

System.out.print(data + " 삽입 실패\t");

 

return -1;

}

 

public int searchForDel(int data) {

int key, hVal;

in point;

 

key = getKey(data);

hVal = hFunc(key);

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

return -1;

}

else if(hTable[point].getValue() == '*') {

return -1;

}

else if(hTable[point].getValue() == data) {

return point;

}

else

point += hFunc2(key);

 

if(point > hTableSize - 1) {

point = point - hTableSize;

}

}

 

System.out.println("탐색 실패");

 

return -1;

}

 

public int search(int data) {

int key, hVal;

in point;

 

key = getKey(data);

hVal = hFunc(key);

point = hVal;

 

for(int i = 0; i < hTableSize; i++) {

if(hTable[point] == null) {

System.out.print(data + " 탐색 실패\n");

 

return -1;

}

else if(hTable[point].getValue() == '*') {

System.out.print(data + " 탐색 실패\n");

 

return -1;

}

else if(hTable[point].getValue() == data) {

System.out.print(data + " 탐색 성공\n");

 

return point;

}

else

point += hFunc2(key);

 

if(point > hTableSize - 1) {

point = point - hTableSize;

}

}

 

System.out.println("탐색 실패");

 

return -1;

}

 

public int delete(int data) {

int find;

 

if(find = searchForDel(data) == -1) {

System.out.print(data + " 자료가 존재하지 않습니다.\t");

 

return -1;

}

else {

hTable[find].setValue('*');

 

System.out.print(data + " 삭제 성공\t");   

 

return 0;

}

}  

public void showHashTable() {

for(int i = 0; i < hTableSize; i++) {

if(hTable[i] == null) {

System.out.print("_ ");

}

else if(hTable[i].getValue() == '*') {

System.out.print("* ");

}

else {

System.out.print(hTable[i].getValue() + " ");

}

System.out.println();

}

}

 

분리 연결법(separate chaining)

연결리스트를 사용하므로 별도의 충돌 해결 방법을 갖지 않는다.

무조건 뒤에 삽입하는것은 효율이 떨어지므로 정렬삽입을 한다.

 

SeparateChaining.java

pubilc class Link {

private int value;

public Link next;

 

public void setValue(int val) {

value = val;

}

 

public int getValue() {

return value;

}

}

 

public class SeparateChaning {

private int hTableSize;

private Link[] hTable;

 

public SeparateChaning(int val) {

hTableSize = val;

hTable = new Link[hTableSize];

}

 

public int hFunc(int key) {

return key % hTableSize;

}

 

public int getKey(int data) {

return data;

}

 

public int insert(int data) {

int key, hVal;

Link link;

Link pre, cur;

key = getKey(data);

hVal = hFunc(key);

 

link = new Link();

link.setValue(data);

 

if(hTable[hVal] == null) {

hTable[hVal] = link;

 

return 0;

}

 

pre = null;

cur = hTable[hVal];

while(true) {

if(cur == null) {

pre.next = link;

 

return 0;

}

else if(cur.getValue() < key) {

pre = cur;

cur = cur.next;

}

 

// 이 링크의 앞에 삽입

else {

 

// cur링크가 리스트의 헤더

if(cur == hTable[hVal]) {

link.next = cur;

hTable[hVal] = link;

 

return 0;

}

else {

link.next = cul;

pre.next = link;

 

return 0;

}

}

}

}

 

public int search(int data) {

int key, hVal;

Link cur;

 

key = getKey(data);

hVal = hFunc(key);

cur = hTable[hVal];

 

while(true) {

if(cur == null) {

System.out.println(key + " : 찾지 못하고 리스트의 끝에 닿음\n");

 

return -1;

}

else if(cur.getValue() == key) {

System.out.println(cur.getValue() + " 찾음\n");

 

return 0;

}

else if(cur.getValue() > key) {

System.out.println(key + " : 찾지 못하고 더 큰 자료를 만남\n");

 

return -1;

}

else {

cur = cur.next;

}

}

}

 

public int searchForDel(int data) {

int key, hVal;

Link cur;

 

key = getKey(data);

hVal = hFunc(key);

cur = hTable[hVal];

 

while(true) {

if(cur == null) {

return null;

}

else if(cur.getValue() == key) {

return pre;

}

else if(cur.getValue() > key) {

return null;

}

else {

cur = cur.next;

}

}

}

 

public int delete(int data) {

int key, hVal;

Link pre, cur;

 

key = getKey(data);

hVal = hFunc(key);

 

if((pre = searchForDel(data)) == null) {

System.out.println(data + " 자료가 존재하지 않습니다.\n");

 

return -1;

}

 

cur = pre.next;

pre.next = cur.next;

 

return 0;

}

 

public void showHashTable() {

Link cur;

 

for(int i = 0; i < hTableSize; i++) {

System.out.print("|" + i + "|\t");

 

cur = hTable[i];

 

if(cur == null) {

System.out.print("_ ");

}

else {

while(cur != null) {

System.out.print(cur.getValue() + " ");

cur = cur.next;

}

}

System.out.println("");

}

System.out.println("");

}

}

 

입력자료가 많아지면 해시테이블 크기가 작아서 충돌이 발생할 수 있다.

해시 테이블 크기를 늘리면 안의 자료를 전부 다시 연산해야 하므로 효율성이 떨어진다.

따라서 입력 자료수가 확실하지 않으면 분리연결법을 사용하자