[item#11] equals를 재정의하려거든 hashCode도 재정의하라

• equals 비교에 사용하는 정보가 변경되지 않았다면 hashCode는 매번 같은 값을 리턴해야한다.(변경되거나, 애플리케이션을 다시 실행했다면 달라질 수 있다.)
• 두 객체에 대한 equals가 같다면, hashCode의 값도 같아야한다.
• 두 객체에 대한 equals가 다르더라도, hashCode의 값은 같을 수 있지만 해시테이블 성능을 고려해 다른 값을 리턴하는 것이 좋다.
• hashCode를 구현할 떄는 equals에서 사용하는 모든 필드들을 사용해서 hashCode를 반영해야한다.

같은 인스턴스인데 다른 hashCode

public class PhoneNumber {
    private final short areaCode, prefix, lineNum;

    public PhoneNumber(int areaCode, int prefix, int lineNum) throws IllegalAccessException {
        this.areaCode = rangeCheck(areaCode, 999, "area code");
        this.prefix = rangeCheck(prefix, 999, "prefix");
        this.lineNum = rangeCheck(lineNum, 9999, "lineNum");
    }

    private static short rangeCheck(int val, int max, String arg) throws IllegalAccessException {
        if (val < 0 || val > max) {
            throw new IllegalAccessException(arg + ": " + val);
        }
        return (short) val;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;

        if (!(obj instanceof PhoneNumber))
            return false;
        PhoneNumber pn = (PhoneNumber) obj;
        return pn.lineNum == lineNum && pn.prefix == prefix && pn.areaCode == areaCode;
    }

    public static void main(String[] args) throws IllegalAccessException {
        Map<PhoneNumber, String> map = new HashMap<>();
        PhoneNumber number1 = new PhoneNumber(123, 456, 7890);
        PhoneNumber number2 = new PhoneNumber(123, 456, 7890);

        // TODO 같은 인스턴스인데 다른 hashCode
        System.out.println(number1.equals(number2));
        System.out.println(number1.hashCode());
        System.out.println(number2.hashCode());

        map.put(number1, "hong");
        map.put(number2, "min");

        System.out.println(map.get(number1));
        System.out.println(map.get(number2));
    
    // true
    // 1694819250
    // 1365202186
    // min
    // hong

    
    }

}

HashMap에 get, put과정 이해

• put을 할때 hashcode라는 메서드를 실행해서 어느 버켓에 넣을지 정하고 넣음
• get을 할때도 key에 대한 hashcode값을 먼저 가져와서 해시에 해당하는 버켓에 해당하는 object를 꺼내는 과정

다른 인스턴스인데 같은 hashCode를 쓴다면?

@Override
public int hashCode() {
    return 42; //  무조건 같은 hashCode를 return 하도록 함.
}

public static void main(String[] args) throws IllegalAccessException {
    Map<PhoneNumber, String> map = new HashMap<>();
    PhoneNumber number1 = new PhoneNumber(123, 456, 7890);
    PhoneNumber number2 = new PhoneNumber(456, 789, 1111);

    // TODO 같은 인스턴스인데 다른 hashCode
    System.out.println(number1.equals(number2));
    System.out.println(number1.hashCode());
    System.out.println(number2.hashCode());

    map.put(number1, "hong");
    map.put(number2, "min");

    System.out.println(map.get(number2));
    
    // false
    // 42
    // 42
    // min

  

HashMap 내부의 LinkedList

1. hash collision이 일어남
2. 해시 버켓에 들어있는 object를 LinkedList로 만듬
3. 버켓에서 꺼내면 LinkedList로 나옴
4. 해시코드가 같으면 모두 같은 버켓으로 들어감
5. 그 버켓안에 들어있는 LinkedList에 쭉 들어감
6. 그 LinkedList에서 꺼내서 equals로 비교를 하게됨
7. hashmap을 쓰는 장점이 없어진다.

hashCode 구현 방법

@Override
public int hashCode() {
    int result = Short.hashCode(areaCode);
    result = 31 * result + Short.hashCode(prefix);
    result = 31 * result + Short.hashCode(lineNum);
    return result;

}

1. 핵심 필드 하나의 값의 해쉬값을 계산해서 result값을 초기화한다.
2. 기본 타입은 Type.hashCode(해당하는 Type), 참조 타입은 해당 필드의 hashCode
   배열은 모든 원소를 재귀적으로 위의 로직을 적용하거나, Array
   result = 31 * result + 해당 필드의 hashCode 계산값
3. result를 리턴한다.
   

31을 곱해주는 이유??

1. 짝수를 가지고 연산을 하면 끝이 0으로 채워지면서 숫자가 왼쪽으로 밀리면서 날아갈수 있다.
2. 해싱을 할 때 해싱충돌이 가장 적은 숫자가 31이다.
3. 별다른 이유가 없다면 일반적으로 31을 쓰는것이 좋다.

위와 같이 쓰지않고 아래와 같이 사용할 수 있다.

@Override
public int hashCode() {
    return Objects.hash(areaCode, prefix, lineNum);
}
    
===> Objects Class
 public static int hash(Object... values) {
        return Arrays.hashCode(values);
    }
    
===> Arrays.hashCode()
public static int hashCode(Object a[]) {
if (a == null)
    return 0;

int result = 1;

for (Object element : a)
    result = 31 * result + (element == null ? 0 : element.hashCode());

return result;
}

hash 캐싱

해싱을 하려는 instance가 불변 객체이고, 해싱을 하는 연산이 많다면 밑에와 같이 캐싱을 할 수 있다.
지연초기화 기법을 사용할 때, 주의할점은 멀티스레드 안정성을 고려해야한다.

private final short areaCode, prefix, lineNum;
private int hashCode;

@Override
public int hashCode() {
    int result = hashCode;
    if (result == 0) { // 여러 스레드가 동시에 들어올 수 있음.  
        result = Objects.hash(areaCode, prefix, lineNum);
    }
    return result;
}

• 가장 좋은 방법은 롬북의 @EqualsAndHashCode를 사용하는 것이 사용편의점 관점에서 좋다.
• hashcode를 직접 작성하면, test도 해야함. equals test도 마찬가지.
• 어떻게 hashCode를 작성하는지를 외부로 나타내지 않을수 있다.

멀티 스레드 환경에서 안전한 코드, Thread-safety !!

• 가장 안전한 방법은 여러 스레드 간에 공유하는 데이터가 없는 것!
• 공유하는 데이터가 있다면:
  • Synchronization
  • ThreadLocal
  • 불변 객체 사용
  • Synchronized 데이터 사용
  • Concurrent 데이터 사용

private int hashCode;

    @Override
    public int hashCode() {
        int result = hashCode;
        if (result == 0) {
            result = Objects.hash(areaCode, prefix, lineNum);
        }
        return result;
    }

위 코드에서는 멀티스레드에 안전한 코드는 아니지만, Objects.hash(areaCode, prefix, lineNum);가 항상 같은 값을 return(멱등성)하므로
사실상 멀티스레드에 안전한 코드

Thread safe code

Synchronized block

@Override
    public synchronized int hashCode() {
        int result = hashCode;
        if (result == 0) {
            result = Objects.hash(areaCode, prefix, lineNum);
        }
        return result;
    }

위 메서드의 문제점 : 성능,

Double Checking Lock

    // cpu cache에 data를 저장하는데, 캐싱한 데이터를 읽어오는 것이 아닌
    // main 메모리에 data를 저장하고 읽어옴
    private volatile int hashCode;
  
@Override
    public int hashCode() {
        if (this.hashCode != 0) {
            return hashCode;
        }

        synchronized (this) {
            int result = hashCode;
            if (result == 0) {
                result = Objects.hash(areaCode, prefix, lineNum);
            }
            return result;
        }
    }

성능상의 문제점 개선!

ThreadLocal

한 Thread 내에서만 공유할수있는 data를 사용하게 한다.
@Tranctional을 쓸때 ThreadLocal을 쓴다.

불변 객체 사용

불변객체도 Thread safe하다.

public class PhoneNumber {
    private final short areaCode, prefix, lineNum;

    public PhoneNumber(int areaCode, int prefix, int lineNum) throws IllegalAccessException {
        this.areaCode = rangeCheck(areaCode, 999, "area code");
        this.prefix = rangeCheck(prefix, 999, "prefix");
        this.lineNum = rangeCheck(lineNum, 9999, "lineNum");
    }

    private static short rangeCheck(int val, int max, String arg) throws IllegalAccessException {
        if (val < 0 || val > max) {
            throw new IllegalAccessException(arg + ": " + val);
        }
        return (short) val;
    }
}

Concurrent 사용

HashTable은 Thread safe하지만, HashMap은 ThreadSafe하지 않다.

Map<String, String> concurrentMap = new ConcurrentHashMap<>();

동시성을 허용하는 Type

read를 할 때는 Thread safe하지않게 허용!
write를 할 땐 다른 Thread에서 read가능!!

example) 하나의 Thread에서 Write를 할 시점엔 다른 Thread에서 read를 하지 못한다.

• 자바 8에서 해시 충돌시 성능 개선을 위해 내부적으로 동일한 버켓에 일정 개수 이상의 엔트리가 추가되면, 연결 리스트 대신 이진 트리를 사용하도록 바뀌었다.
• 연결 리스트에서 어떤 값을 찾는데 걸리는 시간은?
• 이진 트리에서 어떤 값을 찾는데 걸리는 시간은?

LinkedList에서 처음이나 끝에 넣는 시간 : O(1)
LinkedList에서 어떤 값을 찾는데 걸리는 시간 : O(n)
이진트리에서 어떤 값을 찾는데 걸리는 시간 : O(log(n))

왜 LinkedList였을까?
ArrayList는 size를 주고 그 만큼의 공간을 가져야한다.
LinkedList는 하나의 Reference를 사용하면 됨.(?)
공간의 효율성을 따졌다.

https://www.nextree.co.kr/p6506/

https://jwdeveloper.tistory.com/280