반응형
Map 인터페이스
public interface Map<K,V> {
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
}
HashMap 클래스
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
Map 인터페이스를 가지고 만들고 싶은 클래스에 implements Map을 통해 다양한 Map 클래스를 만들 수 있다.
MyLinearMap이라는 클래스를 만든다.
public class MyLinearMap<K, V> implements Map<K, V> {
private List<Entry> entries = new ArrayList<Entry>();
public class Entry implements Map.Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V newValue) {
value = newValue;
return value;
}
}
@Override
public void clear() {
entries.clear();
}
@Override
public boolean containsKey(Object target) {
return findEntry(target) != null;
}
@Override
public boolean containsValue(Object target) {
for (Map.Entry<K, V> entry: entries) {
if (equals(target, entry.getValue())) {
return true;
}
}
return false;
}
@Override
public Set<Map.Entry<K, V>> entrySet() {
throw new UnsupportedOperationException();
}
@Override
public V get(Object key) {
// TODO: FILL THIS IN!
Entry entry = findEntry(key);
if(entry == null) {
return null;
}else {
return entry.getValue();
}
}
@Override
public boolean isEmpty() {
return entries.isEmpty();
}
@Override
public Set<K> keySet() {
Set<K> set = new HashSet<K>();
for (Entry entry: entries) {
set.add(entry.getKey());
}
return set;
}
@Override
public V put(K key, V value) {
// TODO: FILL THIS IN!
Entry entry = findEntry(key);
if(entry == null) {
entries.add(new Entry(key, value));
return null;
}else{
V oldValue = entry.getValue();
entry.setValue(value);
return oldValue;
}
}
@Override
public void putAll(Map<? extends K, ? extends V> map) {
for (Map.Entry<? extends K, ? extends V> entry: map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override
public V remove(Object key) {
// TODO: FILL THIS IN!
Entry entry = findEntry(key);
if(entry == null) {
return null;
}else {
V oldValue = entry.getValue();
entries.remove(entry);
return oldValue;
}
}
@Override
public int size() {
return entries.size();
}
@Override
public Collection<V> values() {
Set<V> set = new HashSet<V>();
for (Entry entry: entries) {
set.add(entry.getValue());
}
return set;
}
/**
* Returns the entry that contains the target key, or null if there is none.
*
* @param target
*/
private Entry findEntry(Object target) {
// TODO: FILL THIS IN!
for(Entry entry: entries) {
if(equals(target, entry.getKey())) {
return entry;
}
}
return null;
}
/**
* Compares two keys or two values, handling null correctly.
*
* @param target
* @param obj
* @return
*/
private boolean equals(Object target, Object obj) {
if (target == null) {
return obj == null;
}
return target.equals(obj);
}
/**
* Returns a reference to `entries`.
*
* This is not part of the Map interface; it is here to provide the functionality
* of `entrySet` in a way that is substantially simpler than the "right" way.
*
* @return
*/
protected Collection<? extends java.util.Map.Entry<K, V>> getEntries() {
return entries;
}
중요한것은 Map.Entry의 key와 value를 통해 Entry클래스를 사용하여 키,밸류로 저장하고 변경하고 지우고 값을 찾는 자료구조형이다.
메서드중에 채워넣어야할 것을(// TODO: FILL THIS IN!) 구현하여 MyLinearMap를 구현한다.
private 내부함수를 추가하고 내부함수를 호출하여 처리할 수 있다.
그리고 핵심 메서드의 성능을 분석하고 상수시간, 선형 계산 등 고려하여 알맞게 구현한다.
결론:
여기에서 만든 MyLinearMap 클래스의 핵심 메서드는 모두 실행시간이 선형이다.
엔트리 개수가 작다면 이 구현은 쓸만하다.
하지만, 핵심 메서드가 상수시간인 Map의 구현도 있다.
개선 방법:
1. 엔트리를 하나의 커다란 List에 저장하는 대신 다수의 작은 리스트로 쪼갠다.
각 키에 대해 해시 코드를 사용하여 어느 리스트를 사용할지 선택
2. 하나의 큰 리스트 대신 다수의 작은 리스트를 사용하는 것이 더 빠르지만, 증가 차수를 개선하지 못한다. 핵심 연산은 여전히 선형이다.
하지만 다른 묘수가 있다. 리스트의 개수를 늘려서 리스트당 엔트리 개수를 제한할 수 있다면 결과는 상수 시간 맵이 된다.
- 출처: Think Data Structures (자바로 배우는 핵심자료구조와 알고리즘) 저자: 앨런B.다우니 지음, 유동환 옮김-
반응형
'Algorithm & problem solving' 카테고리의 다른 글
| MyLinearMap와 해싱 (0) | 2018.08.17 |
|---|---|
| 연결리스트 알고리즘 (0) | 2018.07.03 |
| 선택정렬 알고리즘 (0) | 2018.07.03 |
| 컴퓨터 알고리즘 (0) | 2018.05.18 |