컬렉션 프레임워크 - HashSet

황상익·2024년 6월 24일

Inflearn JAVA

목록 보기

37/61

직접 구현하는 Set1 - MyHashSetV1

set은 중복을 허용 X, 순서 보장 X

Set을 구현하는 방법은 단순. 인덱스가 없기 때문에 단순히 데이터를 저장, 데이터 있는지 확인, 데이터 삭제 & 중복 여부만 check

import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV1 {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    LinkedList<Integer>[] buckets;
    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;
    public MyHashSetV1() {
        initBuckets();
    }
    public MyHashSetV1(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(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;
    }
    @Override
    public String toString() {
        return "MyHashSetV1{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                '}';
    }
}

buckets : 연결 리스트를 배열로 사용

배열안에 연결 리스트가 들어있고, 연결 리스트 안에 데이터 저장
해시 인덱스가 충돌 발생, 같은 연결리스트 안에 여러 데이터가 저장

initBuckets()

연결리스트를 생성해서 배열을 채운다. 배열의 모든 인덱스 위치에는 연결리스트 들어있음
초기 배열의 크기를 생성자를 통해서 전달

public class MyHashSetV1Main {
    public static void main(String[] args) {
        MyHashSetV1 set = new MyHashSetV1();
        set.add(1);
        set.add(2);
        set.add(5);
        set.add(8);
        set.add(14);
        set.add(99);
        set.add(9);
        System.out.println("set = " + set);

        //검색
        int searchVal = 9;
        boolean rst = set.contains(searchVal);
        System.out.println("set contains (" + searchVal + ") = " + rst);

        boolean removeRst = set.remove(searchVal);
        System.out.println("removeRst = " + removeRst);
        System.out.println("set = " + set);
    }
}

문자열 해시 코드

public class StringHashMain {
    static final int CAPACITY = 10;

    public static void main(String[] args) {
        char charA = 'A';
        char charB = 'B';

        //아스키코드로 변경됨
        System.out.println("charA = " + (int)charA);
        System.out.println("charB = " + (int)charB);

        System.out.println();

        //hashCode
        System.out.println("hashCode(\"A\") = " + hashCode("A"));
        System.out.println("hashCode(\"B\") = " + hashCode("B"));
        System.out.println("hashCode(\"AB\") = " + hashCode("AB"));

        System.out.println();

        //hashIndex
        System.out.println("hashIndex(hashCode(\"A\")) = " + hashIndex(hashCode("A")));
        System.out.println("hashIndex(hashCode(\"B\")) = " + hashIndex(hashCode("B")));
        System.out.println("hashIndex(hashCode(\"AB\")) = " + hashIndex(hashCode("AB")));
    }

    //문자가 -> 숫자로 변경됨
    static int hashCode(String str){
        char[] charArray = str.toCharArray();
        int sum = 0;
        for (char c:
             charArray) {
            sum += c;
        }

        return sum;
    }

    //나눈 나머지
    static int hashIndex (int val){
        return val % CAPACITY;
    }
}

문자가 숫자로 표현하게 되면 아스키코드로 변경된다.

해시코드와 해시 인덱스

hashCode라는 메서드를 통해서 문자를 기반으로 고유한 숫자 형성

Hash Function
해시 함수는 임의이 길이의 데이터를 입력받아 고정된 길이의 해시 값을 출력하는 함수

고정된 길이는 저장된 값
같은 데이터 입력시 항상 같은 해시 코드가 출력
다른 데이터를 입력시, 같은 해시코드 출력 가능, = 해시 충돌

HashCode
해시코드는 데이터를 대표하는 값

HasIndex
해시 인덱스는 데이터의 저장 위치를 결정, 주로 해시 코드를 사용해서 만든다.
해시 코드의 결과에 배열의 크기를 나누어 구한다.

자바의 hashCode()

해시 인덱스를 사용하는 해시 자료구조는 데이터 추가, 삭제 성능이 O(1)로 매우 빠르다. 자바에는 정수 int , Integer 뿐만 아니라 char , String , Double , Boolean 등 수 많은 타입이 있다. 뿐만 아니라 개발자가 직접 정의한 Member , User 와 같은 사용자 정의 타입도 있다.

Object.hashCode()

자바는 모든 객체가 자신만의 해시코드를 표현, Object에 있는 hashCode() 메서드

public class Member {
    private String id;

    public Member(String id){
        this.id = id;
    }

    public String getId() {
        return id;
    }

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

        if (obj == null || getClass() != obj.getClass())
            return false;

        Member member = (Member) obj;
        return Objects.equals(id, member.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Member{" +
                "id='" + id + '\'' +
                '}';
    }
}

public class JavaHashCodeMain {
    public static void main(String[] args) {
        //Object의 기본 hashcode는 객체의 참조값을 기반
        Object obj1 = new Object();
        Object obj2 = new Object();
        System.out.println("obj1 = " + obj1.hashCode());
        System.out.println("obj2 = " + obj2.hashCode());

        //각 클래스마다 hashCode를 이미 오버리이딩
        Integer i = 10;
        String strA = "A";
        String strB = "AB";

        System.out.println("i = " + i.hashCode());
        System.out.println("strA = " + strA.hashCode());
        System.out.println("strB = " + strB.hashCode());

        //hashCode는 마이너스 값 들어올 수 있다.
        System.out.println("-1.hashCode = " + Integer.valueOf(-1).hashCode());

        //둘은 같을까?? 인스턴스는 다르지만, equals는 같다
        Member member1 = new Member("idA");
        Member member2 = new Member("idB");

        //equals, hashCode를 오버라이딩 하지 않은 경우와 한 경우 비교
        System.out.println("(member1 == member2) = " + (member1 == member2));
        System.out.println("member1 equals member2 = " + member1.equals(member2));

        System.out.println("hashCode 오버라이딩 한 case");
        System.out.println("member1.hashCode() = " + member1.hashCode());
        System.out.println("member2.hashCode() = " + member2.hashCode());
    }
}

Object의 해시 코드 비교

Object가 기본으로 제공하는 hashCode는 객체의 참조값을 해시코드로 사용 인스턴스마다 서로 다른 값 반환

자바의 기본 클래스의 해시 코드

Integer, String 같은 자바의 기본 클래스들은 대부분 내부 값을 기반으로 해시코드를 구한 수 있도록 hashCode 메서드를 재정의
데이터 값이 같으면 같은 해시코드를 반환
해시 코드의 경우 정수 반환, 마이너스 값 나올 수 있음

직접 구현하는 해시 코드

Member의 hashCode 구현

Member는 hashCode 제정의
hashCode를 재정의할 때 Objects.hash에 해시코드를 사용할 값을 지정해주면서 쉽게 해시 코드를 생성 가능
hashCode를 재정의하지 않으면 Object가 기본으로 제공하는 hashCode를 사용
객체의 참조값을 기반으로 해시 코드를 제공
hashCode를 id를 기반으로 재정의한 덕분에 인스턴스가 달라도 id 값이 같으면 같은 해시 코드 반환

직접 구현하는 Set2 - MyHashSetV2

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;

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

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV2{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}

private LinkedList< Object>[] buckets
타입을 Object로 변경

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

public class MyHashSetV2Main {
    public static void main(String[] args) {
        MyHashSetV2 setV2 = new MyHashSetV2(10);
        setV2.add("A");
        setV2.add("B");
        setV2.add("C");
        setV2.add("AB");
        setV2.add("SET");
        System.out.println("setV2 = " + setV2);

        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 searchVal = "SET";
        boolean rst = setV2.contains(searchVal);
        System.out.println("set.contains(" + searchVal + ")= " + rst);
    }
}

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

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

import chap37.member.Member;

public class MyHashSetMainV2 {
    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 = " + hi.hashCode());
        System.out.println("jpa = " + jpa.hashCode());
        System.out.println("java = " + 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 = " + set);

        Member searchVal = new Member("JPA");
        boolean rst = set.contains(searchVal);
        System.out.println("set.contains(" + searchVal + ")=" + rst);
    }
}

equals() 사용처
"JPA"를 조회할 때 해시 인덱스는 0이다. 따라서 배열의 0 번 인덱스를 조회한다.
여기에는 [hi, JPA] 라는 회원 두 명이 있다. 이것을 하나하나 비교해야 한다. 이때 equals() 를 사용해서 비교한다

hashCode() 는 물론이고, equals() 도 반드시 재정의해야 한다. 참고로 자바
가 제공하는 기본 클래스들은 대부분 hashCode() , equals() 를 함께 재정의해 두었다.

equals, hashCode의 중요성 1

해시 자료 구조를 사용하려면 hashCode() 도 중요하지만, 해시 인덱스가 충돌할 경우를 대비에서 equals() 도 반드시 재정의해야 한다. 해시 인덱스가 충돌할 경우 같은 해시 인덱스에 있는 데이터들을 하나하나 비교해서 찾아야한다. 이때 equals() 를 사용해서 비교한다.

hashCode, equals를 모두 구현하지 않은 경우

public class MemberNoHashNoEq {
    private String id;

    public MemberNoHashNoEq(String id){
        this.id = id;
    }

    public String getId() {
         return id;
    }

    @Override
    public String toString() {
        return "MemberNoHashNoEq{" +
                "id='" + id + '\'' +
                '}';
    }
}

public class HashAndEqualsMain1 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);

        MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
        MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");
        System.out.println("m1.hasCode() = " + m1.hashCode());
        System.out.println("m2.hasCode() = " + m2.hashCode());
        System.out.println("m1.equals(m2) = " + m1.equals(m2));

        set.add(m1);
        set.add(m2);
        System.out.println("set = " + set);

        //검색 실패
        MemberNoHashNoEq searchVal = new MemberNoHashNoEq("A");
        System.out.println("searchVal.hashCode() = " + searchVal.hashCode());
        boolean contains = set.contains(searchVal);
        System.out.println("contains = " + contains);

    }
}

