[인프런 김영한 실전 자바 - 중급편] 컬렉션 프레임워크 - HashSet

HashSet

• 해시 함수 (Hash Function) : 임의의 길이의 데이터를 입력받아 고정된 길이의 해시 값(해시 코드)을 출력하는 함수.
  
  • 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다.
  • 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. => 해시 충돌
• 해시 코드 (Hash Code) : 데이터를 대표하는 값을 의미한다.
  • 해시 코드는 보통 해시 함수를 통해 만들어진다.
• 해시 인덱스 (Hash Index) : 데이터의 저장 위치를 결정한다.
  
  • 해시 인덱스는 보통 해시 코드를 사용해서 만든다.
    보통 해시 코드의 결과에 배열의 크기를 나눠 구한다.
• 문자 데이터를 사용하더라도 문자의 고유한 숫자를 통해 해시 함수를 사용해서 정수 기반의 해시 코드로 변환한 덕분에 해시 인덱스를 사용할 수 있다.

---

hashCode()

• 해시 인덱스를 사용하는 해시 자료구조는 데이터 추가 / 검색 / 삭제 성능이 O(1)로 매우 빠르다.
• 해시 자료 구조를 사용하기 위해서는 해시 인덱스를 위 정수로 된 값인 해시 코드가 필요하다.
  • int, Integer 뿐만 아니라 char, String, Double, Boolean 등의 타입과 Member, User와 같은 사용자 정의 타입이 있다. 
  • 이러한 모든 객체가 해시 코드를 표현할 수 있도록 제공하는 기능이 Object.hashCode()이다.

 

• Object.hashCode() : 모든 객체가 해시 코드를 표현할 수 있는 기능을 제공한다.
  
  • 기본 구현은 객체의 참조 값을 기반으로 해시 코드를 생성한다.
    그렇기에 기본적인 Object.hashCode()는 객체의 인스턴스가 다르면 해시 코드도 다르다.
  • Object.hashCode()가 제공하는 기본 구현을 그대로 사용하기 보다는 보통 오버라이딩해서 사용한다.

• 기본적으로 (해시 코드를 16진수로 변환한 값) == (객체의 참조 값)

 

• 자바의 기본 클래스의 해시 코드
  
  • Integer, String 같은 기본 클래스들은 내부 값을 기반으로 해시 코드를 구할 수 있도록 hashCode()를 오버라이딩해두었다.
  • 데이터 값이 같으면 같은 해시 코드를 가지며 정수를 반환하기 때문에 마이너스 값이 나올 수 있다.

 

• hashCode()를 오버라이딩해두면  모든 종류의 객체를 해시 자료 구조에 보관할 수 있다.
  • 해시 자료 구조는 데이터를 해시 인덱스로 저장하고 검색하기 때문에 해시 자료 구조에 데이터를 저장하는 경우 hashCode(), equals()를 반드시 오버라이딩(구현)해야한다.
  • hashCode()는 해시 인덱스를 구해서 값을 저장하고 값이 담긴 인덱스를 찾기 위해서 사용된다.
  • equals()는 해시 충돌이 생기는 경우 해당 인덱스에서 같은 값이 있는지 비교하기 위해서 사용된다.

 

• hashCode(), equals() 오버라이딩의 중요성
  
  • 둘 다 오버라이딩 하지 않는 경우 - 중복 저장이 가능하고 서로 다른 해시 코드를 갖기 때문에 다른 인덱스에 저장되며 같은 값으로 검색을 해도 참조 값이 서로 다르기에 다른 값으로 인식되서 찾을 수 없다.
  • hashCode()만 오버라이딩 하는 경우 - 같은 값을 갖는 데이터는 같은 해시 코드를 갖지만 참조 값이 서로 다르므로 같은 인덱스 내에 같은 데이터가 저장되며 마찬가지로 검색을 해도 찾을 수 없다.
  • equals()만 오버라이딩 하는 경우 - 같은 값을 갖는 데이터를 저장할 때 다른 해시 코드를 갖고 있기에 다른 인덱스에 값이 저장되고 검색할 때도 인덱스 자체가 다르므로 찾을 수 없다.
  • 모두 구현하는 경우 - 같은 값을 갖는 데이터는 해시 코드도 같고 서로 같은 값으로 인식하므로 중복 저장도 되지 않고 검색할 때도 찾을 수 있다.

 

• hashCode()는 항상 오버라이딩할 필요 없이 해시 자료 구조를 사용하는 경우에만 equals()와 함께 오버라이딩해야한다!!

 

• 해시 함수는 해시 코드가 최대한 충돌하지 않도록 설계되어 있다.
  • 해시 충돌은 성능을 안좋게 만들기 때문에 최대한 해시 충돌이 발생하면 안된다.
  • 해시 함수는 복잡한 추가 연산으로 다양한 범위의 해시 코드를 만들기에 해시 충돌할 가능성이 낮아지고 해시 자료 구조를 사용할 때 성능이 개선된다.
  • 좋은 해시 함수는 해시 코드가 한 곳에 몰리지 않고 균일하게 분포하는 것이 좋다.
    그래야 해시 인덱스가 골고루 분포되기 때문에 성능 최적화가 가능하다.

---

출처: [인프런 김영한 실전 자바 - 중급편]

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2/dashboard

김영한의 실전 자바 - 중급 2편 강의 | 김영한 - 인프런