요약

해시코드는 객체를 구분하는 정수값입니다.
toString은 객체@해시코드의16진수 변환값을 반환합니다.
equals와 ==은 주소비교입니다.
equals()가 true면 반드시 hashCode()의 값도 같아야 합니다.
equals()연산의 비용이 너무 비쌀 경우 우선적으로 해시코드를 비교하고, 해시코드가 동일한 경우에만 equals()연산을 통해 두 객체가 동일한지 정밀검사를 해볼 수 있습니다.
String 객체는 equals(), hashCode(), toString() 메서드가 오버라이딩 되어 있습니다.
String의 equals()와 hashCode()는 값이 동일하면 해시코드도 같으며 equals()도 true를 반환합니다.
String의 toString()은 주소가 아닌 값을 반환하도록 재정의 되어 있습니다.

HashCode()

.hashCode(): Object에 정의된 메서드로 객체의 해시코드를 반환합니다.
해시코드란 해싱 알고리즘에 사용되는 정수값 입니다.
Object클래스의 hashCode() 메서드는 native로 선언된 네이티브 메서드 입니다.
네이티브 메서드란 OS의 메서드를 말합니다. C언어로 이미 만들어진 메서드를 그대로 사용하는 방식입니다.
해시코드는 객체마다 다른 값을 가집니다.
equals()의 결과가 true인 두 객체는 해시코드 역시 동일해야 합니다.
그렇기 때문에 .equals()를 오버라이딩 했다면 .hashCode()도 함께 오버라이딩 해줘야 합니다.
equals()연산의 비용이 너무 비쌀 경우 우선적으로 해시코드를 비교하고, 해시코드가 동일한 경우에만 equals()연산을 통해 두 객체가 동일한지 정밀검사를 하는 방식으로 해시코드를 활용할 수 있습니다.

Hash table, Hash function

• 해시 함수: 임의의 길이를 가지는 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.
  • 계산이 간단하며, 입력 원소가 해시 테이블 전체에 골고루 저장될수록 좋은 해시 함수입니다.
• 해시값, 해시: 해시함수의 결과로 나온 값을 해시값 또는 해시라고 합니다.
• 해싱: 해시값을 구하는 과정을 해싱이라고 합니다.
• 해시 테이블: 해시함수의 해시값을 key(idnex)로 사용해 value(데이터)를 저장하는 자료구조.
  • 해시 테이블은 O(1)시간으로 데이터에 접근할 수 있습니다.

해시함수의 특징