데이터 저장 문제
해시 코드가 서로 다르기 때문에 다른 위치에 각기 저장
회원 id가 "A"로 같은 회원의 데이터가 데이터가 중복 저장

데이터 검색 문제
MemberNoHashNoEq searchValue = new MemberNoHashNoEq("A")
회원 id가 "A"인 객체를 검색하기 위해 회원 id가 "A"인 객체를 만들었다. 이 객체의 참조값은 1008 이라 가정하자.
데이터를 검색할 때 searchValue 객체의 해시 코드는 1008 이다. 따라서 다른 위치에서 데이터를 찾게 되고, 검색에 실패한다

equals, hashCode의 중요성2

import java.util.Objects;

public class MemberOnlyHash {
    private String id;

    public MemberOnlyHash(String id){
        this.id = id;
    }

    public String getId() {
        return id;
    }

    @Override
    public String toString() {
        return "MemberNoHashNoEq{" +
                "id='" + id + '\'' +
                '}';
    }

    @Override
    public int hashCode() {
        return Objects.hash(getId());
    }
}

public class HashAndEqualsMain2 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);

        MemberOnlyHash m1 = new MemberOnlyHash("A");
        MemberOnlyHash m2 = new MemberOnlyHash("A");
        System.out.println("m1.hasCode() = " + m1.hashCode());
        System.out.println("m2.hasCode() = " + m2.hashCode());
        System.out.println("m1.equals(m2) = " + m1.equals(m2));

        set.add(m1);
        set.add(m2);
        System.out.println("set = " + set);

        //검색 실패
        MemberNoHashNoEq searchVal = new MemberNoHashNoEq("A");
        System.out.println("searchVal.hashCode() = " + searchVal.hashCode());
        boolean contains = set.contains(searchVal);
        System.out.println("contains = " + contains);

    }
}

