11. 해시 - bloodfinger8/AlgorithmStudy GitHub Wiki
해시 문제 https://www.acmicpc.net/problem/5052
해시법은 검색과 더불어 데이터의 추가와 삭제도 효율적으로 수행할 수 있는 방법입니다.
해시 테이블은 hash Map(자바) , Maps , dictionaries(파이썬) , associative arrays(c , php ..) 라는 이름으로 알려져있다~
여러분이 페이스북에 방문한다고 가정해봅시다.
- 페이스북 서버에 요청을 한다.
- 서버는 잠시 생각한 다음 요청한 웹 페이지를 찾아서 여러분에게 보내줍니다.
- 여러분은 웹 페이지를 받습니다.
페이스북은 여러분의 친구들의 활동내역을 모아서 보여주는 기능이 있습니다. 그러면 그 활동 내역을 모으고 보여주는데 시간이 몇 초가 걸립니다. 그러면 여러분들은 시간이 오래걸린다고 생각하겠죠?..
페이스북을 더 빠르게 하면서 동시에 서버가 일을 덜 하게 만들 수 있는 방법은 없을까요??
캐싱을 사용하는 것입니다.
캐싱은 2가지 장점을 가지고 있습니다.
- 구구단을 외우고 있는것처럼 웹페이지를 더 빠르게 보여줍니다. 외우고 있으면 찾아 볼 필요가 없겠죠
- 페이스북 서버가 일을 덜 할것입니다.
데이터를 저장할 위치를 간단한 연상으로 구하는 것으로 , 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할 수 있습니다.
배열의 키 값을 배열의 요솟수 13으로 나눈 나머지로 다시 정리하면 아래 표와 같습니다.
해시값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 아래의 해시 테이블입니다.
버킷이 이미 채워져있는 경우가 있을수 있습니다. 이 경우에서 볼수있듯이 키 값과 해시 값의 대응 관계가 반드시 1대1이라는 보증은 없습니다.(보통 N대 1) 이렇게 버킷이 중복되는 현상을 충돌(collision) 이라고 합니다.
이러한 충돌에 대한 대처로 2가지 방법이 존재합니다.
- 체인법 - 같은 해시 값을 갖는 요소를 연결 리스트로 관리
- 오픈 주소법 - 빈 버킷을 찾을 때 까지 해시를 반복
class ChainHash<K,V> {
private int size; //해시테이블 크기
private Node<K,V>[] table; //해시 테이블
public ChainHash(int capacity) {
table = new Node[capacity];
this.size = capacity;
}
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;
}
class Node<K,V> {
private K key ;
private V data;
private Node<K,V> next;
Node(K key , V data , Node<K,V> next){
this.key = key;
this.data = data;
this.next = next;
}
K getKey(){
return key;
}
V getValue(){
return data;
}
public int hashCode(){
return key.hashCode();
}
}
}