🏷️직접 구현하는 Set1 - MyHashSetV1
Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조다.
public class MyHashSetV1 {
private 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 remove(int value) {
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex];
// Integer.valueOf(value) : 래퍼 클래스로 변환
boolean removed = bucket.remove(Integer.valueOf(value));
if (removed) {
size--;
return true;
} else {
return false;
}
}
public boolean contains(int searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
private 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;
}
private int hashIndex(int value) {
return value % capacity;
}
}public class MyHashSetV1Main {
public static void main(String[] args) {
MyHashSetV1 myHashSetV1 = new MyHashSetV1();
myHashSetV1.add(1);
myHashSetV1.add(2);
myHashSetV1.add(5);
myHashSetV1.add(8);
myHashSetV1.add(14);
myHashSetV1.add(99);
myHashSetV1.add(9);
System.out.println(myHashSetV1);
int searchValue = 9;
boolean contains = myHashSetV1.contains(searchValue);
System.out.println("myHashSetV1.contains(" + searchValue + ") = " + contains);
boolean removed = myHashSetV1.remove(searchValue);
System.out.println("myHashSetV1.remove(" + searchValue + ") = " + removed);
System.out.println(myHashSetV1);
}
}remove 구현 도중 파라미터로 들어가는 값에 대한 고민을 한 결과 연결 리스트의 remove가 어떤 식으로 작성되어있는지를 확인한 결과
- ✔️문제
- 해시 인덱스를 사용하려면 보다시피 해시 인덱스를 구할 때 파라미터를 용량으로 나눈 나머지 연산을 적용한 숫자값을 이용해야한다.
- 하지만 문자열의 경우 배열의 인덱스로 사용할 수 없다.
🏷️문자열 해시 코드
public class StringHashMain {
private 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);
int hashCodeA = hashCode("A");
System.out.println("hashCodeA = " + hashCodeA);
int hashCodeB = hashCode("B");
System.out.println("hashCodeB = " + hashCodeB);
int hashCodeAB = hashCode("AB");
System.out.println("hashCodeAB = " + hashCodeAB);
int hashIndexA = hashIndex(hashCodeA);
System.out.println("hashIndexA = " + hashIndexA);
int hashIndexB = hashIndex(hashCodeB);
System.out.println("hashIndexB = " + hashIndexB);
int hashIndexAB = hashIndex(hashCodeAB);
System.out.println("hashIndexAB = " + hashIndexAB);
}
private static int hashCode(String str) {
char[] charArray = str.toCharArray();
int sum = 0;
for (int i = 0; i < charArray.length; i++) {
sum += ((int) charArray[i]);
}
return sum;
}
private static int hashIndex(int value) {
return value % CAPACITY;
}
}
- ✔️정리
hashCode()메서드를 사용하여 문자열을 해시 코드로 변경한다. 그러면 고유한 정수 값이 나오는데 이 값을 해시 코드라 한다.- 숫자 값인 해시 코드를 사용해서 해시 인덱스를 생성한다.
- 이렇게 생성된 해시 인덱스를 배열 인덱스로 사용하면 된다.
- ✔️용어 정리
- 해시 함수 : 임의의 길이의 데이터를 입력으로 받아 고정된 길이의 해시값을 출력하는 함수
- 같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다.
- 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. 이것을 해시 충돌이라 한다.
- 해시 코드 : 데이터를 대표하는 값
- 해시 인덱스 : 해시 인덱스는 데이터의 저장 위치를 결정하는데 주로 해시 코드를 사용해서 만든다. 보통 해시 코드 결과에 배열 크기를 나누어 구한다.
- 해시 함수 : 임의의 길이의 데이터를 입력으로 받아 고정된 길이의 해시값을 출력하는 함수
- ✔️결론
- 문자 데이터를 사용할 때도 해시 함수를 사용해서 정수 기반의 해시 코드로 변환한 덕분에 해시 인덱스를 사용할 수 있게 되었다.
🏷️자바의 hashCode()
public class JavaHashCodeMain {
public static void main(String[] args) {
Object object1 = new Object();
Object object2 = new Object();
System.out.println("object1.hashCode() = " + object1.hashCode());
System.out.println("object2.hashCode() = " + object2.hashCode());
Member member1 = new Member("id-100");
Member member2 = new Member("id-100");
System.out.println("member1.hashCode() = " + member1.hashCode()); // 음수도 나올 수 있음
System.out.println("member2.hashCode() = " + member2.hashCode());
System.out.println("member1 == member2 → " + (member1 == member2));
System.out.println("member1.equals(member2) → " + member1.equals(member2));
}
}- ✔️Object 해시 코드 비교
Object가 제공하는hashCode()는 객체의 참조값을 해시 코드로 사용한다. 따라서 각각의 인스턴스마다 다른 값을 반환한다.
- ✔️자바의 기본 클래스 해시 코드
Integer,String과 같은 자바 기본 클래스들은 대부분 내부 값을 기반으로 해서 해시 코드를 구할 수 있도록hashCode()메서드를 재정의해두었다.- 따라서 데이터 값이 같으면 같은 해시 코드를 반환한다.
- ✔️동일성 vs 동등성
- 동일성은
==연산자를 사용해서 두 객체의 참조가 동일한 객체를 가리키는지를 확인 - 동등성은
equals()메서드를 사용해서 두 객체가 논리적으로 동등한지 확인
- 동일성은
🏷️직접 구현하는 Set2 - MyHashSetV2
public class MyHashSetV2 {
private static final int DEFAULT_INITIAL_CAPACITY = 10;
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 remove(Object value) {
int hashIndex = hashIndex(value);
LinkedList<Object> bucket = buckets[hashIndex];
boolean removed = bucket.remove(value);
if (removed) {
size--;
return true;
} else {
return false;
}
}
public boolean contains(Object searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<Object> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
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) {
// 해시 코드 값 음수 나올 수 있으므로
int hashCode = value.hashCode();
return Math.abs(hashCode) % capacity;
}
@Override
public String toString() {
return "MyHashSetV2{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
'}';
}
}- ✔️코드 변경사항
- 기존
MyHashSetV1은Integer만 저장할 수 있었으나 여기서Object타입으로 수정하여 모든 타입을 저장할 수 있도록 바꿨다. - 파라미터 역시
Object타입으로 변경했다. - 해시 코드가 음수가 나올 수 있기 때문에 나머지 연산을 정상적으로 처리해주기 위해 절댓값 처리를 해준다.
- 기존
🏷️직접 구현하는 Set3 - 직접 만든 객체 보관
- ✔️주의
- 이전에 만든
MyHashSetV2는Object타입을 저장할 수 있게끔 했다. - 기본적으로
equals()는 참조값을 기준으로 비교하기 때문에 직접 만든 객체의 경우equals()와hashCode()메서드를 반드시 재정의해야한다.
- 이전에 만든
public class MyHashSetV2Main {
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);
}
}
🏷️equals, hashCode의 중요성1
Object의 기본 기능
hashCode(): 객체의 참조값을 기반으로 해시 코드를 반환한다.equals(): 재정의하지않은Object의equals()는==동일성 비교를 한다. 따라서 객체의 참조값이 같아야true가 반환된다.
해시 자료 구조를 사용할 때 유의할 점에 대해서 세 가지 경우를 들어 이해해보자.
①. hashCode(), equals()를 모두 구현하지 않은 경우
②. hashCode()는 구현했는데 equals()를 구현하지 않은 경우
③. hashCode()와 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 myHashSetV2 = new MyHashSetV2();
MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");
System.out.println("m1.hashCode() : " + m1.hashCode());
System.out.println("m2.hashCode() : " + m2.hashCode());
System.out.println("m1.equals(m2) : " + m1.equals(m2));
myHashSetV2.add(m1);
myHashSetV2.add(m2);
System.out.println(myHashSetV2);
MemberNoHashNoEq searchValue = new MemberNoHashNoEq("A");
System.out.println("searchValue.hashCode() : " + searchValue.hashCode());
boolean contains = myHashSetV2.contains(searchValue);
System.out.println("contains = " + contains);
}
}실행 결과
m1.hashCode() : 1922154895
m2.hashCode() : 960604060
m1.equals(m2) : false
MyHashSetV2{buckets=[[MemberNoHashNoEq{id='A'}], [], [], [], [], [MemberNoHashNoEq{id='A'}], [], [], [], []], size=2}
searchValue.hashCode() : 932172204
contains = false- ✔️결과
equals(),hashCode()를 모두 구현하지 않고Object가 제공하는 기본 기능을 그대로 사용했기 때문에 객체의 참조값을 기반으로 이루어진다.- 내용이 같다 하더라도
m1과m2는 인스턴스의 값이 같더라도 서로 다른 해시 코드 값을 가지게 된다. 또한equals()역시 참조값을 활용한 동일성 비교가 이루어지는데 참조값이 다르므로 당연히false가 된다. - 같은 값임에도 불구하고 필요한 메서드를 구현하지 않아 다른 버킷에 저장되는 것을 볼 수 있다.
m1과m2인스턴스는 다르지만 둘 다 "A"라는 회원 ID를 가지고 있다. 따라서 논리적으로 같은 회원으로 보아야 한다.
🏷️equals, hashCode의 중요성2
❗hashCode()는 구현했는데 equals()를 구현하지 않은 경우
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(id);
}
}public class HashAndEqualsMain2 {
public static void main(String[] args) {
MyHashSetV2 myHashSetV2 = new MyHashSetV2();
MemberOnlyHash m1 = new MemberOnlyHash("A");
MemberOnlyHash m2 = new MemberOnlyHash("A");
System.out.println("m1.hashCode() : " + m1.hashCode());
System.out.println("m2.hashCode() : " + m2.hashCode());
System.out.println("m1.equals(m2) : " + m1.equals(m2));
myHashSetV2.add(m1);
myHashSetV2.add(m2);
System.out.println(myHashSetV2);
MemberOnlyHash searchValue = new MemberOnlyHash("A");
System.out.println("searchValue.hashCode() : " + searchValue.hashCode());
boolean contains = myHashSetV2.contains(searchValue);
System.out.println("contains = " + contains);
}
}실행 결과
m1.hashCode() : 96
m2.hashCode() : 96
m1.equals(m2) : false
MyHashSetV2{buckets=[[], [], [], [], [], [], [MemberNoHashNoEq{id='A'}, MemberNoHashNoEq{id='A'}], [], [], []], size=2}
searchValue.hashCode() : 96
contains = false- ✔️결과
hashCode()를 재정의했기 때문에 같은id를 사용하는m1과m2는 같은 해시 코드가 나오게 된다.- 따라서 같은 해시 코드를 가지게 되지만
equals()는 구현하지 않았기 때문에 참조값을 기준으로 동일성 비교를 하게 되며 이 결과false가 나오게 된다. add()메서드에서 중복 데이터를 체크하기 때문에 같은 데이터가 저장되면 안된다.contains()메서드에서 데이터를 비교할 때equals()를 사용하는데 재정의를 하지 않았기 때문에 인스턴스 참조값으로 비교를 하게 된다.m1,m2는 참조값이 서로 다른 인스턴스이기 때문에 비교에 실패한다.
❗hashCode(), equals()를 모두 구현한 경우
public class HashAndEqualsMain3 {
public static void main(String[] args) {
MyHashSetV2 myHashSetV2 = new MyHashSetV2();
Member m1 = new Member("A");
Member m2 = new Member("A");
System.out.println("m1.hashCode() : " + m1.hashCode());
System.out.println("m2.hashCode() : " + m2.hashCode());
System.out.println("m1.equals(m2) : " + m1.equals(m2));
myHashSetV2.add(m1);
myHashSetV2.add(m2);
System.out.println(myHashSetV2);
Member searchValue = new Member("A");
System.out.println("searchValue.hashCode() = " + searchValue.hashCode());
boolean contains = myHashSetV2.contains(searchValue);
System.out.println("contains = " + contains);
}
}실행 결과
m1.hashCode() : 65
m2.hashCode() : 65
m1.equals(m2) : true
MyHashSetV2{buckets=[[], [], [], [], [], [Member{id='A'}], [], [], [], []], size=1}
searchValue.hashCode() = 65
contains = true- ✔️결과
- 객체의 참조값이 아닌 인스턴스 내부의 값을 기준으로 수행되도록
equals(),hashCode()를 재정의하여 정상적인 결과를 얻을 수 있다.
- 객체의 참조값이 아닌 인스턴스 내부의 값을 기준으로 수행되도록
🏷️직접 구현하는 Set4 - 제네릭과 인터페이스 도입
public interface MySet<E> {
boolean add(E e);
boolean contains(E e);
boolean remove(E e);
}public class MyHashSetV3<E> implements MySet<E> {
private static final int DEFAULT_INITIAL_CAPACITY = 10;
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 remove(E value) {
int hashIndex = hashIndex(value);
LinkedList<E> bucket = buckets[hashIndex];
boolean removed = bucket.remove(value);
if (removed) {
size--;
return true;
} else {
return false;
}
}
public boolean contains(E searchValue) {
int hashIndex = hashIndex(searchValue);
LinkedList<E> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
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;
}
private int hashIndex(E value) {
// 해시 코드 값 음수 나올 수 있으므로
int hashCode = value.hashCode();
return Math.abs(hashCode) % capacity;
}
@Override
public String toString() {
return "MyHashSetV3{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
", capacity=" + capacity +
'}';
}
public int getSize() {
return size;
}
}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);
String searchValue = "A";
boolean contains = set.contains(searchValue);
System.out.println("contains = " + contains);
}
}실행 결과
MyHashSetV3{buckets=[[], [], [], [], [], [A], [B], [C], [], []], size=3, capacity=10}
contains = true