Java 자료구조, 컬렉션 프레임웍 - 4, (Hash, Set, Map)

Hash

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 빠르게 진행 
데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가)  한 쌍으로 존재하고, 
key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됨

예시
만약, hello 라는 문자열을 정수형 key 값으로 바꾼다면, h + e + l + l + o -> 104 +101 + 108 + 108 + 111 = 532라는 해시코드로 변환 할 수 있음

HashSet

Set 인터페이스를 구현한 대표적인 컬렉션, 중복 허용 X,
요소 추가시 add()나 addAll()사용, 중복 요소 추가 시도 시 false 반환

equals메서드를 이용한 비교에 의해, true를 얻은 두 객체에 대해 얻은 해시코드는 같아야 한다.

equals메서드를 이용한 비교에 의해, false를 얻은 두 객체에 대해 얻은 해시코드는 반드시 다를 필요는 없지만, 
해싱을 사용하는 컬렉션의 성능 향상을 위해 다른 것이 좋다.

중복을 허용하지 않으면서 저장순서는 유지하고 싶다면 LinkedHashSet을 사용해야 한다.
    

참고    HashSet은 내부적으로 HashMap을 이용해서 만들어졌다.
String 클래스는 문자열의 내용으로 해시코드를 만들어 내기 때문에 같은 문자열에 대한 hashCode()호출은 항상 동일한 해시코드를 반환하지만, 
Object 클래스는 객체의 주소로 해시코드를 만들어내기 때문에, 실행할 때마다 해시코드 값이 달라질 수 있다.
String 클래스는 Object로부터 받은 hashCode()를 오버라이딩 해놨기 때문

TreeSet

이진 검색 트리(binary search tree) 자료구조 형태로 데이터 저장
정렬, 검색, 범위 검색에 높은 성능
이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리'로 구현되어 있다.

이진 트리
여러 개의 노드가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며, '루트'라고 불리는 하나의 노드부터 시작해 확장해 나간다.

첫 번째 저장한 값은 루트가 되고, 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교해가며 트리를 따라 내려간다.
작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다

컴퓨터는 값을 알아서 비교하지 못하기 때문에, 저장되는 객체가 Comparable을 구현하던가,
TreeSet에게 Comparator을 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면 예외가 발생한다

데이터를 순차적으로 저장하지 않고, 특정 위치를 찾아 저장/삭제하기 때문에 링크드 리스트보다 데이터의 추가/삭제 시간이 더 걸린다.
대신 검색과 정렬 기능이 더 좋다.

headSet메서드와 tailSet 메서드를 사용하면, 저장된 객체 중 지정된 기준 값보다 작은 값의 객체들과 큰 값의 객체들을 얻을 수 있다

HashMap, Hashtable  (HashMap의 구버전이 Hashtable, HashMap 사용 권장)

Map을 구현했으므로 키, 값을 묶어 하나의 데이터로 저장, 
해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 좋음

키, 값은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기보다, 
하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터 무결성적인 측면에서 더 바람직하다.

예시

비객체지향적 코드
Object[] key;
Object[] value;

객체지향적 코드
Entry[] table;
class Entry{
    Object key;
    Object value;
}                           // 클래스에 멤버변수로 키값을 선언하고, 그 클래스를 이용한 배열을 만든다

     
키, 값을 각각 Object타입으로 저장하기 때문에 어떤 객체도 저장할 수 있지만,
키는 주로 String을 대문자 또는 소문자로 통일해서 사용한다

키      중복 허용 X     // 값을 찾는데 사용되기 때문에 유일해야함
값      중복 허용 O

해싱과 해시함수
해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다.
        
해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 되어있다. p.651
배열의 각 요소에는 링크드리스트가 저장되어 있어서, 실제 데이터는 링크드 리스트에 담기게 된다.

배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n

실제로 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다.
Object클래스의 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어내기 때문에,
모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌륭한 방법이다.

TreeMap

    이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터 저장

HashMap과 TreeMap

    대부분의 검색의 경우, HashMap이 좋다.
    범위 검색이나 정렬이 필요한 경우에만 TreeMap 사용

Properties

    Hashtable을 상속받아 구현한 것
    Hashtable은 키 값을 (Object, Object)로 저장하지만 Properties는 (String, String)으로 단순하게 저장
    
    주로 애플리케이션의 환경설정과 관련된 속성(Property)을 저장하는데 사용
    데이터를 파일로부터 읽고 쓰는 편리한 기능 제공

Collections로 할 수 있는 일

1. 컬렉션의 동기화
멀티 쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근할 수 있기 때문에, 
데이터의 일관성(consistency)을 유지하기 위해서는 공유되는 객체에 동기화(synchronization)가 필요하다

2. 변경 불가 컬렉션 만들기
컬렉션에 저장된 데이터를 보호하기 위해 컬렉션을 변경할 수 없게, 즉 읽기전용으로 만들어야 할 때가 있다.
주로 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다보면 데이터가 손상될 수 있다.

3. 싱글톤 컬렉션 만들기
단 하나의 객체만을 저장하는 컬렉션을 만들고 싶은 경우 사용
매개변수로 저장할 요소를 지정하면, 해당 요소를 저장하는 컬렉션을 반환,
그리고 반환된 컬렉션은 변경할 수 없다.

4. 한 종류의 객체만 저장하는 컬렉션 만들기
컬렉션에 모든 종류의 객체를 저장할 수 있다는 것은 장점이기도 하고 단점이기도 하다.
대부분의 경우 한 종류의 객체를 저장하며, 컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한하고 싶을 때 사용
지네릭스로도 처리할 수 있지만 지네릭스는 jdk1.5부터 등장하므로 이전에 작성된 코드와의 호환성 때문에 사용

 

 

그리고 collection이 있고, collections이 있는데

java.util.Collection은 인터페이스이고, java.util.Collections는 클래스이다.

각각의 역할이 다르므로 기억해두자.