10. HashMap
Map interface는 아래와 같이 구성된다. HashMap이라는 이름이 붙은 이유는 저장하는 방식이 Hashing이기 떄문이다. 그리고 탐색을 할때 빠른 속도를 보장한다.
HashMap의 class정의는 아래와 같이 구성이 된다.
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
transient Node<K,V>[] table;
...
// inner class가 따로 정의되어 있다.
// Map.Entry를 구현한다. 여기에서 Key와 Value가 정의 된다.
// 특이한 점은 key는 한 번 정의되면 바뀔 수가 없다.
static class Node<K,V> implements Map.Entry<K,V> {
final K key;
V value;
...
}
}
Plain Text
복사
HashMap: Methods
HashMap의 정의 함수는 위와같이 구성된다.
HashMap 내장 함수는 위와같이 구성된다.
여기에서 중요한 것은 어떻게 데이터를 가져오고 저장하는지이다. 그래서 get과 put 키워드가 존재하고 remove를 활용하여 데이터를 삭제한다.
containsKey와 containsValue를 통하여 데이터의 키와 값을 찾을 수도 있다.
또 하나 특이한 것은 keySet과 values이다. 이것은 key또는 value를 모두 가져오는 것으로 반환형을 보면 keySet은 Unique한 Set을 사용하지만 values는 Collection을 사용하여 중복을 허용한다.
HashMap: Example 1
HashMap<String,String> 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("Please enter id and password.");
System.out.print("id: ");
//user의 입력을 받은 다음 뒤에 나오는 spacebar을 제거해 준다.
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 does not exist.");
continue;
} else {
if(!(map.get(id)).equals(password)) {
System.out.println("password does not match.");
} else {
System.out.println("welcome.");
break; }
}
}
s.close();
Plain Text
복사
HashMap: Example 2
HashMap<String,Integer> map = new HashMap<>();
map.put("Kim Java", Integer.valueOf(90));
map.put("Kim Java", Integer.valueOf(100));
map.put("Lee Java", Integer.valueOf(100));
map.put("Kang Java", Integer.valueOf(80));
map.put("Ahn Java", Integer.valueOf(90));
Set<Map.Entry<String,Integer>> set = map.entrySet();
Iterator<Map.Entry<String,Integer>> it = set.iterator();
while(it.hasNext()) {
Map.Entry<String,Integer> e = (Map.Entry<String,Integer>)it.next();
System.out.println("name: " + e.getKey() + ", score: " + e.getValue());
}
Set<String> keys = map.keySet();
System.out.println("participants: " + keys);
Collection<Integer> values = map.values();
Iterator<Integer> it2 = values.iterator();
int total = 0;
while(it2.hasNext()) {
Integer i = (Integer)it2.next();
total += i.intValue();
}
System.out.println("total: " + total);
System.out.println("average: " + (float)total/set.size());
System.out.println("max: " + Collections.max(values));
System.out.println("min: " + Collections.min(values));
Plain Text
복사
HashMap: Example 3
HashMap 안에 HashMap이 존재하는 경우
public class Lecture {
static HashMap<String,HashMap<String,String>> phoneBook = new HashMap<>();
public static void main(String[] args) {
addPhoneNo("friend", "Lee Java", "010-111-1111");
addPhoneNo("friend", "Kim Java", "010-222-2222");
addPhoneNo("friend", "Kim Java", "010-333-3333");
addPhoneNo("work", "Kim Daeri", "010-444-4444");
addPhoneNo("work", "Kim Daeri", "010-555-5555");
addPhoneNo("work", "Park Daeri", "010-666-6666");
addPhoneNo("work", "Lee Guajang", "010-777-7777");
addPhoneNo("laundary", "010-888-8888");
// 들어가 있는 정보 모두 출력함
printList();
}
static void addPhoneNo(String groupName, String name, String tel) {
addGroup(groupName);
HashMap<String,String> group = phoneBook.get(groupName);
// 핸드폰 번호는 모두 다를 가능성이 이름에 비해 많기 때문에 전화번호를 key로 하고 value를 이름으로 작성했다.
group.put(tel, name);
}
// 같은 groupName이 없다면 phoneBook에 삽입한다.
static void addGroup(String groupName) {
if(!phoneBook.containsKey(groupName)) phoneBook.put(groupName, new HashMap<String,String>());
}
// 매개변수가 2개인 경우의 삽입
static void addPhoneNo(String name, String tel) {
addPhoneNo("others", name, tel);
}
// printList를 통하여 모든 Entry를 출력한다.
static void printList() {
Set<Map.Entry<String,HashMap<String,String>>> set = phoneBook.entrySet();
Iterator<Map.Entry<String,HashMap<String,String>>> it = set.iterator();
while(it.hasNext()) {
//3개의 데이터를 가져온다.
Map.Entry<String,HashMap<String,String>> e = (Map.Entry<String,HashMap<String,String>>)it.next();
//가져온 데이터들을 또 작게 나눈다.
Set<Map.Entry<String,String>> subset = e.getValue().entrySet();
Iterator<Map.Entry<String,String>> subIt = subset.iterator();
System.out.println(" * " + e.getKey() + "[" + subset.size() + "]");
while(subIt.hasNext()) {
Map.Entry<String,String> subE = (Map.Entry<String,String>)subIt.next();
String telNo = subE.getKey();
String name = subE.getValue();
System.out.println(name + " " + telNo);
}
System.out.println();
}
}
}
Plain Text
복사
HashMap: Example 4
character의 갯수를 HashMap을 활용하여 계산하기
public class Lecture {
public static void main(String[] args) {
String[] data = {"A", "K", "A", "K", "D", "K", "A", "K", "K", "K", "Z", "D"};
HashMap<String,Integer> map = new HashMap<>();
for(int i=0; i<data.length; i++) {
//만약 이미 포함된 값이라면 character의 갯수는 1 증가할 것이다.
if(map.containsKey(data[i])) {
Integer value = map.get(data[i]);
map.put(data[i], Integer.valueOf(value.intValue() + 1));
} else {
map.put(data[i], Integer.valueOf(1));
}
}
// 카운트 된 갯수만큼 bar을 시각적으로 보여준다.
Iterator<Map.Entry<String,Integer>> it = map.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<String,Integer> entry = it.next();
int value = 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);
}
}
Plain Text
복사
HashMap: Hashing
HashMap이라는 것은 HashFunction을 사용하여서 데이터를 저장하고 탐색도 하는 것을 이야기 한다.
만약 그러다가 같은 위치에 저장하라고 HashFunction의 return값이 나왔다면
연결리스트로 해당 위치에 데이터를 계속 연결해 준다.
•
on hashing performance
Hash Function으로 Hash Value를 계산하면 매우 빠르다. 하지만 중복된 데이터가 많은 slot(bucket)에서의 속도는 빠르지 않다. 그래서 가급적 한 슬롯에서는 데이터가 하나만 있는 것이 최적이다.
•
HashMap은 hashCode를 사용한다.
만약 클래스 Object의 hashCode()를 사용하면 객체마다 다른 HashCode가 나오게 된다.
그래서 hashCode()를 Override하여 사용해야 한다. 그래야만 다른 객체간의 비교에서도 hashCode가 동일하게 나올것이다. 그렇기에 hashCode와 equals가 같은 semantic이 되도록 해주어야 한다.
11. TreeMap
TreeMap역시 Map에서 Tree형태로 구현한 것이다. 특히나 Red-Black tree형태로 자료를 저장하고 있다. 그래서 기본적으로 key로 sorting을 한다. 만약 key가 비교 불가능하면 Exception이 발생한다.
일밙거으로 HashMap이 TreeMap에 비해서 빠르다. 하지만 데이터를 정렬하여 저장하고자 할때는 TreeMap이 훨씬 낫다.
TreeMap: Methods
TreeMap: Example
위에서 나온 character 카운트하는 예제와 동일하지만 유일하게 TreeMap을 사용하였다는 차이점이 존재한다.
public class Lecture {
public static void main(String[] args) {
String[] data = {"A","K","A","K","D","K","A","K","K","K","Z","D"};
TreeMap<String,Integer> map = new TreeMap<>();
for(int i=0; i<data.length; i++) {
if(map.containsKey(data[i])) {
Integer value = map.get(data[i]);
map.put(data[i], Integer.valueOf(value.intValue() + 1));
} else {
map.put(data[i], Integer.valueOf(1));
}
}
Iterator<Map.Entry<String,Integer>> it = map.entrySet().iterator();
System.out.println("=== basic sort ===");
while(it.hasNext()) {
Map.Entry<String,Integer> entry = it.next();
int value = entry.getValue().intValue();
System.out.println(entry.getKey() + ": " + printBar('#', value) + " " + value);
}
System.out.println();
Set<Map.Entry<String,Integer>> set = map.entrySet();
List<Map.Entry<String,Integer>> list = new ArrayList<>(set);
Collections.sort(list, new ValueComparator<Map.Entry<String,Integer>>());
it = list.iterator();
// 차이점이 이렇게 sort를 했다는 차이점이 존재한다.
System.out.println("=== sort by the value ===");
while(it.hasNext()) {
Map.Entry<String,Integer> entry = it.next();
int value = entry.getValue().intValue();
System.out.println(entry.getKey() + ": " + printBar('#', value) + " " + value);
}
}
// inner class
@SuppressWarnings("unchecked") // anotation으로 경고가 나오지 말라고 하는 것
static class ValueComparator<T> implements Comparator<T> {
public int compare(Object o1, Object o2) {
if(o1 instanceof Map.Entry && o2 instanceof Map.Entry) {
Map.Entry<String,Integer> e1 = (Map.Entry<String, Integer>)o1;
Map.Entry<String,Integer> e2 = (Map.Entry<String, Integer>)o2;
int v1 = e1.getValue().intValue();
int v2 = e2.getValue().intValue();
return v2 - v1;
}
return -1;
}
}
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);
}
}
Plain Text
복사
