[JAVA 더 깊게] 자바의 해쉬(feat. equals 재정의)

개요

프로젝트를 개발하다보면 정말 많이 쓰이는 자료구조 Map이 있다.

자바는 이 Map을 구현하는데 해쉬의 개념을 이용한다.

Set의 HashSet도 있긴하다.

아무튼 이 해쉬는 삽입 삭제 조회의 효율성 세마리 토끼를 모두 잡은 자료구조로써 아주 유용하다.

이 해쉬라는게 어떤 이점이 있는지? 어떤 특성들이 있는지? 그리고 자바에서 어떻게 활용되는지 알아보자.

해쉬의 개념

해쉬는 내부적으로 배열에 데이터를 담아두는데 값 v를 해싱해서 얻은 해쉬주소를 이 배열의 index로 사용해 값 v를 저장한다.

해싱: 값 v를 해시함수를 통해 수치화하는것

 

해쉬

 

이 때문에 선형 구조 (ArrayList , LinkedList)의 단점이었던, 특정 값 v를 찾기위해서 O(N)의 복잡도를 가지며 모든 element를 순회할 필요가 없어졌다.

해쉬 자료구조의 장점과 단점

장점

get(value) 시 value를 해싱해 value가 저장된 index를 바로 찾아낼수있기 때문에 O(1)만에 조회가 가능하다.

해쉬주소를 가지고 index에 바로 접근할수있기때문에 삽입, 삭제 , 조회가 모두 O(1)로 매우 빠르다.

단점

해싱, 배열의 크기, 그리고 충돌을 막기위한 체이닝 기법을 위한 내부적인 연결리스트 등의 리소스가 더 사용된다.

해쉬는 배열 구조로 되어있기때문에 사용하지 않는 공간도 할당되어있다.

해싱을 하는데 리소스가 쓰인다.

충돌방지를 위한 체이닝 리소스가 쓰인다.

 

즉, 해쉬 자료구조는 리소스를 어느정도 포기하고 삽입,삭제,조회의 효율성(O(1))을 극대화한 자료구조이다.

해쉬충돌

서로다른 두 값 v1, v2가 해싱후 결과가 같을 수 있다.

이런상황을 해쉬충돌이라고 한다.

해쉬 충돌을 해결하는 대표적인 방법중 하나가 체이닝 기법이다.

해쉬 충돌은 완전히 피할수없는 것이지만, 최대한 발생하지 않도록 해쉬함수 로직을 잘 짜야한다.

자바는 체이닝을 위해 내부적으로 LinkedList를 가지고있는데, 이때문에 추가 리소스가 든다.

자바에서의 해쉬

어떻게 저장할까?

해쉬는 값 v를 해싱하여 얻어낸 해쉬주소를 index로 사용해 해당 위치에 값v를 저장한다고했다.

이때 값 v를 해싱할때 v의 hashCode() 메소드를 호출하여 얻은 해시코드를 해쉬 주소로 사용한다.

예를들어 문자열 String을 HashSet에 저장할 경우, String의 hashCode()메서드를 호출하여 그 값을 index로 사용하는것이다.

hashCode()는 java.util.Object 클래스에 구현된 메서드인데, String은 이 hashCode()를 Override했다.

hashCode() 를 재정의 할때 주의할점

• hashCode()를 재정의 할땐 반드시 equals도 재정의 해야한다.

Map<Menu,Integer> menus = new HashMap<>();
menus.put(new Menu("치킨", 16_000), 10); //a
menus.put(new Menu("감자튀김", 8_000), 2);
menus.put(new Menu("콜라", 2_000), 7);
 
Menu menu = new Menu("치킨", 16_000); //b
int count = menus.get(menu); //찾기 불가!

menus.get(menu)는 수행되지 않는다.

equals 재정의 전에는 a와 b는 다른 주소를 참조함으로 다른 객체로 인식한다.

그래서 menu와 동일한 key를 찾을수 없는것이다.

필드값이 같다면 같은 객체로 인지하도록 equals를 재정의 해야한다.

사용자 정의 객체를 key로 사용하도록 재정의하기

public class Menu {
    private final String name;
    private final int price;

    public Menu(final String name, final int price) {
        this.name = name;
        this.price = price;
    }

    // equals 재정의
    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (!(o instanceof Menu))
            return false;
        Menu menu = (Menu)o;
        return price == menu.price && Objects.equals(name, menu.name); //필드 값이 같으면 true
    }
    
    // hashcode 재정의
    @Override
    public int hashCode() {
        return Objects.hash(name, price); //필드값을 가지고 hashing
    }
}

1. hashcode를 재정의하여 필드값이 동일하면 같은 해시주소가 나오도록 한다.
2. equals를 재정의하여 필드값이 동일하면 같은 객체로 판단할수있도록 한다.

이 블로그가 친절하게 잘 설명해 두었다.

[Java] equals() & hashcode() 메서드는 언제 재정의해야 할까? (velog.io)

자바에서의 해쉬를 이용한 컬랙션

자바에서 해쉬를 이용한 컬랙션 Map , Set 2가지가 있다.

Set

Set<Person> set = new HashSet<>();

Person 객체를 해싱하여 배열에 저장한다. 단, 집합 자료구조임으로 중복을 허용하지 않는다.

이때 Person 객체의 hashCode()와 equals를 overriding 해야한다.

Map

Map<Person,String> map = new HashMap<>();
Map<Person,String> map = new HashTable<>();  //동기화 지원
Map<Person,String> map = new LinkedHashMap<>();
Map<Person,String> map = new TreeMap<>();

Map은 key & value로 구성되어있는 자료구조이다.

Map은 key를 해싱하여 나온 해쉬주소를 index로 활용해 해당 위치에 value를 저장한다.

Map<String,Person> map = new HashMap<>();

보통은 그냥 편하게 자바에서 이미 hashCode()를 override 한 String, Integer 등의 class를 key로 사용하는데,

적절한 hashCode() override를 통해 사용자 정의 class도 충돌없이 key로 사용되도록 할수있다.

사용자 정의 class를 key로 사용해야하는 상황이 있을 수 있으니 알아둬야한다.

Reference

[Java] equals() & hashcode() 메서드는 언제 재정의해야 할까? (velog.io)

[JAVA] HashSet이란? & 사용법 정리 (tistory.com)

https://www.youtube.com/watch?v=HraOg7W3VAM