2025.01.12 - [Java공부(코딩)] - 코딩초보의 자바(Java)공부 27일차 { 컬렉션프레임워크 -Hash }
코딩초보의 자바(Java)공부 27일차 { 컬렉션프레임워크 -Hash }
1.List vs Set 정의**: 리스트는 요소들의 순차적인 컬렉션이다. 요소들은 특정 순서를 가지며, 같은 요소가 여러 번 나타날 수 있다.**특징**:**순서 유지**: 리스트에 추가된 요소는 특정한 순서를
ddkk1120.tistory.com
이 글과 이어집니다!!
Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조이다.**
이전에 구현한 성능이 O(n)으로 느린 `MyHashSetV0` 를 다시 한번 확인해보자.
**MyHashSetV0의 단점**
`add()`로 데이터를 추가할 때 셋에 중복 데이터가 있는지 전체 데이터를 항상 확인해야 한다. 따라서 O(n)으로
입력 성능이 나쁘다. 중복 데이터가 있는지 검색 O(n) + 데이터 입력 O(1) O(n)
`contains()`로 데이터를 찾을 때는 셋에 있는 모든 데이터를 찾고 비교해야 하므로 평균 O(n)이 걸린다.
`add(value)` : 셋에 값을 추가한다. 중복 데이터는 저장하지 않는다.
`contains(value)` : 셋에 값이 있는지 확인한다.`
remove(value)` : 셋에 있는 값을 제거한다.
package collection.set;
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));
//Integer타입으로변환 후 remove키워드사용(객체만 사용할 수 있음)
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()`연결 리스트를 생성해서 배열을 채운다. 배열의 모든 인덱스 위치에는 연결 리스트가 들어있다.
초기 배열의 크기를 생성자를 통해서 전달할 수 있다.
기본 생성자를 사용하면 `DEFAULT_INITIAL_CAPACITY` 의 값인 16이 사용된다.
`add()` : 해시 인덱스를 사용해서 데이터를 보관한다.
`contains()` : 해시 인덱스를 사용해서 데이터를 확인한다.
`remove()` : 해시 인덱스를 사용해서 데이터를 제거한다.\
메인코드
package collection.set;
public class MyHashSetV1Main {
public static void main(String[] args) {
MyHashSetV1 set = new MyHashSetV1(10);
set.add(1);
set.add(2);
set.add(11);//중복
set.add(23);
set.add(88);
set.add(8);//hashIndex중복
System.out.println(set);
//검색
int search = 88;
boolean contains = set.contains(search);
System.out.println("set에 "+search+"이(가) 존재하는가?? : "+contains);
//삭제
boolean remove = set.remove(23);
System.out.println("remove : "+remove);
System.out.println(set);
}
}MyHashSetV1{buckets=[[], [1, 11], [2], [23], [], [], [], [], [88, 8], []], size=6}
set에 88이(가) 존재하는가?? : true
remove : true
MyHashSetV1{buckets=[[], [1, 11], [2], [], [], [], [], [], [88, 8], []], size=5}
**남은 문제**
해시 인덱스를 사용하려면 데이터의 값을 배열의 인덱스로 사용해야 한다. 그런데 배열의 인덱스는 0, 1, 2 같은 숫자만
사용할 수 있다. "A", "B"와 같은 문자열은 배열의 인덱스로 사용할 수 없다.
다음 예와 같이 숫자가 아닌 문자열 데이터를 저장할 때, 해시 인덱스를 사용하려면 어떻게 해야할까?
예)
MyHashSetV1 set = new MyHashSetV1(10);
set.add("A");
set.add("B");
set.add("HELLO");
package javaBasic2.collection.set;
public class StringHashMain {
static final int CAPACITY = 10;
public static void main(String[] args) {
char charA = 'A';
char charB = 'B';
char charC = 'C';
char charD = 'D';
System.out.println(charA +" = "+(int)charA);
System.out.println(charB +" = "+(int)charB);
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(A) = "+hasIndex(hashCode("A")));
System.out.println("hashIndex(B) = "+hasIndex(hashCode("B")));
}
static int hashCode(String str) {
char[] charArray = str.toCharArray();
int sum = 0;
for (char c : charArray) {
sum+=c;
}
return sum;
}
static int hasIndex(int value) {
return value % CAPACITY;
}
}char 형을 int 형으로 캐스팅하면 문자의 고유한 숫자를 확인할 수 있다.
해시 함수(Hash Function)
해시 함수는 임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값(해시 코드)을 출력하는 함수이다.
여기서 의미하는 고정된 길이는 저장 공간의 크기를 뜻한다. 예를 들어서 int 형 1 , 100 은 둘다 4byte를
차지하는 고정된 길이는 뜻한다.
같은데이터를입력하면항상 같은 해시코드가 출력됨
해시 코드(Hash Code)
해시 코드는 데이터를 대표하는 값을 뜻한다. 보통 해시 함수를 통해 만들어진다.
데이터 A 의 해시 코드는 65
데이터 B 의 해시 코드는 66
데이터 AB 의 해시 코드는 131
해시 인덱스(Hash Index)
해시 인덱스는 데이터의 저장 위치를 결정하는데, 주로 해시 코드를 사용해서 만든다.
보통 해시 코드의 결과에 배열의 크기를 나누어 구한다
문제점
: 문자뿐 아니라 Animal 등의 객체의경우에는 어떻게 해시코드를정의할까??
자바의 hashCode()
Object.hashCode()
이 메서드는 그냥 사용하기보단
재정의(오버라이딩)해서 사용하곤 한다
긴말하지않고 코드를 구현해봅시다
package javaBasic2.collection.set;
public class MemberMain {
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는 같다.
MemberHash member1 = new MemberHash("idA");
MemberHash member2 = new MemberHash("idA");
MemberNotHash member3 = new MemberNotHash("idC");
MemberNotHash member4 = new MemberNotHash("idC");
//equals, hashCode를 오버라이딩 한 경우
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());
//equals , hashCode를 오버라이딩 하지 않은 경우
System.out.println("(member3 == member4) = " + (member3 == member4));
System.out.println("member3 equals member4 = " +
member3.equals(member4));
System.out.println("member3.hashCode() = " + member3.hashCode());
System.out.println("member4.hashCode() = " + member4.hashCode());
}
}
결과값
obj1.hashCode() = 1848402763
obj2.hashCode() = 205797316
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
(member3 == member4) = false
member3 equals member4 = false
member3.hashCode() = 443308702
member4.hashCode() = 935044096
Object의 해시 코드 비교
Object 가 기본으로 제공하는 hashCode() 는 객체의 참조값을 해시 코드로 사용한다. 따라서 각각의 인스턴
스마다 서로 다른 값을 반환한다.
그 결과 obj1 , obj2 는 서로 다른 해시 코드를 반환한다.
자바의 기본 클래스의 해시 코드
Integer , String 같은 자바의 기본 클래스들은 대부분 내부 값을 기반으로 해시 코드를 구할 수 있도록
hashCode() 메서드를 재정의해 두었다.
따라서 데이터의 값이 같으면 같은 해시 코드를 반환한다.
해시 코드의 경우 정수를 반환하기 때문에 마이너스 값이 나올 수 있다
동일성과 동등성 복습
잠깐 동일성과 동등성에서 학습한 내용을 복습해보자.
Object 는 동등성 비교를 위한 equals() 메서드를 제공한다.
자바는 두 객체가 같다는 표현을 2가지로 분리해서 사용한다.
동일성(Identity): == 연산자를 사용해서 두 객체의 참조가 동일한 객체를 가리키고 있는지 확인
동등성(Equality): equals() 메서드를 사용하여 두 객체가 논리적으로 동등한지 확인
Member의 hashCode() 구현
Member 는 hashCode() 를 재정의했다.
hashCode() 를 재정의할 때 Objects.hash() 에 해시 코드로 사용할 값을 지정해주면 쉽게 해시 코드를 생
성할 수 있다.
hashCode() 를 재정의하지 않으면 Object 가 기본으로 제공하는 hashCode() 를 사용하게 된다. 이것은 객
체의 참조값을 기반으로 해시 코드를 제공한다. 따라서 회원의 id 가 같아도 인스턴스가 다르면 다른 해시 코드를
반환하게 된다.
hashCode() 를 id 를 기반으로 재정의한 덕분에 인스턴스가 달라도 id 값이 같으면 같은 해시 코드를 반환한
다.
따라서 인스턴스가 다른 member1 , member2 둘다 같은 해시 코드를 반환하는 것을 확인할 수 있다.
직접 구현하는 Set2 - MyHashSetV2
전에는 Integer타입만 들어올수 있는 set이었지만
이번에는 바꿔보자
package javaBasic2.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 "MyHashSetV1{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
'}';
}
}
private LinkedList<Object>[] buckets
MyHashSetV1 은 Integer 숫자만 저장할 수 있었다. 여기서는 모든 타입을 저장할 수 있도록 Object 를 사
용한다.
추가로 저장, 검색, 삭제 메서드의 매개변수도 Object 로 변경했다.
hashIndex()
hashIndex() 부분이 변경되었다.
먼저 Object 의 hashCode() 를 호출해서 해시 코드를 찾는다. 그리고 찾은 해시 코드를 배열의 크기
( capacity )로 나머지 연산을 수행한다. 이렇게 해시 코드를 기반으로 해시 인덱스를 계산해서 반환한다.
Object 의 hashCode() 를 사용한 덕분에 모든 객체의 hashCode() 를 구할 수 있다. 물론 다형성에 의해 오
버라이딩 된 hashCode() 가 호출된다.
hashCode() 의 실행 결과로 음수가 나올 수 있는데, 배열의 인덱스로 음수는 사용할 수 없다. Math.abs() 를
사용하면 마이너스를 제거해서 항상 양수를 얻을 수 있다
메인코드
package collection.set;
public class MyHashSetV2Main {
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);
}
}MyHashSetV1{buckets=[[], [AB], [], [], [], [A], [B, SET], [C], [D], []], size=6}
A.hashCode=65
B.hashCode=66
AB.hashCode=2081
SET.hashCode=81986
set.contains(SET) = true
문자열이 들어가는것을 확인 할 수 있다.
자바의 `String` 은 `hashCode()` 를 재정의해 두었다. 우리는 이 값을 사용하면 된다.
직접 구현하는 Set3 - 직접 만든 객체 보관
package collection.set;
public class MyHashSetV2Main2 {
public static void main(String[] args) {
MyHashSetV2 set = new MyHashSetV2(10);
Member member1 = new Member("동곤자바");
Member member2 = new Member("많관부");
set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("AB");
set.add("SET");
set.add(member1);
set.add(member2);
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());
//검색
Object searchMem = member1;
boolean result = set.contains(searchMem);
System.out.println("set.contains(" + searchMem + ") = " + result);
}
}
MyHashSetV2{buckets=[[], [AB], [], [], [], [A], [B, SET], [C, Member [id=많관부]], [D, Member [id=동곤자바]], []], size=8}
A.hashCode=65
B.hashCode=66
AB.hashCode=2081
SET.hashCode=81986
set.contains(Member [id=동곤자바]) = true
이렇게 Member객체도 넣을 수 있습니다.
주의점
Member클래스에 꼭
hashcode()와 equals()를 오버라이딩 할 것.
equals() 사용처**
그렇다면 `equals()` 는 언제 사용할까?
"JPA"를 조회할 때 해시 인덱스는 0이다. 따라서 배열의 `0` 번 인덱스를 조회한다.
여기에는 `[hi, JPA]` 라는 회원 두 명이 있다. 이것을 하나하나 비교해야 한다. 이때 `equals()` 를 사용해서 비교한다.
따라서 해시 자료 구조를 사용할 때는 `hashCode()` 는 물론이고, `equals()`
자바가 제공하는 기본 클래스들은 대부분 `hashCode()` , `equals()` 를 함께 재정의해 두었다.
도 반드시 재정의해야 한다.
Hashcode()와 eqauls()의 중요성
한번 Object에서 기본적으로 제공하는 해쉬코드와
재정의한 해쉬코드의 차이를 한번 보도록할게요
package collection.set;
public class Hashcod_eqauls {
public static void main(String[] args) {
Member2 m1 = new Member2("유동");
Member2 m2 = new Member2("유동");
System.out.println("hashCode()와 eqauls() 구현X");
System.out.println("m1.hascode() : "+m1.hashCode());
System.out.println("m2.hascode() : "+m2.hashCode());
System.out.println("m1.equals(m2) : "+m1.equals(m2));
System.out.println("\nhashCode()와 eqauls() 구현O");
Member m3 = new Member("자바");
Member m4 = new Member("자바");
System.out.println("m3.hascode() : "+m3.hashCode());
System.out.println("m4.hascode() : "+m4.hashCode());
System.out.println("m3.equals(m4) : "+m3.equals(m4));
}
}hashCode()와 eqauls() 구현X
m1.hascode() : 1450495309
m2.hascode() : 1528902577
m1.equals(m2) : false
hashCode()와 eqauls() 구현O
m3.hascode() : 1631907
m4.hascode() : 1631907
m3.equals(m4) : true
보시는바와 같이
구현(재정의)를 안했으면
분명 논리적으로는 "유동"으로
같은데 해시코드가 다른 모습을 알 수 있어요.
Object의 hashcode()는 참조값을
기반으로 만들어짐!!!!
그러므로 재정의를 해 값만 따져야함
hashCode()와 eqauls()중 하나라도 빼먹지말고
재정의 해야함!!!!!
hashCode()만 정의하고
eqauls()를 정의하지 않은 경우에는
둘이 같은 객체라고 판단하지않음
즉
중복된값은 넣지않는 set에
같은 객체 두개가 들어가게되는것임
직접 구현하는 Set4 - 제네릭과 인터페이스 도입
public interface Myset<E> {
boolean add(E e);
boolean remove(E e);
boolean contains(E e);
}
제네릭으로 만든 인터페이스를 구현해서
MyHashSetV3를 제네릭클래스로 만들어보자!!
package collection.set;
import java.util.Arrays;
import java.util.LinkedList;
public class MyHashSetV3<E> implements Myset<E> {
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<>();
}
}
@Override
public boolean add(E e) {
int hashIndex = hashIndex(e);
LinkedList<E> bucket = buckets[hashIndex];
if (bucket.contains(e)) {
return false;
}
bucket.add(e);
size++;
return true;
}
@Override
public boolean remove(E e) {
int hashIndex = hashIndex(e);
LinkedList<E> bucket = buckets[hashIndex];
boolean result = bucket.remove(e);
if (result) {
size--;
return true;
} else {
return false;
}
}
@Override
public boolean contains(E e) {
int hashIndex = hashIndex(e);
LinkedList<E> bucket = buckets[hashIndex];
return bucket.contains(e);
}
private int hashIndex(E e) {
//hashCode의 결과로 음수가 나올 수 있다. abs()를 사용해서 마이너스를 제거한다.
return Math.abs(e.hashCode()%capacity);
}
public int getSize() {
return size;
}
@Override
public String toString() {
return "MyHashSetV2{" +
"buckets=" + Arrays.toString(buckets) +
", size=" + size +
'}';
}
}전에는 Object로 다루던 객체들이
모두 E(제네릭타입)으로 변경 됐다
메인코드
package collection.set;
public class MyHashSetV3Main {
public static void main(String[] args) {
MyHashSetV3<Integer> iSet = new MyHashSetV3<Integer>();
iSet.add(10);
iSet.add(20);
iSet.add(30);
iSet.add(6);
iSet.add(18);
iSet.add(6);//중복된값은 set에 들어가지않음
System.out.println(iSet);
int searchI = 10;
boolean contains = iSet.contains(searchI);
System.out.println(searchI+"가 있는가?? "+contains);
MyHashSetV3<Member> mSet = new MyHashSetV3<Member>();
Member m1 = new Member("동곤자바");
Member m2 = new Member("많이 들어와 주세요!");
Member m3 = new Member("hashCode,eqauls구현완료!");
mSet.add(m1);
mSet.add(m2);
mSet.add(m3);
Member search = new Member("동곤자바");
boolean contains2 = mSet.contains(search);
System.out.println(search+"가 있나요? :"+contains);
}
}MyHashSetV2{buckets=[[10, 20, 30], [], [], [], [], [], [6], [], [18], []], size=5}
10가 있는가?? true
MyHashSetV2{buckets=[[Member [id=많이 들어와 주세요!]], [], [], [], [], [], [], [], [Member [id=동곤자바], Member [id=hashCode,eqauls구현완료!]], []], size=3}
Member [id=동곤자바]가 있나요? :true
제네릭 덕분에 Integer만을 받는 Set도 만들 수 있으며
Member의 객체만을 인자로받는 Set을 만들 수 있었다
'Java공부(코딩)' 카테고리의 다른 글
| 코딩초보의 자바(Java)공부 30일차 { Map , Stack , Queue } (1) | 2025.01.16 |
|---|---|
| 코딩초보의 자바(Java)공부 29일차 - { Set } (1) | 2025.01.15 |
| 코딩초보의 자바(Java)공부 27일차 { 컬렉션프레임워크 -Hash } (0) | 2025.01.12 |
| 코딩초보의 자바(Java)공부 26일차 { 컬렉션프레임워크 - List } (0) | 2025.01.09 |
| 코딩초보의 자바(Java)공부 25일차 { 컬렉션프레임워크 - ArrayList와LinkedList } (0) | 2025.01.08 |