데이터 저장 문제
add() 로직은 중복 데이터를 체크하기 때문에 같은 데이터가 저장되면 안된다

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;
}

데이터 검색 문제
MemberOnlyHash searchValue = new MemberOnlyHash("A")
회원 id가 "A"인 객체를 검색하기 위해 회원 id가 "A"인 객체를 만들었다. 해시 코드가 구현되어 있다.
searchValue 는 해시 인덱스 6을 정확히 찾을 수 있다.
해시 인덱스에 있는 모든 데이터를 equals() 를 통해 비교해서 같은 값을 찾아야 한다.
다음 코드를 보자. bucket.contains(searchValue) 내부에서 연결 리스트에 있는 모든 항목을 searchValue 와 equals() 로 비교한다

hashCode와 equals 모두 구현

public class HashAndEqualsMain3 {
    public static void main(String[] args) {
        MyHashSetV2 set = new MyHashSetV2(10);

        Member m1 = new Member("A");
        Member m2 = new Member("A");
        System.out.println("m1.hasCode() = " + m1.hashCode());
        System.out.println("m2.hasCode() = " + m2.hashCode());
        System.out.println("m1.equals(m2) = " + m1.equals(m2));

        set.add(m1);
        set.add(m2);
        System.out.println("set = " + set);

        //검색 실패
        Member searchVal = new Member("A");
        System.out.println("searchVal.hashCode() = " + searchVal.hashCode());
        boolean contains = set.contains(searchVal);
        System.out.println("contains = " + contains);

    }
}