• 같은 입력값에 대해 같은 출력값이 보장됩니다.
• 서로 다른 입력값으로부터 동일한 출력값이 나올 가능성은 희박합니다.
  • 충돌 저항성: h(x) = h(x')를 만족하는 x와 x'을 찾아내는 건 불가능합니다.
• 일방향성을 갖습니다. 즉, 해시함수의 결과값으로 원본 데이터를 찾는 건 어렵습니다(역상 저항성)

해시의 활용

• 무결성 검사
• 동일 파일 식별 및 수정파일 검출
• DB에 비밀번호 저장
• 블록체인 - 사용자들의 공동장부를 비교할 때 변경사항이 있는지 확인함

해시 충돌 해결방법

• 해시 충돌: 해시 함수가 서로 다른 두 개의 입력값에 대해 같은 해시값을 출력하는 상황입니다.

체이닝 방법

• 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 저장하는 방법입니다.
• 원소를 검색할 때 해당 연결 리스트의 원소들을 차례로 탐색합니다.
• 같은 주소에 너무 많은 데이터가 담기면 해시의 장점을 잃어버리게 됩니다.

개방 주소 방법(open addressing)

• 체이닝과 달리 하나의 주소에 하나의 값만 가지게 만드는 방법입니다.
• 충돌이 발생했을 때 해당 원소를 어떤 공간에 넣느냐에 따라 다양한 방법이 존재합니다.
  • 선형조사(linear probing): 충돌위치로부터 한칸씩 움직이면서 빈 공간을 찾는 방법입니다.
  • 이차원 조사(quadratic probing): 충돌위치로부터 i^2씩 움직이면서 빈 공간을 찾는 방법입니다.
    특정 영역에 원소가 몰려있더라도 그 영역을 빠르게 벗어날 수 있습니다.
  • 더블 해싱: 두 개의 해싱함수를 이용합니다.
    하나의 해시함수는 최초 해시값을 얻을 때에만 사용합니다. 그 결과로 충돌이 발생했을 때 나머지 해시함수를 통해 이동할 폭을 결정합니다.
    두 개의 해시값이 겹칠 확률은 매우 희박하다는 점을 이용한 방법입니다.

toString()

객체를 문자열로 변환하기 위한 메서드 입니다.
클래스이름@주소값이 반환됩니다. 조금 더 정확히는 클래스이름@해시코드를 16진수로 변환한 값이 반환됩니다.

public static toString(){
	return getClass().getName()+"@"+Integer.toHexString(hashCode());
}

클래스이름과 주소값을 활용하는 경우는 적기 때문에 toString()을 오버라이딩하는 경우가 많습니다.

equals()

Object의 .equals()는 두 객체의 주소가 동일한지 비교합니다.

public boolean equals(Object obj){
	return (this == obj);
}

String의equals()

String 객체는 .equals()를 다음과 같이 오버라이딩 하고 있습니다.

    public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

비교 문자열이 널이 아니고, 문자열 값이 모두 동일하다면 true를 반환합니다.
==은 객체의 주소비교, equals()는 일반적으로는 내부적으로 ==을 사용해 객체의 주소를 비교 하지만, String은 오버라이딩을 통해 equals()로 객체의 값을 비교할 수 있습니다.

동등성과 동일성

동등성

• 두 객체의 정보가 같다. 값이 같다는 의미. .equals()연산을 통해 판별 가능

동일성

• 두 객체가 완전히 동일하다. 주소값이 같다는 의미. ==연산을 통해 판별 가능

Literal String vs Object String

여기

확인

import java.util.*;

public class Main {
	public static class NormalObj {
		int x;

		public NormalObj(int x) {
			super();
			this.x = x;
		}

	}

	public static class OverridedOj {
		int x;

		public OverridedOj(int x) {
			super();
			this.x = x;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			OverridedOj other = (OverridedOj) obj;
			if (x != other.x)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return "Student2 [x=" + x + "]";
		}

	}

	public static void main(String[] args) {
		String s1 = "abc";
		String s2 = "abc";
		System.out.println("<Literal String>");
		System.out.println("equals비교: "+s1.equals(s2));
		System.out.println("==비교: "+ (s1 == s2));
		System.out.println("해시코드: " + s1.hashCode()  +"||"+ s2.hashCode());
		System.out.println("toString: " + s1.toString() +"||"+ s2.toString());		
		System.out.println("===================");
		String a1 = new String("abc");
		String a2 = new String("abc");
		System.out.println("<Object String>");
		System.out.println("equals비교: "+a1.equals(a2));
		System.out.println("==비교: "+ (a1 == a2)); 
		System.out.println("해시코드: " + a1.hashCode()  +"||"+ a2.hashCode());
		System.out.println("toString: " + a1.toString() +"||"+ a2.toString());		
		System.out.println("===================");
		NormalObj z1 = new NormalObj(1);
		NormalObj z2 = new NormalObj(1);
		System.out.println("<Personal Class>");
		System.out.println("equals비교: "+z1.equals(z2));
		System.out.println("==비교: "+ (z1 == z2)); 
		System.out.println("해시코드: " + z1.hashCode()  +"||"+ z2.hashCode());
		System.out.println("toString: " + z1.toString() +"||"+ z2.toString());		
		System.out.println("===================");
		OverridedOj zz1 = new OverridedOj(1);
		OverridedOj zz2 = new OverridedOj(1);
		System.out.println("<Overrided Personal Class>");
		System.out.println("equals비교: "+zz1.equals(zz2));
		System.out.println("==비교: "+ (zz1 == zz2)); 
		System.out.println("해시코드: " + zz1.hashCode()  +"||"+ zz2.hashCode());
		System.out.println("toString: " + zz1.toString() +"||"+ zz2.toString());
	}

}

• literal String은 두 변수가 완전히 동일합니다.

• Object String은 재정의된 메서드에 의해 해시코드가 동일하며 equals값도 true가 반환됩니다.
  하지만 ==를 통해 비교한 주소는 다릅니다.

• 일반적인 클래스는 해시코드와 equals의 값이 모두 다릅니다.

• hashCode()와 equals() 오버라이딩을 통해 주소비교가 아닌 값비교를 진행할 수 있습니다.

Integer의 == 비교

실험

public class Main {
	public static void main(String[] args) {
		Integer a = 1;
		Integer b = 1;
		System.out.println(a==b); // true
		
		Integer c = 365;
		Integer d = 365;
		System.out.println(c==d); // false
		
        // 값비교
		System.out.println(a.equals(b)); // true
		System.out.println(c.equals(d)); // true
	}
}

• Integer타입의 a와b 변수에 1을 담은 뒤 ==비교를 하면 true가 나옵니다.
• 같은 방식으로 Integer타입의 c와d 변수에 365를 담은 뒤 ==비교를 하면 false가 나옵니다.

이유

• Integer a = 1;에서 1은 int타입이고 a는 Integer타입으로 둘은 타입이 다릅니다.
• 하지만 auto-boxing에 의해 Integer a = 1;는 컴파일시 자동으로 Integer a = Integer.valueOf(1);이 됩니다.
  • int타입의 1이 Integer타입의 1로 변환됩니다.
• 결국 Integer a = 1;과 Integer a = 365; 모두 Integer.valueOf()과정을 거치게 됩니다.

Integer.valueOf()

• Integer.valueOf()는 i가 IntegerCache.low와 IntegerCache.high사이의 값일때와 그렇지 않을 때 return하는 값이 다릅니다.

  • 즉 우리는 1과 365중 하나는 해당 범위 내에 있는 값이고, 나머지 하나는 해당 범위 밖의 값이라서 결과가 달라졌다는 걸 알게 되었습니다.

• 조금 더 자세히 살펴보면 캐시범위 내에서는 기존에 IntegerCache.cache에 담긴 값을 그대로 반환해주고, 캐시범위를 벗어났을 때에는 return new Integer(i);를 통해 새로운 객체를 반환한다는 사실을 알 수 있습니다.

• IntegerCache.low는 -128, IntegerCache.high는 127입니다. -128 ~ 127의 값만 캐싱하는 이유는 해당 값들이 개발할 때 빈번하게 사용되는 정수값들이기 때문입니다.

기타

Integer의 .equals()역시 String처럼 값을 비교하도록 오버라이딩 되어있습니다.

• 그렇기 때문에 .equals()비교는 -128<=i<=127범위가 아니더라도 값을 비교하기 때문에 a.equals(b)와 c.equals(d) 모두 true를 반환합니다.

결론

• Integer a = 1;은 형변환(auto-boxing)이 일어납니다.
• auto-boxing과정에서 Integer.valueOf()메서드가 사용됩니다.
• Integer.valueOf()메서드는 인자 i가 -128<=i<=127이라면 캐싱된 값을, 그렇지 않다면 새로운 Integer 객체를 반환합니다.
  • 이렇게 값을 캐싱하는 이유는 -128<=i<=127범위의 정수를 개발중에 많이 사용하기 때문입니다.
• Integer의 .equals()는 값을 비교하도록 오버라이딩 되어있습니다.

References

• https://www.youtube.com/watch?v=GfYg3imRZsc
• https://www.youtube.com/watch?v=aOWddxH8WVw
• https://www.youtube.com/watch?v=Vi0hauJemxA
• https://www.youtube.com/watch?v=Mdp6rq4v0_o
• https://www.youtube.com/watch?v=Rpbj6jMYKag
• https://meetup.toast.com/posts/185