컬렉션 프레임워크_Hash Set

이동건 (불꽃냥펀치)·2024년 12월 4일
부트캠프 이후자바자바 자료구조자바의 기본
0

구현으로 알아보는 HashSet

MyHashSetV1

이전의 MyHashSet은 데이터를 추가할 때 중복 데이터가 있는지 체크하는 부분에서 O(n)으로 성능이 좋지않았다. 이렇게 느린 MyHashSetV0을 Hash 알고리즘을 이용해서 평균 O(1)로 개선해보자. 

private void initBuckets() {
          buckets = new LinkedList[capacity];
          for (int i = 0; i < capacity; i++) {
              buckets[i] = new LinkedList<>();
          }
}


public boolean add(int value) {
          int hashIndex = hashIndex(value);
          LinkedList<Integer> bucket = buckets[hashIndex];
          if (bucket.contains(value)) {
              return false;
          }
          bucket.add(value);
          size++;
          return true;
    }
    
    
    public boolean contains(int searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<Integer> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
	}
    
    
    public boolean remove(int value) {
        int hashIndex = hashIndex(value);
        LinkedList<Integer> bucket = buckets[hashIndex];
        boolean result = bucket.remove(Integer.valueOf(value));
        if (result) {
			size--;
            return true;
        } else {
            return false;
        }
	}
    
    
    private int hashIndex(int value) {
        return value % capacity;
	}
    
    
    public int getSize() {
        return size;
	}
  • buckets: 연결 리스트를 배열로 사용한다.
    • 배열안에 연결 리스트가 들어있고, 연결 리스트안에 데이터가 저장된다.
    • 해시 인덱스가 충돌이 발생하면 같은 연결 리스트 안에 여러 데이터가 저장된다.
  • initBuckets()
    • 연결 리스트를 생성해서 배열을 채운다. 배열의 모든 인덱스 위치에는 연결 리스트가 들어있다.
  • add(): 해시 인덱스를 사용해서 데이터를 보관한다.
  • contains(): 해시 인덱스를 사용해서 데이터를 확인한다.
  • remove(): 해시 인덱스를 사용해서 데이터를 제거한다.

남은 문제
해시 인덱스를 사용하려면 데이터의 값을 배열의 인덱스로 사용해야 하지만 배열의 인덱스는 숫자만 사용할 수 있다. 숫자가 아닌 문자열 데이터를 저장할 때는 어떻게 해야할까?


문자열 해시 코드

 	static int hashCode(String str) {
 
          char[] charArray = str.toCharArray();
          int sum = 0;
          for (char c : charArray) {
				sum += c; 
          }
          
			return sum; 
       }
       
      static int hashIndex(int value) {
          return value % CAPACITY;
          } 
          
		}

실행결과

  hash(A) = 65
  hash(B) = 66
  hash(AB) = 131
  hashIndex(A) = 5
  hashIndex(B) = 6
  hashIndex(AB) = 1

모든 문자는 본인만의 고유한 숫자로 표현할 수 있다. 예를들어서 'A' 는 65 , 'B' 는 66 으로표현된다.가장단순하 게 char 형을 int 형으로 캐스팅하면 문자의 고유한 숫자를 확인할 수 있다.

용어정리

해시함수

  • 해시함수는 임의의 데이터를 입력받아 고정된 길이의 해시 코드를 출력하는 함수이다.
  • 같은 데이터를 입력하면 항상 같은 해시코드가 출력된다.
  • 다른 데이터를 입력해도 같은 해시코드가 출력될 수 있는데, 이를 해시 충돌이라한다.
    • "BC" => B(66) + C(67) = 133
    • "AD" => A(65) + D(68) = 133

해시코드

  • 해시 코드는 데이터를 대표하는 값을 뜻하며, 보통 해시 함수를 통해 만들어진다.
  • 데이터 A의 해시코드는 65
  • 데이터 AB의 해시코드는 131

해시 인덱스

  • 해시 인덱스는 데이터의 저장위치를 결정한다.
  • 보통 해시 코드의 결과에 배열의 크기를 나눠 구한다.


자바의 hashCode()

해시 인덱스를 사용하는 해시 자료 구조는 성능이 O(1)로 매우 빠르다. 그런데 해시 자료구조를 사용하려면 해시코드가 필요하지만, 자바에서는 char , String , Double , Boolean 등 수 많은 타입이 있을뿐만 아니라 개발자가 직접 정의한 Member , User 와 같은 사용자 정의 타입도 있다. 이 모든 타입을 해시 자료 구조에 저장하려면 모든 객체가 숫자 해시 코드를 제공할 수 있어야 한다.

Object.hashCode()

public class Object {
    public int hashCode();
}
  • 이 메서드를 그대로 사용하기 보다 오버라이딩해서 사용한다.
  • 이 메서드의 기본 구현은 객체의 참조값을 기반으로 해시 코드를 생성한다.
  • 객체의 인스턴스가 다르면 해시 코드도 다르다.