데이터 저장
다음으로 m2 저장을 시도한다. m1 과 같은 해시 코드를 사용하므로 해시 인덱스도 같다. 여기서 중복 데이터를 저장하면 안되므로 m1 과 m2 를 equals 비교한다. 같은 데이터가 이미 있으므로 m2는 저장에 실패한다. 결과적으로 중복 데이터가 저장되지 않는다.

데이터 검색
searchValue 의 해시 코드로 6번 해시 인덱스를 찾는다.
searchValue 와 6번 해시 인덱스 내부의 데이터를 모두 equals 비교한다. searchValue 와 m1이 equals 비교에 성공하므로 참을 반환한다.

hash를 사용한다고 해서 항상 충돌을 피할 수는 없다, 하지만 경우의 수가 줄어든다.

직접 구현하는 set4 - 제네릭과 인터페이스 도입

public interface MySet<E> {
    boolean add(E element);
    boolean remove(E value);
    boolean contains(E value);
}

import chap37.member.MySet;

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashSetV3<E> implements MySet<E> {
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    private LinkedList<E>[] buckets;
    private int size = 0;
    private int capacity = DEFAULT_INITIAL_CAPACITY;
    public MyHashSetV3() {
        initBuckets();
    }
    public MyHashSetV3(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(E value) {
        int hashIndex = hashIndex(value);
        LinkedList<E> bucket = buckets[hashIndex];
        if (bucket.contains(value)) {
            return false;
        }
        bucket.add(value);
        size++;
        return true;
    }
    public boolean contains(E searchValue) {
        int hashIndex = hashIndex(searchValue);
        LinkedList<E> bucket = buckets[hashIndex];
        return bucket.contains(searchValue);
    }
    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;
        }
    }
    private int hashIndex(Object value) {
        int hashCode = value.hashCode();
        int hashIndex = Math.abs(hashCode) % capacity;
        return hashIndex;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV3{" +
                "buckets=" + Arrays.toString(buckets) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}

public class MyHashSetV3Main {
    public static void main(String[] args) {
        MySet<String> set = new MyHashSetV3<>();

        set.add("A");
        set.add("B");
        set.add("C");
        System.out.println("set = " + set);

        String searchVal = "A";
        boolean contains = set.contains(searchVal);
        System.out.println("set.contains(" + searchVal + ")=" + contains);

    }
}

제네릭을 사용함으로써 타입 안정성이 더 높아진다.

황상익

개발자를 향해 가는 중입니다~! 항상 겸손

이전 포스트

Hash

다음 포스트