[JAVA] 17. 컬렉션 프레임워크(TreeSet, HashMap, HashTable, 해싱과 해시함수, TreeMap, Properties, Collections)

https://hyejin.tistory.com/584

[JAVA] 17. 컬렉션 프레임워크 (Comparator, Comparable, HashSet, TreeSet)

 

1️⃣ TreeSet

TreeSet은 이진 검색 트리(binary search tree) 라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 

이진 검색 트리 (binary search tree)
- 모든 노드는 최대 두 개의 자식노드를 가질 수 있다. 
- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식 노드의 값은 부모노드의 값보다 커야한다. 
- 노드의 추가 삭제에 시간이 걸린다. (순차적으로 저장하지 않으므로)
- 검색(범위 검색)과 정렬에 유리하다. 
- 중복된 값을 저장하지 못한다. 

-> 저번에 HashSet으로 Lotto 번호를 만드는 예제에서는 정렬하는 코드가 들어갔었는데 TreeSet은 이미 정렬을 하기 때문에 정렬하는 코드를 넣을 필요가 없다. 

 

 

-> subSet() 을 이용해서 범위검색(range search)를 할 때 시작 범위는 포함되지만 끝 범위는 포함되지 않으므로 result1에는 c로 시작하는 단어까지만 검색 결과에 포함되어 있다. 

만일 끝 범위인 d로 시작하는 단어까지 포함시키고자 한다면, 아래와 같이 끝 범위에 'zzz'와 같은 문자열을 붙이면 된다. 

(d로 시작하는 단어 중에서 'dzzz' 다음에 오는 단어는 없을 것이기 때문에 d로 시작하는 모든 단어들이 포함될 것이다.)

 

 

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

 

 

 

2️⃣ HashMap, HashTable

HashTable과 HashMap은 Vector와 Arraylist의 관계와 같아서 HashTable보다는 새로운 버전인 HashMap을 사용할 것을 권한다. 

HashMap은 Map을 구현했으므로 Map의 특징, 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다. 

그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다. 

-> HashMap은 Entry라는 내부 클래스를 정의하고, 다시 Entry타입의 배열을 선언하고 있다. 

 

HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉 (Object, Object)의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다.

 

키 key : 컬렉션 내의 키(key) 중에서 유일해야한다. 
값 value : 키(key)와 달리 데이터의 중복을 허용한다. 

-> 키는 저장된 값을 찾는데 사용되는 것이기 때문에 컬렉션 내에서 유일해야한다. 

-> 즉, HashMap에 저장된 데이터를 하나의 키로 검색했을 때 결과가 단 하나이어야 한다는 것이다. 

 

 

 

-> 세번째의 asdf 키는 이미 존재하기 때문에 새로 추가되는 것이 아니라 기존의 값을 덮어쓴다. 그래서 asdf의 연결된 값은 1234이다. 

Map은 값의 중복은 허용하지만 키는 중복을 허용하지 않기 때문에 저장하려는 두 데이터 중에서 어느 쪽을 키로 할 것인지 잘 결정해야 한다. 

 

 

(Map.Entry는 Map의 내부인터페이스이다.)

 

 

-> 문자열 배열에 담긴 문자열을 하나씩 읽어서 HashMAp에 키로 저장하고 값으로 1을 저장한다. 

HashMap에 같은 문자열이 키로 저장되어 있는지 containsKey()로 확인하여 이미 저장되어 있는 문자열이면 값을 1 증가시킨다. 

 

 

3️⃣ 해싱과 해시 함수 

 해싱이란 해시함수(hash function)을 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. 

해시함수는 데이터가 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, HashTable 등이 있다. 

 

-> 해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 되어 있다. 

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다. 

 

 

 

HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object 클래스에 정의된 hashCode()를 해시함수로 사용한다. 

Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 방법이다. 

 

String 클래스의 경우에는 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다.

그래서 서로 다른 String 인스턴스일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출하면 같은 해시코드를 얻는다. 

 

서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다. 

따라서 새로운 클래스를 정의할 때 equals()를 재정의오버라이딩 해야한다면 hashCode()도 같이 재정의해서 equals()의 결과가 true인 두 객체의 해시코드hashCode()의 결과값이 항상 같도록 해주어야 한다. 

-> 그렇지 않으면 해싱을 구현한 클래스에서는 equals()의 호출결과가 true이지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다. 

 

 

4️⃣ TreeMap

TreeMap은 이름에서도 알 수 있듯이 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다. 

-> 그래서 검색과 정렬에 적합한 컬렉션 클래스이다. 

 

