TreeSet
TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보여주는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현되어 있다.
그리고 Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.
이진 트리(binary tree)는 링크드리스트처럼 여러 개의 노드(node)가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 루트(root)라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다.
위 아래로 연결된 두 노드를 부모-자식 관계에 있다고 하며 위의 노드를 부모노드, 아래의 노드를 자식노드라 한다. 부모-자식관계는 상대적인 것이며 하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다.
이진 트리의 노드를 코드로 표현하면 다음과 같다.
class TreeNode{
TreeNode left; //왼쪽 자식 노드
Object element; //객체를 저장하기 위한 참조변수
TreeNode right; //오른쪽 자식 노드
}데이터를 저장하기 위한 Object타입의 참조변수 하나와 두 개의 노드를 참조하기 위한 두 개의 참조변수를 선언했다.
이진 검색 트리(binary search tree)는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진트리이다.
예를 들어 데이터를 5,1,7의 순서로 저장한 이진트리의 구조는 다음과 같다.
5의 left, right는 각각 1, 7을 가리킨다.
이진 검색 트리에 7,4,9,1,5의 순서로 값을 저장한다고 가정하면 다음과 같은 순서로 저장이된다.
- 7 저장
- 비교(4<7) , 7의 왼쪽자식노드에 4저장
- 비교(9>7), 7의 오른쪽 자식 노드에 9저장
- 비교 (1<7), 7의 왼쪽 자식노드 4랑비교, (1<4) , 4의 왼쪽 노드에 저장
- 비교(5<7), 7의 왼쪽 자식 노드 4랑비교, (4<5), 4의 오른쪽 노드에 저장
첫 번째로 저장되는 값은 루트가 되고, 두번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 작은 값은 왼쪽에 큰값은 오른쪽에 저장한다. 이렇게 트리를 구성하면 , 왼쪽 마지막 레벨이 제일 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰값이 된다. 앞서 살펴본 것처럼, 컴퓨터는 알아서 값을 비교하지 못한다.
TreeSet에 저장되는 객체가 Comparable을 구현하던가 아니면, TreeSet에게 Compartor를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면 TreeSet에 객체를 저장할 때 예외가 발생한다.
왼쪽 마지막 값에서부터 오른쪽 값까지 값을 왼쪽노드→부모노드→오른쪽 노드 순으로읽어오면 오름차순으로 정렬된 순서를 얻을 수 있다. TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색(range search), 예를 들면 3과 7사이의 범위에 있는 값을 검색이 매우 빠르다.
저장된 값의 개수에 비례해서 검색 시간이 증가하긴 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교횟수가 3~4번만 증가할 정도로 검색효율이 뛰어난 자료구조이다.
트리는 데이터를 순차적으로 저장하는 것이 아니라 저장위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드리스트보다 데이터의 추가/삭제 시간은 더 걸린다, 대신 배열이나 링크드 리스트에 비해 검색과 정렬기능이 더 뛰어나다.
이진 검색 트리(binary search tree)는
-모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
-왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야 한다.
-노드의 추가 삭제에 시간이 걸린다(순차적으로 저장하지 않으므로)
-검색(범위검색)과 정렬에 유리하다
-중복된 값을 저장하지 못한다.
TreeSet의 생성자와 메서드
TreeSet() : 기본생성자
TreeSet(Collection c) : 주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp) : 주어진 정렬조건으로 정렬하는 TreeSet을 생성
TreeSet(SortedSet s) : 주어진 SortedSet을 구현한 컬렉션을 저장하는 TreeSet을 생성
boolean add(Object o) : 지정된 객체(o)를 Collection에 추가
boolean addALl(Collection c) : Collection(c)의 객체들을 Collection에 추가
void clear() : 지정된 모든 객체를 삭제한다.
Object clone() : TreeSet을 복제하여 반환한다.
Comparator comparator() : TreeSet의 정렬기준(Comparator)를 반환한다.
boolean contains(Object o) : 지정된 객체가 포함되어 있는지를 확인한다.
boolean containsAll(Collection c) : Collection의 객체들이 포함되어 있는지 확인한다.
NavigableSet descendingSet() : TreeSet에 저장된 요소들을 역순으로 정렬해서 반환
Object first() : 정렬된 순서에서 첫번째 객체를 반환한다.
Object floor(Object o) : 지정된 객체와 같은 객체를 반환, 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
SortedSet headSet(Object toElement) : 지정된 객체보다 작은 값의 객체들을 반환한다.
NavigableSet headSet(Object toElement, boolean inclusive): 지정된 객체보다 작은 값의 객체들을 반환, inclusive가 true이면, 같은 값의 객체도 포함
Object higher(Object o) : 지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null
boolean isEmpty() : TreeSet이 비어있는지 확인한다.
Iterator iterator() : TreeSet의 Iterator를 반환한다.
Object last() : 정렬된 순서에서 마지막 객체를 반환한다.
Object lower(Object o) : 지정된 객체보다 작은 값을 가진 객체중 제일 가까운 값의 객체를 반환, 없으면 null
Object pollFirst() : TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환
Object pollLast() : TreeSet의 마지막 번째 요소(제일 큰 값의 객체)를 반환
booelan remove(Object o) : 지정된 객체를 삭제한다.
boolean retainAll(Collection c) : 주어진 컬렉션과 공통된 요소만을 남기고 삭제한다.(교집합)
int size() : 저장된 객체의 개수를 반환한다.
Spliterator spliterator() : TreeSet의 spliterator를 반환
SortedSet subSet(Object fromElement, Object toElement) : 범위 검색(fromElement와 toElement사이)의 결과를 반환한다.(끝 범위인 toElement는 범위에 포함되지 않음)
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) : 범위 검색의 결과를 반환한다. true값이면 시작값 또는 끝값이 포함된다.
SortedSet tailSet(Object fromElement) : 지정된 객체보다 큰 값의 객체들을 반환한다.
Object[] toArray() : 저장된 객체를 객체배열로 반환한다.
Object[] toArray(Object[] a) : 저장된 객체를 주어진 객체배열에 저장하여 반환한다.
import java.util.*;
public class TreeSetLotto {
public static void main(String[] args) {
Set set = new TreeSet();
for(int i=0; set.size()<6; i++){
int num = (int)(Math.random()*45)+1;
set.add(num);
}
System.out.println(set);
}
}
================================
[9, 17, 25, 34, 41, 45]TreeSet은 저장할때 이미 정렬하기 때문에 HashSet과 달리 따로 정렬할 필요가 없다.
import java.util.*;
public class TreeSetEx1 {
public static void main(String[] args) {
TreeSet set = new TreeSet();
String from = "b";
String to = "d";
set.add("abc"); set.add("alien"); set.add("bat");
set.add("car"); set.add("Car"); set.add("disc");
set.add("dance"); set.add("dZZZZ"); set.add("dzzzz");
set.add("elephant"); set.add("elevator"); set.add("fan");
set.add("flower");
System.out.println(set);
System.out.println("range search : from"+from+" to "+to);
System.out.println("result1 : "+set.subSet(from, to));
System.out.println("result2 : "+set.subSet(from, to+"zzz"));
}
}
======================================
[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : b to d
result1 : [bat, car]
result2 : [bat, car, dZZZZ, dance, disc]subSet()을 이용해서 범위검색(range search)할 때 시작범위는 포함되지만 끝범위는 포함되지 않으므로 result1에는 c로 시작하는 단어까지만 검색결과에 포함되어 있다.
만일 끝 범위인 d로 시작하는 단어까지 포함시키고자 한다면, 아래와 같이 끝 범위에 'zzz'와 같은 문자열을 붙이면된다.
System.out.println("result2 : "+set.subSet(from, to+"zzz"));d로 시작하는 단어 중에서 'dzzz'다음에 오는 단어는 없을 것이기 때문에 d로 시작하는 모든 단어들이 포함될 것이다.
결과를 보면 'abc'보다 'Car'가 앞에 있고, 'dZZZZ'가 'dance'보다 앞에 정렬되어 있는 것을 알 수 있따. 대문자가 소문자보다 우선하기 때문에 대소문자가 섞여 있는 경우 의도한 것과는 다른 범위검색 결과를 얻을 수 있다.
그래서 가능하면 대문자 또는 소문자로 통일해서 저장하는 것이 좋다.
- 반드시 대소문자가 섞여 있어야 하거나 다른 방식으로 정렬해야 하는 경우 Compartor를 이용하면 된다.
문자열의 경우 정렬순서는 문자의 코드값이 기준이 되므로, 오름차순 정렬의 경우 코드값의 크기가 작은 순서에서 큰순서, 즉 공백, 숫자, 대문자, 소문자 순으로 정렬되고 내림차순의 경우 그 반대가 된다.
public class AsciiPrint {
public static void main(String[] args) {
char ch =' ';
//공백 이후의 문자들을 출력한다.
for(int i=0; i<95; i++)
System.out.print(ch++);
}
}
==========================
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWX
YZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~- 출력된 실행결과의 첫번째 문자는 공백문자이다.
import java.util.*;
public class TreeSetEx2 {
public static void main(String[] args) {
TreeSet set = new TreeSet();
int[] score = {80,95,50,35,45,65,10,100};
for(int i=0; i<score.length; i++)
set.add(new Integer(score[i]));
System.out.println("50보다 작은값: "+set.headSet(new Integer(50)));
System.out.println("50보다 큰값: "+set.tailSet(new Integer(50)));
}
}
=======================================================
50보다 작은값: [10, 35, 45]
50보다 큰값: [50, 65, 80, 95, 100]
hashSet에 메서드와 tailSet메서드를 이용하면 , TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값의 객체들과 작은 값의 객체들을 얻을 수 있다.
50보다 작은 값 : 50의 왼쪽 가지 아래
50보다 큰값 : 50의 왼쪽가지아래 이외의 값들
HashMap과 Hashtable
HashTable과 HashMap의 관계는 Vector과 ArrayList의 관계와 같아서 Hashtable보다는 새로운 버전인 HashMap을 사용한 것을 권한다.
HashMap은 Map을 구현했으므로 앞에서 살펴본 Map의 특징 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다. 그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
HashMap이 데이터를 어떻게 저장하는지 확인하기 위해 실제소스의 일부를 보자.
public class HashMap extends AbstractMap, implements Map, Cloneable, Serializable{
transient Entry[] table;
...
static class Entry implements Map.Enty{
final Object key;
Object value;
....
}
}HashMap은 Entry라는 내부 클래스르 정의하고 다시, Entry타입의 배열을 선언하고 있다. 키와 값은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성(integrity)적인 측면에서 더 바람직하다.
- Map.Entry는 Map인터페이스에 정의된 static inner interface이다.
HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉 (Object , Object_의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만, 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다.
키(key) : 컬렉션 내의 키(key)중에서 유일해야 한다.
값(valeu) : 키(key)와 달리 데이터의 중복을 허용한다.
키는 저장된 값을 찾는데 사용되는 것이기 때문에 컬렉션 내에서 유일(unique)해야 한다. 즉 , HashMap에 저장된 데이터를 하나의 키로 검색했을 때 결과가 단 하나이어야 함을 뜻한다. 만일 하나의 키에 대해 여러 검색결과 값을 얻는다면 원하는 값이 어떤 것인지 알 수 없기 때문이다.
예를 들어 사용자ID가 키(key)로 , 비밀번호가 값(value)으로 연결되어 저장된 데이터집합이 있다고 가정하자. 로그인 시에 비밀번호를 확인하기 위해서 입력된 사용자ID에 대한 비밀번호를 검색했을 때, 단 하나의 결과를 얻어야만 올바른 비밀번호를 입력했는지 확인이 가능할 것이다. 만일 하나의 사용자ID에 대해서 두 개 이상의 비밀번호를 얻는다면 어떤 비밀번호가 맞는 것인지 알 수 없다.
HashMap의 생성자와 메서드
HashMap() : HashMap 객체를 생성
HashMap(int initialCapacity) : 지정된 값을 초기용량으로 하는 HashMap 객체를 생성
HashMap(int initialCapacity, float loadFactor) : 지정된 초기용량과 load factor의 HashMap객체를 생성
hashMpa(Map m) : 지정된 Map의 모든 요소를 포함하는 HashMap을 생성
void clear() : HashMap에 저장된 모든 객체를 제거
Object clone() : 현재 HashMap을 복제해서 반환
boolean containsKey(Object key) : HashMap에 지정된 키(key)가 포함되어 있는지 알려준다. (포함되어 있으면 true)
boolean containsValue(Object value) : HashMap에 지정된 값(value)가 포함되어 있는지 알려준다. (포함되어 있으면 true)
Set entrySet() : HashMap에 저장된 키와 값을 엔트리(키와 값의 결합)의 형태로 Set에 저장해서 반환
Object get(Object key) : 지정된 키(key)의 값(객체)을 반환, 못찾으면 null반환
Object getOrDefault(Object key, Object defalutValue) : 지정된 키(key)의 값(객체)을 반환한다. 키를 못찾으면 키본값(defaultValue)로 지정된 객체를 반환
boolean isEmpty() : HashMap이 비어있는지 알려준다.
Set keySet() : HashMap에 저장된 모든 키가 저장된 Set을 반환
Object put (Object key, Object vlaue) : 지정된 키와 값을 HashMap에 저장
Object remove(Object key) : HashMap에서 지정된 키로 저장된 값(객체)를 제거
Object replace(Object key, Object value) : 지정된 키의 값을 지정된 객체(value)로 대체
boolean replace(Object key, Object oldValue, Object newValue) : 지정된 키와 객체(oldValue)가 모두 일치하는 경우에만 새로운 객체(newValue)로 대체
int size() : HashMap에 저장된 요소의 개수를 반환
Collections values() : HashMap에 저장된 모든 값을 컬렉션의 형태로 반환
import java.util.*;
public class HashMapEx1 {
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("myId", "1234");
map.put("asdf", "1111");
map.put("asdf", "1234");
Scanner s = new Scanner(System.in);
while(true){
System.out.println("Id와 Password를 입력해주세요.");
System.out.print("id : ");
String id = s.nextLine().trim();
System.out.print("password : ");
String password = s.nextLine().trim();
System.out.println();
if(!map.containsKey(id)){
System.out.println("입력하신 id는 존재하지 않습니다. 다시 입력해주세요");
continue;
}else{
if(!(map.get(id)).equals(password)){
System.out.println("비밀번호가 일치하지 않습니다. 다시 입력해주세요.");
}else{
System.out.println("id와 비밀번호가 일치합니다.");
break;
}
}
}
}
}
===============================
Id와 Password를 입력해주세요.
id : asdf
password : 1111
비밀번호가 일치하지 않습니다. 다시 입력해주세요.
Id와 Password를 입력해주세요.
id : asdf
password : 1234
id와 비밀번호가 일치합니다.HashMap을 생성하고 사용자 ID와 비밀번호를 키와 값의 쌍(pair)으로 저장한 다음, 입력된 사용자 ID를 키로 HashMap에서 검색해서 얻은 값(비밀번호)을 입력된 비밀번호와 비교하는 예제이다.
HashMap mp = new HashMap();
map.put("myId", "1234");
map.put("asdf", "1111");
map.put("asdf", "1234");위의 코드는 HashMap을 생성하고 데이터를 저장하는 부분인데 이 코드가 실행되고 나면 HashMap에는 다음과 같은 형태로 데이터가 저장된다.
키 (key ) : 값(value)
myid : 1234
asdf : 1234
3개의 데이터쌍을 저장했지만 실제로는 2개 밖에 저장되지 않은 이유는 중복된 키가 있기 때문이다. 세번째로 저장한데이터의 키인 'asdf'는 이미 존재하기 때문에 새로 추가되는 대신 기존의 값을 덮어썻다. 그래서 키 asdf에 연결된 값은 1234가 된다.
Map은 값은 중복을 허용하지만 키는 중복을 허용하지 않기 때문에 저장하려는 두 데이터 중에서 어느 쪽을 키로 할것인지를 잘 결정해야 한다.
- Hashtable은 키나 값으로 null을 허용하지 않지만, HashMap은 허용한다. 그래서 map.put(null);이나 , map.get(null);과 같이 할 수 있다.
import java.util.*;
public class HashMapEx2 {
public static void main(String[] args) {
HashMap map = new HashMap();
map.put("김자바", new Integer(100));
map.put("이자바", new Integer(100));
map.put("강자바", new Integer(90));
map.put("안자바", new Integer(80));
Set set = map.entrySet();
Iterator it = set.iterator();
while (it.hasNext()) {
Map.Entry e = (Map.Entry) it.next();
System.out.println("이름 : " + e.getKey() + ", 점수 : " + e.getValue());
}
set = map.keySet();
System.out.println("참가자 명단 : " + set);
Collection values = map.values();
it = values.iterator();
int total = 0;
while (it.hasNext()) {
Integer i = (Integer) it.next();
total += i.intValue();
}
System.out.println("총점 : " + total);
System.out.println("평균 : " + (float) total / set.size());
System.out.println("최고 점수 : " + Collections.max(values));
System.out.println("최저 점수 : " + Collections.min(values));
}
}
===============================================
이름 : 안자바, 점수 : 80
이름 : 김자바, 점수 : 100
이름 : 강자바, 점수 : 90
이름 : 이자바, 점수 : 100
참가자 명단 : [안자바, 김자바, 강자바, 이자바]
총점 : 370
평균 : 92.5
최고 점수 : 100
최저 점수 : 80HashMap의 기본적인 메서드를 이용해서 데이터를 저장하고 읽어오는 예제이다. entrySet()을 이용해서 키와 값을 함께 읽어 올 수도 있고, keySet()이나 values()를 이용해서 키와 값을 따로 읽어 올 수도 있다.
import java.util.*;
public class HashMapEx3 {
static HashMap phoneBook = new HashMap();
public static void main(String[] args) {
addPhoneNo("친구", "이자바", "010-111-1111");
addPhoneNo("친구", "김자바", "010-222-2222");
addPhoneNo("친구", "김자바", "010-333-3333");
addPhoneNo("회사", "김대리", "010-444-4444");
addPhoneNo("회사", "김대리", "010-555-5555");
addPhoneNo("회사", "박대리", "010-666-6666");
addPhoneNo("회사", "이과장", "010-777-7777");
addPhoneNo("세탁", "010-888-8888");
printList();
}
static void addPhoneNo(String groupName, String name, String tel) {
addGroup(groupName);
HashMap group = (HashMap) phoneBook.get(groupName);
group.put(tel, name); // 이름은 중복될 수 있으니 전화번호를 key로 저장한다.
}
// 그룹 추가 메서드
static void addGroup(String groupName) {
if (!phoneBook.containsKey(groupName))
phoneBook.put(groupName, new HashMap());
}
static void addPhoneNo(String name, String tel) {
addPhoneNo("기타", name, tel);
}
// 전화번호부 전체를 출력하는 메서드
static void printList() {
Set set = phoneBook.entrySet();
Iterator it = set.iterator();
while (it.hasNext()) {
Map.Entry e = (Map.Entry) it.next();
Set subset = ((HashMap) e.getValue()).entrySet();
Iterator subIt = subset.iterator();
System.out.println(" * " + e.getKey() + "[" + subset.size() + "]");
while (subIt.hasNext()) {
Map.Entry subE = (Map.Entry) subIt.next();
String telNo = (String) subE.getKey();
String name = (String) subE.getValue();
System.out.println(name + " " + telNo);
}
System.out.println();
}
}
}
============================
* 기타[1]
세탁 010-888-8888
* 친구[3]
이자바 010-111-1111
김자바 010-222-2222
김자바 010-333-3333
* 회사[4]
이과장 010-777-7777
김대리 010-444-4444
김대리 010-555-5555
박대리 010-666-6666HashMap은 데이터를 키와 값을 모두 Object타입으로 저장하기 때문에 HashMap의 값(value)으로 HashMap을 다시 저장할 수 있다. 이렇게 함으로써 하나의 키에 다시 복수의 데이터를 저장할 수 있다.
먼저 전화번호를 저장할 그룹을 만들고 그룹 안에 다시 이름과 전화번호를 저장하도록 했다. 이때 이름대신 전화번호를 키로 사용헀다는 것을 확인하자. 이름은 동명이인이 있을 수 있지만, 전화번호는 유일하기 떄문이다.
import java.util.*;
public class HashMapEx4 {
public static void main(String[] args) {
String[] data = { "A", "K", "A", "K", "D", "K", "A", "K", "K", "K",
"Z", "D" };
HashMap map = new HashMap();
for (int i = 0; i < data.length; i++) {
if (map.containsKey(data[i])) {
Integer value = (Integer) map.get(data[i]);
map.put(data[i], new Integer(value.intValue() + 1));
} else {
map.put(data[i], new Integer(1));
}
}
Iterator it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry entry = (Map.Entry) it.next();
int value = ((Integer) entry.getValue()).intValue();
System.out.println(entry.getKey() + " : " + printBar('#', value)
+ " " + value);
}
}
public static String printBar(char ch, int value) {
char[] bar = new char[value];
for (int i = 0; i < bar.length; i++)
bar[i] = ch;
return new String(bar); // String(char[] chArr)
}
}
===========================================
A : ### 3
D : ## 2
Z : # 1
K : ###### 6문자열 배열에 담긴 문자열을 하나씩 읽어서 HashMap에 키로 저장하고 값으로 1을 저장한다. HashMap에 같은 문자열이 키로 저장되어 있는지 containsKey()로 확인하여 이미 저장되어있는 문자열이면 값을 1 증가시킨다.
그리고 결과를 printBar()를 이용해서 그래프로 표현했다. 이렇게 하면 문자열 배열에 담긴 문자열들의 빈도수를 구할 수 있다.
한정된 범위 내에 있는 순차적인 값들의 빈도수는 배열을 이용하지만, 이처럼 한정되지 않은 범위의 비순차적인 값들의 빈도수는 HashMap을 이용해서 구할 수 있다.
- 결과를 통해 HashMap과 같이 해싱을 구현한 컬렉션 클래스들은 저장순서를 유지하지 않는다는 사실을 확인하자.
해싱과 해싱함수
해싱이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다. 해시 함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable등이 잇다.
Hashtable은 컬렉션 프레임웍이 도입되면서 HashMap으로 대체되었으나 이전 소스와의 호환성 문제로 남겨두고 있다. 가능하면 Hashtable대신 HashMap을 사용하자.
해싱에서 사용하는 자료구조는 배열과 링크드리스트의 조합으로 되어 있다.
저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그곳에 연결되어 있는 링크드 리스트에 저장하게 된다.
- 검색하고자 하는 값의 키로 해시함수를 호출한다.
- 해시 함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드리스트를 찾는다.
- 링크드리스트에서 검색한 키와 일치하는 데이터를 찾는다
링크드르시트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다.
반면에 배열은 배열의 크기가 커져도, 원하는 요소가 몇 번째에 있는지만 알면 아래의 공식에 의해서 빠르게 원하는 값을 찾을 수 있다.
배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size*n
하나의 링크리스트에 최소한의 데이터만 젖아되려면, 저장될 데이터의 크기를 고려해서 HashMap의 크기를 적절하게 지정해주어야 하고, 해시함수가 서로 다른 키에 대해서 중복된 해시코드의 반환을 최소화해야 한다. 그래야 HashMap에서 빠른 검색시간을 얻을 수 있다.
그래서 해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘이다.
실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다.
Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌룡한 방법이다.
String클래스의 경우 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다.
그래서 서로 다른 String인스턴스일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출하면 같은 해시코드를 얻는다.
HashSet에서 이미 설명했던 것과 같이 서로 다른 두 객체에 대해 equlas()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다. HashMap에서도 같은 방법으로 객체를 구별하며, 이미 존재하는 키에 대한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다.
그래서 새로운 클래스를 정의할 때 equals()를 재정의오버라이딩해야 한다면 hashCode()도 같이 재정의해서 equals()의 결과가 true인 두 객체의 해시코드 hashCode()의 결과값이 항상 같도록 해주어야 한다.
그렇지 않으면 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 equal()의 호출결과가 true이지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다.
- equlas()로 비교한 결과가 false이고, 해시코드가 같은 경우는 같은 링크드리스트에 저장된 서로 다른 두 데이터가 된다.
'Back-end' 카테고리의 다른 글
| 11 컬렉션 프레임웍(6) (0) | 2021.07.10 |
|---|---|
| 04 정확하고 다양한 결과 출력 WHERE절과 연산자 (0) | 2021.07.10 |
| 11 컬렉션 프레임웍(4) (0) | 2021.07.08 |
| 11 컬렉션 프레임웍(3) (0) | 2021.07.07 |
| 11 컬렉션 프레임웍(2) (0) | 2021.07.06 |
