리스트(List) vs 셋(Set)
List
정의: 요소들의 순차적인 컬렉션, 요소들은 특정 순서가 있고 같은 요소가 여러번 나타날 수 있음
- 순서유지
- 중복 허용
- 인덱스 접근
용도: 순서가 중요하거나 중복된 요소를 허용하는 경우 사용한다.
ex. 장바구니 목록, 순서가 있는 이벤트 목록
Set
정의: 유일한 요소들의 컬렉션
- 유일성
- 순서 미보장
- 빠른 검색
용도: 중복 허용x, 요소의 유무만 중요한 경우 사용
ex. 회원 ID, 고유한 항목의 집합add(value) contains(value) remove(value)이렇게 중복 체크할 때 O(n)이기 때문에 성능이 떨어진다.public boolean contains(int value){ for(int data : elementData){ if(data == value){ return true; } } return false; }
이 문제를 해결하기 위해 Hash알고리즘을 사용한다.
Hash알고리즘
배열의 장점은 특정 Index 값을 알고 있다면 검색할때 매우 빠르다.
여기서 Index값과 Data값을 맞추면 검색할 때 매우 유리한데 이게 Hash알고리즘이다.(이래서 중복 허용 x임)Integer[] inputArray = new Integer[10]; inputArray[1] = 1; inputArray[2] = 2; inputArray[5] = 5; inputArray[8] = 8;
[null, 1, 2, null, null, 5, null, null, 8, null]
Data값과 Index값을 똑같이 설정하면 특정 Data를 찾을 때 매우 편하긴 하지만 보이는 바와 같이 메모리 공간 낭비가 크다.
이 문제를 해결하기 위해hashIndex = Data % CAPACITY;Data를 배열 크기로 나눈 나머지를 인덱스 값으로 이용한다.
이게 hashIndex이다.
하지만 여기서 또 문제가 발생할 수 있는데, 나머지가 같은 경우이다.
[null, 1, 2, null, 14, 5, null, null, 8, 99], CAPACITY = 10
이런 배열이 있을 때 Data에 9를 추가하면
99 % 10 = 9
9 % 10 = 9
같은 나머지를 가지기 때문에 index 9 에서 충돌한다.
이를 해결하기 위해 9번 index안에 또 배열을 만들어 그 안에서 또 비교한다. 이는 최악의 경우 O(n)의 성능을 보이지만 O(1)인 경우가 대부분일 것이다.
public class Main {
static final int CAPACITY = 10;
public static void main(String[] args) {
//{1,2,5,8,14,99}
LinkedList<Integer>[] buckets = new LinkedList[CAPACITY];
System.out.println("buckets = "+ Arrays.toString(buckets));
for(int i=0; i<CAPACITY; i++){
buckets[i] = new LinkedList<>();
}
System.out.println("buckets = "+ Arrays.toString(buckets));
add(buckets,1);
add(buckets,2);
add(buckets,5);
add(buckets,8);
add(buckets,14);
add(buckets,99);
add(buckets,9); //중복
System.out.println();
System.out.println("buckets = "+ Arrays.toString(buckets));
//검색
int searchValue = 9;
boolean contains = contains(buckets,searchValue);
System.out.println("bucket.contains("+searchValue+") = "+contains);
}
private static void add(LinkedList<Integer>[] buckets, int value){
int hashIndex = hashIndex(value);
LinkedList<Integer> bucket = buckets[hashIndex]; //O(1)
if(!bucket.contains(value)){ //같은 값 있는지 확인
bucket.add(value);
}
}
static int hashIndex(int value){
return value % CAPACITY;
}
private static boolean contains(LinkedList<Integer>[] buckets, int searchValue){
int hashIndex = hashIndex(searchValue);
LinkedList<Integer> bucket = buckets[hashIndex];
return bucket.contains(searchValue);
}
}배열의 이름을
buckets로 만들고LinkedList는 하나의 바구니이다.
정리하면 배열 안에LinkedList가 들어있고,LinkedList안에 데이터가 들어가는 구조이다.
Hash알고리즘으로 Set 구현
Set: 중복을 허용하지 않고 순서를 보장하지 않는 자료구조
static final int DEFAULT_INITIAL_CAPACITY = 16; LinkedList<Integer>[] buckets; private int size = 0; private int capacity = DEFAULT_INITIAL_CAPACITY;
buckets: 연결리스트를 배열로사용하고 배열 안에 연결리스트가 들어있다. 해시 인덱스가 충돌이 발생하면 같은 연결 리스트 안에 여러 데이터를 저장.
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)); //숫자를 넘기면 index 위치를 지우기 때문에 bucket 안에 있는 값을 찾아 지운다 if(result){ size--; return true; }else{ return false; } } private int hashIndex(int value){ return value%capacity; }
initBuckets: 연결리스트를 생성해서 배열을 채운다. 배열의 모든 index위치에는 연결리스트가 들어있다.
contains(): 해시 인덱스를 사용해서 데이터를 확인.
숫자가 아닌 문자열 데이터를 저장하려면 어떻게 해야할까?
- index가 문자열과 같아야하는데
hashCode를 이용한다.
- 해시함수(Hash Function)
- 임의의 데이터를 입력받아 고정된 길이의 hashCode를 출력하는 함수
- 다른 데이터를 입력했을 때 같은 해시코드가 출력될 수 있는데 이를 해시 충돌이라 함
- 해시코드(Hash Code)
- 데이터를 대표하는 값
"A"의 해시코드는 65,"B"의 해시코드는 66 등- 해시 인덱스(Hash Index)
- 해시 인덱스는 데이터의 저장위치를 결정, 해시코드를 통해 생성
- 해시코드의 결과와 배열의 크기를 나눈 나머지를 통해 구한다.
Java의 HashCode()
문자열이 아닌 객체의 해시코드를 정의할 때는 자바가 제공하는
hashCode()메서드를 이용한다.
클래스 생성 시,equals()와hashCode()메서드를 만들어준다.@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); }
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()); //각 class 마다 hashCode 를 Override 해둠 Integer i = 10; String strA = "A"; String strAB = "AB"; System.out.println("10.hashCode() = "+i.hashCode()); System.out.println("A's hashCode() = "+strA.hashCode()); System.out.println("AB's hashCode() = "+strAB.hashCode()); //둘은 같을까? 다를까? 인스턴스는 다르지만, equals 는 같다 Member member1 = new Member("idA"); Member member2 = new Member("idA"); //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()); System.out.println((member1.hashCode() == member2.hashCode())); }
결과: obj1.hashCode() = 762218386 obj2.hashCode() = 796533847 10.hashCode() = 10 A's hashCode() = 65 AB's hashCode() = 2081 (member1 == member2) = false (member1 equals member2) = true (member1.hashCode() = 104101 (member2.hashCode() = 104101 true자바의 동일성, 동등성
- 동일성(Identity):
==연산으로 객체의 참조가 동일한 객체를 가리키는지 확인- 동등성(Equality):
equals()메소드를 통해 두 객체가 논리적으로 동등한지 확인
객체를 직접 만드는 경우 hashCode()를 재정의 해야한다!!
항상 해시자료구조에 데이터를 저장하는 경우 hashCode()를 구현해야한다.
구현하지 않으면 객체를 여러개 생성 시 데이터가 같아도 참조값이 다를 수 있어 데이터를 구분할 수 없는 문제가 발생하는 등 여러 문제가 생긴다.