(검색에 관한 대부분의 경우에는 HashMap이 TreeMap보다 더 뛰어나다. HashMap을 사용하는 것이 좋다. 근데 범위 검색이나 정렬이 필요한 경우에 대해서는 TreeMap을 사용하면 된다.)

 

 

5️⃣ Properties 

Properties는 HashMap의 구버전인 Hashtable을 상속받아 구현한 것으로 Hashtable은 키와 값을 (Object, Object)의 형태로 저장하는데 비해 Properties는 (String,String)의 형태로 저장하는 보다 단순화된 컬렉션 클래스이다. 

 

stringPropertyNames() 

: Properties에 저장되어 있는 모든 키key 를 Set에 담아서 반환한다. 

-> 여기서는 Iterator의 구버전 Enumeration 을 사용해서 element 값을 출력했다. 

 

setProperty() 

: 지정된 키와 값을 저장한다. 이미 존재하는 키면 새로운 값으로 바꾼다. 

-> 데이터를 저장하는 setProperty()는 단순히 Hashtable의 put메서드를 호출할 뿐이다. 

setProperty()는 기존에 같은 키로 저장된값이 있는 경우 그 값을 Object 타입으로 반환하며, 그렇지 않을 때는 Null 을 반환한다. 

 

getProperty()

: Properties에 저장된 값을 읽어오는 일을 하는데, 만일 읽어오려는 키가 존재하지 않으면 지정된 기본값을 반환한다.

 

 

 

6️⃣ Collections

Arrays가 배열과 관련된 메서드를 제공하는 것처럼, Collections는 컬렉션과 관련된 메서드를 제공한다. 

(컬렉션을 위한 static 메서드 제공) 

 

- 컬렉션의 동기화

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

 

Vector와 Hashtable과 같은 구버전의 클래스들은 자체적으로 동기화 처리가 되어 있는데, 멀티쓰레드 프로그래밍이 아닌 경우에는 불필요한 기능이 되어 성능을 떨어트리는 요인이 된다.

 

그래서 새로 추가된 ArrayList와 HashMap과 같은 컬렉션은 동기화를 자체적으로 처리하지 않고 필요한 경우에만 java.util.Collections 클래스의 동기화 메서드를 이용해서 동기화 처리가 가능하도록 변경한다. 

 

 

- 변경불가 컬렉션 만들기

컬렉션에 저장된 데이터를 보호하기 위해서 컬렉션을 변경할 수 없게, 읽기 전용으로 만들수 있다. 

(주로 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다보면 데이터가 손상될 수 있는데, 이를 방지하기 위해 사용)

 

 

- 싱글톤 컬렉션 만들기

단 하나의 객체만을 저장하는 컬렉션을 만들고 싶을 경우가 있다. 

-> 매개변수로 저장할 요소를 지정하면 , 해당 요소를 저장하는 컬렉션을 반환하고 이 반환된 컬렉션은 변경할 수 없다.

 

 

- 한 종류의 객체만 저장하는 컬렉션 만들기

-> 컬렉션에 모든 종류의 객체를 저장할 수 있다는 것은 장점이기도 하고 단점이기도 하다. 

대부분의 경우 한 종류의 객체를 저장하며, 컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한하고 싶을 때 이 메서드를 사용한다. 

 

컬렉션에 저장할 요소의 타입을 제한한다는 것은 지네릭스로 간단하게 처리할 수 있다!( 근데 이런 메서드를 제공하는 이유는 호환성 때문)

 

 

 

❗️ 정리 

ArrayList : 배열 기반, 데이터의 추가와 삭제에 불리, 순차적인 추가/삭제는 제일 빠름. 임의의 요소에 대한 접근성이 뛰어남 

LinkedList:  연결 기반, 데이터의 추가와 삭제에 유리, 임의의 요소에 대한 접근성이 좋지는 않다. 

HashMap : 배열과 연결이 결합된 형태, 추가, 삭제, 검색, 접근성이 모두 뛰어남. 검색에는 최고성능을 보인다. 

TreeMap: 연결기반, 정렬과 검색(특히 범위검색)에 적합, 검색 성능은 HashMap보다는 떨어짐

Stack: Vector를 상속받아 구현(LIFO) 

Queue: LinkedList가 Queue인터페이스를 구현 (FIFO)

Properties : HashTable을 상속받아 구현(String, String)

HashSet : HashMap을 이용해서 구현 

TreeSet: TreeMap을 이용해서 구현 

LinkedHashMap, LinkedHashSet : HashMap과 HashSet에 저장순서 유지 기능을 추가