해쉬 이해하기(Java)

http://hyeonstorage.tistory.com/265

여기 블로그 보고 작성했습니다. 해쉬 이해하기 쉽게 잘 쓰셨던데 지금은 휴면이라서.. 아쉽더군요.

Hash.java

public class Hash {

// 데이터 저장할 Entry는 값과 다음 Entry를 가지고 있는다.

// 해쉬테이블에 저장인덱스가 중복될 경우(충돌발생!) 분리연결법을 사용해 그 인덱스에 연결리스트를 만들어 관리하기 위한것.

private class Entry{

private int value;

public Entry next;

}

private int size;

private Entry[] hTable;

// 생성자.. size를 받아서 배열 테이블을 생성한다.

public Hash(int size) {

this.size = size;

this.hTable = new Entry[size];

}

// key 값으로 해쉬 테이블에 저장될 인덱스를 리턴

public int hashMethod(int key) {

return key % size; // 키값을 사이즈로 나눈 나머지 값으로 인덱스를 만든다. 사이즈가 10인 경우 키가 5라면 5, 12라면 2를 반환..

// 데이터가 많다면 사이즈를 크게 하는게 중복을 줄이는 길이겠지... 소숫값으로 하는게 더 나은 방법이다. 소수가 아닐때보다 중복값이 적음~

}

// 저장할 데이터로 키(해쉬코드)를 추출한다. 실제 해쉬에는 특별한 알고리즘이 적용돼 해쉬코드를 얻는다.

public int getKey(int data) {

return data; // 여기선 그냥 숫자값 그대로 키값으로 사용한다.

}

// 데이터를 해쉬테이블에 저장한다.

public int add(int data) {

// data의 키(해쉬코드)와 저장할 인덱스를 얻는다.

int key = getKey(data);

int hashValue = hashMethod(key);

// 저장할 Entry 생성

Entry entry = new Entry();

entry.value = data;

// 해쉬 테이블에 저장할 인덱스가 비어있다면, 저장하고 끝낸다.

if(hTable[hashValue] == null) {

hTable[hashValue] = entry;

return 0;

}

// 만약에 저장할 인덱스에 데이터가 있다면! 중복이므로, 엔트리 배열에 담아야한다.

Entry pre = null;

Entry cur = hTable[hashValue]; // 기존에 담겨있던 엔트리를 커서로 지정.

// 해쉬코드순으로 정렬한다는걸 기억하자.

// 해당 인덱스의 연결리스트(엔트리 배열)는 값의 크기가 작은 값부터 큰 순서로 정렬되어있다.

while(true) {

if(cur == null) {

System.out.println("cursor가 null입니다. pre.next를 들어올값("+ key +")로 설정합니다.");

//hTable[hashValue] = entry; // 이부분을 아래처럼 수정했더니 제대로 돌아감!

pre.next = entry;

return 0;

}else if(getKey(cur.value) < key) {

System.out.println("cursor 값("+ getKey(cur.value) +")이 들어올 값("+ key +")보다 작습니다. pre는 현재커서가 되고, 커서는 다음 커서로 넘어갑니다.");

// 해당 인덱스의 커서 노드의 해쉬코드값이 key(새로 들어올 데이터의 해쉬코드값)보다 작으면 커서를 하나 뒤로 옮긴다.

// 기존에 저장된 값이, 새로 들어올 값보다 작으면

// 기존 저장된 엔트리가 pre가 되고, 커서를 다음 노드로 옮긴다...

// (다음 노드가 null이면... 다음 while문에서 위에 조건문을 타면서 엔트리를 저장하고 끝.)

// 근데 여기서 드는 의문은 pre의 next에는 왜 아무것도 저장을 저장을 안하지..?? 계속 null 아닌가? 로직이 뭔가 이상한데...

pre = cur;

cur = cur.next;

}else {

// 해당 인덱스의 커서 노드의 해쉬코드값이 key(새로 들어올 데이터의 해쉬코드값)보다 크면, 여기 저장!!

// 해당 인덱스의 커서 노드의 값이 key보다 크면, 여기에 저장한다.

// 커서 노드가 HashTable의 첫번째 노드이면

if(cur == hTable[hashValue]) {

System.out.println("cursor 값("+ getKey(cur.value) +")이 리스트의 첫번째 값("+ hTable[hashValue].value +")과 같습니다.");

// 삽입 노드를 첫번째 노드로 삽입하고, 다음 노드를 커서노드로 지정한다.

entry.next = cur;

hTable[hashValue] = entry;

return 0;

}else {

System.out.println("cursor 값("+ getKey(cur.value) +")이 리스트의 첫번째 값("+ hTable[hashValue].value +")과 다릅니다. pre.next는 현재 들어올 값이 되고, 현재 들어올 값의 next는 커서가 됩니다.");

// 첫번째 노드가 아니면

// 삽입 노드의 다음 노드로 커서노드를 지정하고 전 노드의 다음 노들르 삽입노드로 지정한다.

entry.next = cur;

pre.next = entry;

return 0;

}

// 데이터가 있는 위치를 가져온다.

public int get(int data) {

int key = getKey(data); // 해쉬코드

int hashValue = hashMethod(key); // 인덱스

// 데이터가 있는 인덱스의 첫번째 노드를 얻는다.

Entry cur = hTable[hashValue];

System.out.println("cur===="+cur);

while(true) {

if(cur == null) {

// 인덱스가 비어있다면 -1 반환

return -1;

}else if(getKey(cur.value) == key) {

// 커서의 값과 찾으려는 데이터의 키가 같다면 해당 인덱스 반환

// 근데 이부분 이상한게 value랑 key를 비교하는게 맞나?

// getKey(cur.value) == key 이렇게 각 값의 해쉬코드를 비효해야하는거 아님? 지금이야 데이터 값이 키값이라서 이렇다곤 하지만..음..

return hashValue;

}else if(getKey(cur.value) > key) {

// 커서의 값이 찾으려는 키보다 크면 -1 반환

// 리스트는 작은 값에서 큰 값으로 정렬되어있다.

return -1;

}else {

// 커서의 값이 키보다 작으면 다음 노드로 커서 이동

cur = cur.next;

}

// 데이터가 있는 노드를 반환한다.

private Entry getEntry(int data) {

int key = getKey(data);

int hashValue = hashMethod(key);

// 해쉬테이블의 인덱스의 첫번째 노드와 두번째 노드

Entry pre = hTable[hashValue];

Entry cur = pre.next;

while(true) {

if(cur == null) {

// 커서 노드가 null이면 null 반환

return null;

}else if(getKey(cur.value) == key) {

// 커서 노드의 값이 키와 같으면 전 노드를 반환

return pre;

}else if(getKey(cur.value) > key) {

// 커서의 값이 키보다 크면 null 반환

return null;

}else {

// 커서의 값이 키보다 작으면 커서를 다음으로 이동

pre = cur;

cur = cur.next;

}

// data를 제거

public int remove(int data) {

Entry pre = null;

// 데이터가 있는 노드의 전노드를 가져오고 null이면 -1 반환

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

return -1;

}

// 전 노드가 데이터의 다음노드를 가리키게 한다.

// 데이터 노드를 건너뛰게 연결한다(제거)

Entry cur = pre.next;

pre.next = cur.next;

return 0;

}

public String toString() {

StringBuffer result = new StringBuffer();

Entry cur = null;

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

result.append("[" + i + "]\t");

cur = hTable[i];

if(cur == null) {

result.append("n ");

}else {

while(cur!=null) {

result.append(cur.value + " ::: next=" + cur.next);

cur = cur.next;

}

result.append("\n");

}

return result.toString();

}

Test.java

public class Test {

public static void main(String[] args) {

//DecimalFormat f = new DecimalFormat("###,###.##");

//BigDecimal d = new BigDecimal(456745674.56);

//BigDecimal d = new BigDecimal(456745674);

//System.out.println(f.format(d));

Hash hash = new Hash(5);