7-2. HashSet

직접 구현하는 해시 코드

---

• Member의 경우 회원의 id가 같으면 논리적으로 같은 회원으로 표현할 수 있음

• 따라서 회원 id를 기반으로 동등성을 비교하도록 equals를 재정의해야 함

• 여기에 hashCode()도 같은 원리가 적용됨

  • 회원 id가 같으면 논리적으로 같은 회원으로 표현할 수 있음
  • 따라서 회원 id를 기반으로 해시 코드를 생성해야 함

Member의 hashCode() 구현

• Member의 hashCode()를 재정의
• hashCode()를 재정의할 때 Objects.hash()에 해시 코드로 사용할 값을 지정해주면 쉽게 해시 코드를 생성할 수 있음
• hashCode()를 재정의하지 않으면 Object가 기본적으로 제공하는 hashCode()를 사용하게 됨
  • 이것은 객체의 참조값을 기반으로 해시 코드를 제공함
  • 따라서 회원 id가 같아도 인스턴스가 다르면 다른 해시 코드를 반환하게 됨
• hashCode()를 id를 기반으로 재정의한 덕분에 인스턴스가 달라도 id 값이 같으면 같은 해시 코드를 반환함
  • 따라서 인스턴스가 다른 member1, member2 둘 다 같은 해시 코드를 반환하는 것을 확인할 수 있음

정리

• 자바가 기본으로 제공하는 클래스 대부분은 hashCode()를 재정의해두었음
• 객체를 직접 만들어야 하는 경우에 hashCode()를 재정의하면 됨
• hashCode()만 재정의하면 필요한 모든 종류의 객체를 해시 자료 구조에 보관할 수 있음
• 정리하면 해시 자료 구조에 데이터를 저장하는 경우 hashCode()를 구현해야 함

직접 구현하는 Set2 - MyHashSetV2

---

hashCode()를 사용해서 모든 데이터 타입을 저장할 수 있는 MyHashSetV2

• 자바의 hashCode()를 사용하면 타입과 관계없이 해시 코드를 편리하게 구현할 수 있음

package collection.set;
 
import java.util.Arrays;
import java.util.LinkedList;
 
public class MyHashSetV2 {

 	static final int DEFAULT_INITIAL_CAPACITY = 16;
    
 	private LinkedList<Object>[] buckets;
    
 	private int size = 0;
 	private int capacity = DEFAULT_INITIAL_CAPACITY;
 	
    public MyHashSetV2() {
 		initBuckets();
    }
    
 	public MyHashSetV2(int capacity) {
 		this.capacity = capacity;
 		initBuckets();
    }
    
 	private void initBuckets() {
        buckets = new LinkedList[capacity];
 		for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }
    
	public boolean add(Object value) {
 		int hashIndex = hashIndex(value);
 		LinkedList<Object> bucket = buckets[hashIndex];
        
 		if (bucket.contains(value)) {
 			return false;
        }
        
        bucket.add(value);
        size++;
        
 		return true;
    }
    
 	public boolean contains(Object searchValue) {
 		int hashIndex = hashIndex(searchValue);
 		LinkedList<Object> bucket = buckets[hashIndex];
        
 		return bucket.contains(searchValue);
    }
    
 	public boolean remove(Object value) {
 		int hashIndex = hashIndex(value);
 		LinkedList<Object> bucket = buckets[hashIndex];
        
 		boolean result = bucket.remove(value);
 		
        if (result) {
            size--;
 			return true;
        } 
		else {
 			return false;
        }
    }
    
 	private int hashIndex(Object value) {
 		//hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
 		return Math.abs(value.hashCode()) % capacity;
    }
    
 	public int getSize() {
 		return size;
    }
    
    @Override
 	public String toString() {
 		return "MyHashSetV2{" +
 			"buckets=" + Arrays.toString(buckets) +
			", size=" + size +
 			", capacity=" + capacity +
 			'}';
    }
    
}

private LinkedList<Object>[]buckets

• MyHashSetV1은 Integer 숫자만 저장할 수 있음
  • 여기서는 모든 타입을 저장할 수 있도록 Object를 사용함
  • 추가로 저장, 검색, 삭제 메서드의 매개변수도 Object로 변경했음

hashIndex()

• hashIndex() 부분이 변경됨

• 먼저 Object의 hashCode()를 호출해서 해시 코드를 찾고 찾은 해시 코드를 배열의 크기로 나머지 연산을 수행함

  • 이렇게 해시 코드를 기반으로 해시 인덱스를 계산해서 반환함

• Object의 hashCode()를 사용한 덕분에 모든 객체의 hashCode()를 구할 수 있음

  • 물론 다형성에 의해 오버라이딩 된 hashCode()가 호출됨

