HashMap, Hashtable 클래스

[HashMap, Hashtable 클래스]

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable{
    transient Entry[] table; // key-value를 담고 있는 배열
    // ...
    static class Entry implements Map.Entry{ // Map.Entry는 Map의 내부에 선언된 인터페이스
        final Object key;
        Object value;
        // ...
    }
}

// 비 객체지향적인 코드
Object[] key;
Object[] value; // 따로 관리

// 객체지향적인 코드 
Entry[] table;
class Entry{
    Object key;
    Object value; } // 함께 관리

// 사용 예시
HashMap map = new HashMap();
map.put(“abcd”, “1234”); // map = [abcd:1234]
map.put(“aaaa”, “1234”); // map = [abcd:1234, aaaa:1234]
map.put(“aaaa”, “1111”); // map = [abcd:1234, aaaa:1111] <- 키는 중복허용X

1. Map 인터페이스를 구현한 클래스

  - Hashtable은 동기화가 되어있는 old version -> HashMap이 new version

2. 데이터를 키(key)와 값(value)의 쌍으로 저장

  - 해싱(hashing) 기법으로-> 데이터가 많아도 검색이 빠르다.

3. 순서 유지X -> 순서를 유지하려면 LinkedHashMap클래스를 사용하면 된다.

4. 키는 중복X, 값은 중복O

 

[해싱(hashing)]

왼쪽은 해시함수, 오른쪽은 데이터가 저장된 해시테이블

1. 해시함수(hash function)를 이용해서  해시테이블(hash table)의 데이터를 저장, 검색하는 것

  - 해시코드 = 저장 위치(index)

 2. 해시 테이블은 배열과 링크드 리스트가 조합된 형태

  - 배열의 접근성 + 링크드 리스트의 변경에 유리하다는 장점을 이용

3. 해시함수는 Objects.hash()로 작성

4. 해싱 과정

① 키로 해시함수를 호출해서 해시코드를 얻는다.

② 해시코드(해시함수의 반환값)에 대응하는 링크드 리스트를 배열에서 찾는다.

③ 링크드 리스트에서 키와 일치하는 데이터를 찾는다.

5. 해시함수는 언제 불러와도 결과가 같아야 하기 때문에 같은 키에 대해 항상 같은 해시코드를 반환해야 한다.

6. 서로 다른 키일지라도 같은 값의 해시코드를 반환할 수도 있다. (75년생과 72년생의 해시코드가 똑같이 7인 것처럼)

 

[생성자]

HashMap()
// 기본 생성자

HashMap(int initialCapacity)
// 초기 용량(배열의 크기) 설정

HashMap(int initialCapacity, float loadFactor)
// 초기 용량 + 용량을 늘리는 시기 설정
// loadFactor=0.8이면 80%가 찼을 때 용량 늘림
// 보통은 2배로 늘린다.

HashMap(Map m)
// m의 모든 요소를 포함하는 HashMap 생성

 

[메서드]

Object put(Object key, Object value)
// 지정된 키와 값을 저장

void putAll(Map m)
// m의 모든 요소를 저장

Object remove(Object key)
// key로 저장된 객체(value) 삭제

Object replace(Object key, Object value)
// key에 저장된 값을 value로 변경

boolean replace(Object key, Object oldVal, Object newVal)
// key와 oldVal이 모두 일치하는 객체의 값을 newVal로 변경

boolean containsKey(Object key)
// key가 포함되어 있다면 true 반환

boolean containsValue(Object value)
// value가 포함되어 있다면 true 반환

Object get(Object key)
// key의 값을 반환

Object getOrDefault(Object key, Object defaultValue)
// key의 값을 반환. key를 못 찾으면 defaultValue 반환

Set entrySet()
// HashMap에 저장된 키와 값을 엔트리(키와 값의 결합) 형태로 Set에 저장해서 반환

Set keySet()
// 모든 키를 Set에 저장해서 반환

Collection values()
// 모든 값을 컬렉션의 형태로 반환

void clear()
// 저장된 모든 객체 제거

boolean isEmpty()
// HashMap이 비어있다면 true 반환

int size()
// 저장된 요소의 개수 반환

Object clone()
// 복제

 

[코드 예시 – 시험 점수 출력]

HashMap map = new HashMap();
map.put("무지", 90);
map.put("무지", 100); // key가 중복이므로 value만 100으로 업데이트됨
map.put("춘식", 100);
map.put("튜브", 80);
map.put("콘", 90);

Set set = map.entrySet(); // Map은 iterator() 사용 불가
Iterator it = set.iterator();
while(it.hasNext()) {
    Map.Entry e = (Map.Entry)it.next();
    System.out.println("이름: "+ e.getKey() + ", 점수: " + e.getValue());
}
// 이름: 콘, 점수: 90
// 이름: 튜브, 점수: 80
// 이름: 무지, 점수: 100
// 이름: 춘식, 점수: 100

set = map.keySet();
System.out.println("명단: " + set);
// 명단: [콘, 튜브, 무지, 춘식]

Collection values = map.values();
it = values.iterator();
int total = 0;
while(it.hasNext()) {
    int i = (int)it.next(); // 원래는 Integer라고 해야하나, 오토박싱이 되기 때문에 int로 해도 상관없음
    total += i;
}

System.out.println("총점: " + total); // 총점: 370
System.out.println("평균: " + (float)total/set.size()); // 평균: 92.5
System.out.println("최고점 : " + Collections.max(values)); // 최고점 : 100
System.out.println("최저점 : " + Collections.min(values)); // 최저점 : 80

 

 [코드 예시 – 반장 선거]

// 득표수를 그래프로 그려줄 메서드
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)
}

//main()
String[] vote = { "춘식","무지","춘식","무지","튜브","무지","춘식","무지","무지","무지","라이언","튜브" };
HashMap map = new HashMap();
for(int i=0; i < vote.length; i++) {
    if(map.containsKey(vote[i])) {
        int value = (int)map.get(vote[i]);
        map.put(vote[i], value+1);  // key가 있다면 값에 1씩 더해줌
    }
    else
        map.put(vote[i], 1);	    // key가 없다면 추가해주면서 값을 1로 초기화		
}

Iterator it = map.entrySet().iterator();
while(it.hasNext()) {
    Map.Entry entry = (Map.Entry)it.next();
    int value = (int)entry.getValue();
    System.out.println(entry.getKey() + ": " + printBar('#', value) + " " + value );
}
// 춘식: ### 3
// 튜브: ## 2
// 라이언: # 1
// 무지: ###### 6

---

[쿠키글] TreeMap

- 범위 검색과 정렬에 유리한 컬렉션 클래스

- HashMap보다 데이터 추가, 삭제에 시간이 더 걸린다. (비교하면서 저장하기 때문에)

- TreeSet이 TreeMap으로 만든 것

- key-value를 이용한다는 것 빼고는 TreeSet과 같다.

- 다수의 데이터에서 개별적인 검색은 TreeMap보다 HashMap이 빠르다.