package collection.set.member;
  import java.util.Objects;
  public class Member {
      private String id;
      public Member(String id) {
          this.id = id;
	}
      public String getId() {
          return id;
	}
      @Override
      public boolean equals(Object o) {
          if (this == o) return true;
          if (o == null || getClass() != o.getClass()) return false;
          Member member = (Member) o;
          return Objects.equals(id, member.id);
	}
      @Override
      public int hashCode() {
          return Objects.hash(id);
      }
  • 여기서는 Member의 id 값을 기준으로 equals 비교를 하고,hashCode도 생성한다.

예제

public class JavaHashCodeMain {
	public static void main(String[] args) {

//Object의 기본 hashCode는 객체의 참조값을 기반으로 생성

		Object obj1 = new Object();
        Object obj2 = new Object(); 
        System.out.println("obj1.hashCode() = " + obj1.hashCode()); 
        System.out.println("obj2.hashCode() = " + obj2.hashCode());
        //각 클래스마다 hashCode를 이미 오버라이딩 해두었다.
        Integer i = 10;
        String strA = "A";
        String strAB = "AB";
        System.out.println("10.hashCode = " + i.hashCode()); 
        System.out.println("'A'.hashCode = " + strA.hashCode()); 
        System.out.println("'AB'.hashCode = " + strAB.hashCode());
        //hashCode는 마이너스 값이 들어올 수 있다.

        System.out.println("-1.hashCode = " + Integer.valueOf(-1).hashCode());
        //둘은 같을까 다를까?, 인스턴스는 다르지만, equals는 같다. 
        Member member1 = new Member("idA");
        Member member2 = new Member("idA");
        
        

        System.out.println("(member1 == member2) = " + (member1 == member2)); 
        System.out.println("member1 equals member2 = " +member1.equals(member2));
        
       	System.out.println("member1.hashCode() = " + member1.hashCode());
        System.out.println("member2.hashCode() = " + member2.hashCode());
      }
}

결과

obj1.hashCode() = 762218386
  obj2.hashCode() = 796533847
  10.hashCode = 10
  'A'.hashCode = 65
  'AB'.hashCode = 2081
  -1.hashCode = -1
  (member1 == member2) = false
  member1 equals member2 = true
  member1.hashCode() = 104101
  member2.hashCode() = 104101
  • Member의 경우 회원의 id가 같으면 논리적으로 같은 회원으로 표현할 수 있어, 회원 id 를 기반으로 동등성을 비교하도록 equals를 재정의해야 한다.
  • 여기에 hashCode() 도 같은 원리가 적용된다. 회원의 id 가 같으면 논리적으로 같은 회원으로 표현할 수 있다. 따라 서 회원 id 를 기반으로 해시 코드를 생성해야 한다.
  • hashCode() 를 재정의하지 않으면 Object 가 기본으로 제공하는 hashCode() 를 사용하게 된다.
    이것은 객체의 참조값을 기반으로 해시 코드를 제공한다. 따라서 회원의 id 가 같아도 인스턴스가 다르면 다른 해시 코드를 반환하게 된다.

MyHashSetV2

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

  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 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;
	}
    
    	private int hashIndex(Object value) {
    
    		return Math.abs(value.hashCode()) % capacity;
        
      }
  }

private LinkedList<Object>[] buckets

  • 여기서는 모든 타입을 저장할 수 있도록 Object를 사용했다.

hashIndex()

  • 먼저 Object 의 hashCode() 를 호출해서 해시 코드를 찾는다. 그리고 찾은 해시 코드를 배열의 크기
    로 나머지 연산을 수행한다.
  • Object 의 hashCode() 를 사용한 덕분에 모든 객체의 hashCode() 를 구할 수 있다.
  • hashCode() 의 실행 결과로 음수가 나올 수 있는데, 배열의 인덱스로 음수는 사용할 수 없다.
  • Math.abs() 를 사용하면 마이너스를 제거해서 항상 양수를 얻을 수 있다.

MyHashSetV3

MyHashSetV2는 Object를 받을 수 있어, 직접 만든 Member와 같은 객체도 보관할 수 있다.

여기서 주의할 점은 직접 만든 객체가 hashCode(),equals() 두 메서드를 반드시 구현해야 한다는 점이다.

equals ,hashcode의 중요성

해시자료구조를 사용하려면 hashcode()도 중요하지만, 해시 인덱스가 충돌할 경우를 대비해서 equals()를 반드시 재정의해야한다.

클래스를 만들 때 hahsCode(),equals()를 재정의하지 않으면 해시 자료 구조에서 Object가 기본적으로 제공하는 hahsCode(),equals()를 사용한다. 이때 제공되는 기능은 단순히 인스턴스의 참조를 기반으로 작동한다.

  • hashCode 또는 equals를 구현하지 않은 경우
 MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
 MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");

m1,m2는 논리적으로 같다고 보지만, hashCode,equals를 구현하지 않아 참조값으로 동일성을 판단해 두 값이 서로 다르다고 인지된다.

그 결과 hashCode가 매번 다르게 설정될 수 있어 저장할 때 같은 id값이 다른 인덱스에 저장되거나 검색할때 잘못된 결과값이 나올 수 있다.


MyHashSetV4

지금까지 만든 헤시셋에 제네릭을 도입해서 타입 안정성을 높였다.


  package collection.set;
  public interface MySet<E> {
      boolean add(E element);
      boolean remove(E value);
      boolean contains(E value);
}
public class MyHashSetV3<E> implements MySet<E> {

    private LinkedList<E>[] buckets;
    
    ...
    
      @Override
    public boolean add(E value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }
        bucket.add(value);
        size++;
        return true;
	}
    
    @Override
    public boolean contains(E searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<E> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
	}	


    @Override
    public boolean remove(E value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        boolean result = bucket.remove(value);
        if (result) {
			size--;
            return true;
        } else {
            return false;
        }
	}
}
...










출처: 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

profile
이동건 (불꽃냥펀치)
자바를 사랑합니다
이전 포스트

타임리프(thymeleaf) 정리

다음 포스트

세미 프로젝트 1일차_달력1

0개의 댓글

관련 채용 정보