코자개 - Hash

 

Hash

- HashMap<K,V>

= 키를 입력하면 그에 해당하는 값을 빠르게 꺼낼 수 있는 자료구조

 

put(key,value) : 값 저장

get(key) : 값 꺼내기

containsKey(key) : 존재하는지 확인

getOrDefault(key, default) : 없으면 기본값 반환 

 

 

 

Hashing 

- 키 값을 해시 함수에 넣어서 배열의 인덱스를 계산해 저장하는 구조이다.

-> HashMap 내부에는 실제로 배열이 있다.

 

?? 배열의 인덱스를 어케 정해? = 키를 해싱해서 정함

 

Map<Integer, Integer> map = new HashMap<>();
map.put(1001, 5);

 

예를 들어 배열의 크기를 16이라고 가정하면 1001%16 = 9  -> 배열의 9번 칸에 5 저장

 

 

map.put(1001, 10);

 

만약 같은 키를 put 하면 ? 

-> 1001%16 = 9 이므로 인덱스는 9 , 근데 key 중복은 허용을 안 하므로 값을 덮어쓴다.

 

 

 

 

Hash 충돌

map.put(17, 1);
map.put(33, 2);  // 둘 다 hash % 16 = 1

 

근데 이렇게 key는 다르지만 인덱스(1로)가 같을 때 충돌이 발생한다. 

 

-> 이는 내부적으로 연결 리스트나 트리 구조로 충돌을 해결한다 = Seperate Chaining이라고 함

 

 

 

 

Hashing  : 키를 숫자로 바꾸는 과정 (hashCode())

배열 위치 계산 : hash % 배열크기로 위치 결정

충돌 처리 : 같은 인덱스에 여러 값이 오면 리스트/ 트리로 저장

HashMap : 빠른 조회/ 저장 가능 O(1) 수준

 

 

 

 

**[hashCode()] 

- 객체의 내용 기반 고유 숫자를 생성하는 메서드이다.

- 인덱스가 아니라 고유 숫자일 뿐이다.

Point p = new Point(1, 2);
int hash = p.hashCode();  // 예: 12345678

 

 

- 진짜 배열 인덱스 구하는 방법

hash = 12345678
index = 12345678 % 16 = 14

 

-> 14가 진짜 배열 인덱스임.

---

 

 

[오버라이딩]

- HashMap이나 HashSet의 내부 동작

1) hashCode()로 위치를 찾고

2) 해당 위치에 여러 객체가 있으면 equals()로 동일 객체인지 판단

 

 

 

** 오버라이딩 안 한 경우

class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x; this.y = y;
    }
}

Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
set.add(new Point(1, 2));  // 중복처럼 보이지만, 실제로는 다른 객체로 인식됨!
System.out.println(set.size()); // 결과: 2

 

 

** 오버라이딩 한 경우

class Point {
    int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // hashCode 오버라이딩
    @Override
    public int hashCode() {
        return 31 * x + y;
    }

    // equals 오버라이딩
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return this.x == other.x && this.y == other.y;
    }
}

 

 

즉, hashCode()는 객체를 해시값으로 변환하며 같은 내용이면 같은 해시값이 필요해서 오버라이딩 해야함.

equals()는 객체 내용을 비교하며 중복 판단, 같은 객체인지 결정하기 위해 오버라이딩 해야함.

 

 

 

---

TreeSet은 중복 x, value 가 정렬

-> 정렬이 필요할 때 빼고는 HashSet보다는 많이 걸리므로 HashSet 쓰자