Hash(ing) 시험 유형들이 있음 → 다른 유형과 섞여서 나오는 편 ⇒ 어떤 데이터를 관리하고 저장하기 위한 [고유의 식별 코드]를 만드는 것
정렬된 형태를 보장하지 않음
들어온 상태도 보장하지 않음
시간복잡도 :
→ 중복된 hash → hash collision 이게 많을수록 O(N)
→ int로 고유 식별번호만 만들어서 사용하면 O(1) *amortized
Key는 최대한 int로 사용하길 권장
→ 불가피한 상황에서는 문자열을 쓸수밖에 없음
→ 가능하면 일단 문자열로 먼저 풀고 마지막에 int로 변환하는 최적화 필요
→ iteration 가능 → but, 최대한 기피해야함
키워드 : [기록]
→ DAT를 쓰지 못하는 경우 → HashMap 사용
// 생성
HashMap<Integer, String> hm = new HashMap<>();
// 삽입
hm.put(3, "three");
hm.put(1, "one");
hm.put(4, "four");
hm.put(2, "two");
// 접근
System.out.println(hm.get(3));
// 삭제
hm.remove(4);
static class Node{
int r;
int c;
Node(int r, int c){
this.r = r;
this.c = c;
}
}
public static void main(String[] args) throws Exception{
HashMap<Node, Integer> nhm = new HashMap<>();
nhm.put(new Node(0, 0), 0);
nhm.put(new Node(1, 1), 1);
nhm.put(new Node(1, 10), 11);
nhm.put(new Node(10, 11), 21);
System.out.println(nhm.get(new Node(0, 0))); // null 출력됨
// why?
// 해시코드가 다름. => 오버라이딩 필요
}
정렬형태 vs 정렬 x
compareTo 하나로 비교 vs HashCode + equals
HashCode : 객체의 식별 번호
String a = "miracom";
String b = "samsung";
System.out.println(a.hashCode());
System.out.println(b.hashCode());
⇒ 배열 인덱스의 주소를 찾아줌.
Treemap이랑 HashMap은 형제이지만 전혀 다른 색깔을 가진 친구들 → 절대 혼동하면 안됨
static class Node{
int r;
int c;
Node(int r, int c){
this.r = r;
this.c = c;
}
@Override
// 모든 노드에 대한 해시코드는 1로 나오도록 변경
public int hashCode(){
return 1;
}
}
public static void main(String[] args) throws Exception{
HashMap<Node, Integer> nhm = new HashMap<>();
nhm.put(new Node(0, 0), 0);
nhm.put(new Node(1, 1), 1);
nhm.put(new Node(1, 10), 11);
nhm.put(new Node(10, 11), 21);
nhm.put(new Node(0, 0), 2); // 갱신 안되고 새로 추가됨
// why?
// 해시코드가 동일한 배열 내에 있는 모든 값을 비교를 해줘야 하는데
// 비교할 능력이 안됨.
// 비교는 equals로 하기 때문.
System.out.println(new Node(0, 0).equals(new Node(0, 0)); // 출력 false
// => 지금의 equals는 아래 코드로 들어가기 때문
// public boolean equals(Object obj){
// return (this == obj);
// }
}
static class Node{
int r;
int c;
Node(int r, int c){
this.r = r;
this.c = c;
}
@Override
// 모든 노드에 대한 해시코드는 1로 나오도록 변경
public int hashCode(){
return 1;
}
@Override
//
public boolean equals(Object o){
if (this == o)
return true;
if (this.getClass() !- o.getClass())
return false;
Node ob = (Node) o;
return ob.y == y && ob.x == x;
}
}
public static void main(String[] args) throws Exception{
HashMap<Node, Integer> nhm = new HashMap<>();
nhm.put(new Node(0, 0), 0);
nhm.put(new Node(1, 1), 1);
nhm.put(new Node(1, 10), 11);
nhm.put(new Node(10, 11), 21);
nhm.put(new Node(0, 0), 2); // 정상적으로 갱신되는 것을 볼 수 있음.
System.out.println(new Node(0, 0).equals(new Node(0, 0)); // 출력 true
}
삽입 :
static class Node{
int r;
int c;
Node(int r, int c){
this.r = r;
this.c = c;
}
@Override
// 모든 노드에 대한 해시코드는 1로 나오도록 변경
// 얘가 본체
public int hashCode(){
//return 수식; // 모두 고유의 hashcode를 생성할 수 있다면 O(1)로 가능
// 이 좌표 체계가 모두 중복이 되지 않도록 하는 hashCode 구성
// -> 좌표체계는 0~100까지 있다. (0, 0) ~ (100, 100)
// #1. 좌표 % 100??
// #2. (100-x) + " " (100-y) => x + "" + y
// 결합
// x + y
// return r * 1000 + c;
return r * 100 + x;
}
@Override
//
public boolean equals(Object o){
if (this == o)
return true;
if (this.getClass() !- o.getClass())
return false;
Node ob = (Node) o;
return ob.y == y && ob.x == x;
}
}
public static void main(String[] args) throws Exception{
HashMap<Node, Integer> nhm = new HashMap<>();
nhm.put(new Node(0, 0), 0);
nhm.put(new Node(1, 1), 1);
nhm.put(new Node(1, 10), 11);
nhm.put(new Node(10, 11), 21);
nhm.put(new Node(0, 0), 2); // 정상적으로 갱신되는 것을 볼 수 있음.
System.out.println(new Node(0, 0).equals(new Node(0, 0)); // 출력 true
// ====================================================================
// Key : Node => 고유 식별 번호 담는다
// value : 원래 넣으려고 했던거
HashMap<Integer, Integer> nn = new HashMap<>();
// 이렇게 쓴다면 => 절대로 중복이 생성되어서는 안됨
int hash = getHash(new Node(0, 0));
nn.put(hash, 0);
}
구슬치기 : 해싱 + 구현