• hashCode()의 실행 결과로 음수가 나올 수 있는데, 배열의 인덱스로 음수는 사용할 수 없음

  • Math.abs()를 사용하면 마이너스를 제거해서 항상 양수를 얻을 수 있음

 package collection.set;
 
 public class MyHashSetV2Main1 {
 
 	public static void main(String[] args) {
    
	 	MyHashSetV2 set = new MyHashSetV2(10);
        set.add("A");
        set.add("B");
        set.add("C");
        set.add("D");
        set.add("AB");
        set.add("SET");
 		System.out.println(set);

 		System.out.println("A.hashCode=" + "A".hashCode());
 		System.out.println("B.hashCode=" + "B".hashCode());
 		System.out.println("AB.hashCode=" + "AB".hashCode());
 		System.out.println("SET.hashCode=" + "SET".hashCode());
        
		//검색
		String searchValue = "SET";
 		boolean result = set.contains(searchValue);
 		System.out.println("set.contains(" + searchValue + ") = " + result);
        
    }
}

실행 결과

MyHashSetV2{buckets=[[], [AB], [], [], [], [A], [B, SET], [C], [D], []], size=6, 
capacity=10}
A.hashCode=65
B.hashCode=66
AB.hashCode=2081
SET.hashCode=81986
bucket.contains(SET) = true

• 자바 String은 hashCode()를 재정의해 두었고, 이 값을 사용하면 됨

• hashIndex(Object value)에서 value.hashCode()를 호출하면 실제로는 String에서 재정의한 hashCode()가 호출됨

• 이렇게 반환된 해시 코드를 기반으로 해시 인덱스를 생성함

• 참고로 자바의 해시 함수는 단순히 문자들을 더하기만 하는 것이 아니라 더 복잡한 연산을 사용해서 해시 코드를 구함

직접 구현하는 Set3 - 직접 만든 객체 보관

---

직접 만든 객체를 set에 보관

• MyHashSetV2는 Object를 받을 수 있음
• 따라서 직접 만든 Member와 같은 객체도 보관할 수 있음
• 여기서 주의할 점은 직접 만든 객체가 hashCode(), equals() 두 메서드를 반드시 구현해야 한다는 점임

 package collection.set;
 
 import collection.set.member.Member;
 
 public class MyHashSetV2Main2 {
 
 	public static void main(String[] args) {
    
 		MyHashSetV2 set = new MyHashSetV2(10);
		Member hi = new Member("hi");
 		Member jpa = new Member("JPA"); //대문자 주의!
 		Member java = new Member("java");
 		Member spring = new Member("spring");
        
 		System.out.println("hi.hashCode() = " + hi.hashCode());
 		System.out.println("jpa.hashCode() = " + jpa.hashCode());
 		System.out.println("java.hashCode() = " + java.hashCode());
 		System.out.println("spring.hashCode() = " + spring.hashCode());
        
        set.add(hi);
        set.add(jpa);
        set.add(java);
        set.add(spring);
 		System.out.println(set);
    
 		//검색
		Member searchValue = new Member("JPA");
 		boolean result = set.contains(searchValue);
		System.out.println("set.contains(" + searchValue + ") = " + result);
        
    }
}

• 예제에서 "JPA"가 대문자로 만들어진 것에 주의

실행결과

hi.hashCode() = 3360
jpa.hashCode() = 73690
java.hashCode() = 3254849
spring.hashCode() = -895679956

MyHashSetV2{buckets=[[Member{id='hi'}, Member{id='JPA'}], [], [], [], [], [], 
[Member{id='spring'}], [], [], [Member{id='java'}]], size=4, capacity=10}

//검색
bucket.contains(Member{id='JPA'}) = true

• Member의 hashCode()를 id 값을 기반으로 재정의해 둠
• hashIndex(Object value)에서 value.hashCode()를 호출하면 실제로는 Member에서 재정의한 hashCode()가 호출됨
• 이렇게 반환된 해시 코드를 기반으로 해시 인덱스를 생성함

equals() 사용처

• "JPA"를 조회할 때 해시 인덱스는 0임

  • 따라서 배열의 0번 인덱스를 조회함

• 여기에는 [hi, JPA]라는 회원 두 명이 있음

  • 이것을 하나하나 비교해야 함
  • 이때 equals()를 사용해서 비교함

• 따라서 해시 자료 구조를 사용할 때는 hashCode()는 물론이고, equals()도 반드시 재정의해야 함

  • 참고로 자바가 제공하는 기본 클래스들은 대부분 hashCode(), equals()를 함께 재정의해 둠

강의 출처 : 김영한의 실전 자바 - 중급 2편