반응형
MyLinearMap 클래스의 성능을 향상을 위해 MyLinearMap 객체의 컬렉션을 포함하는 MyBetterMap이라는 새로운 클래스를 만든다.
내장된 맵에 따라 키를 나누므로 각 맵의 엔트리 개수는 더 줄어든다.
finidEntry 메스드와 그것을 호출하는 메서드의 속도를 빠르게 한다.
public class MyBetterMap<K, V> implements Map<K, V> {
// MyBetterMap uses a collection of MyLinearMap
protected List<MyLinearMap<K, V>> maps;
/**
* Initialize the map with 2 sub-maps.
*
*/
public MyBetterMap() {
makeMaps(2);
}
/**
* Makes a collection of `k` MyLinearMap
*
* @param k
*/
protected void makeMaps(int k) {
maps = new ArrayList<MyLinearMap<K, V>>(k);
for (int i=0; i<k; i++) {
maps.add(new MyLinearMap<K, V>());
}
}
인스턴스 변수maps는 MyLinearMap 객체의 컬렉션이다.
생성자 K를 인자로 받아 얼마나 많은 맵을 사용할지 정의한다.
makeMaps 메서드는 내장된 맵을 생성하고 생성된 맵을 ArrayList에 저장한다.
새로운 키를 추가하면 맵 중 하나를 고르고, 같은 키가 있다면 그 키를 어느 맵에 넣엇는지 기억해야 한다.
한가지 방법은 하위 맵을 무작위로 결정하고 각 키를 어느 맵에 넣었는지 추적하는것이다.
Map 객체로 키를 조회하여 그에 맞는 하위 맵을 찾을 수 있을거 같지만, Map 인터페이스를 효율적으로 구현하여
해시 함수를 사용하는 것이다.
Object 객체를 인자로 받아 해시 코드라는 정수를 반환한다.
Obejct객체에 대해서는 항상 같은 해시 코드를 반환해야 한다.
이러한 방식으로 해시 코드를 사용하여 키를 저장하면 키를 조회할 때 항상 같은 해시코드를 얻게된다.
자바에서는 hashCode 메서드를 제공하여 해시 함수를 계산한다.
protected MyLinearMap<K, V> chooseMap(Object key) {
int index = key==null ? 0 : Math.abs(key.hashCode()) % maps.size();
return maps.get(index);
}
key가 null이면 임의로 인덱스 0인 하위 맵을 선택한다.
null이 아니라면 hashCode 메서드를 호출하여 정수를 얻고 Math.abs 메서드를 호출하여 절대값을 만든다.
그다음 나머지 연산자인 %를 사용하여 결과가 0에서 map.size()-1에 있을 보장한다.
따라서 index는 항상 유효한 인덱스가 되고 chooseMap 메서드는 선택한 맵의 참조를 반환한다.
put과 get 메서드에서 모두 chooseMap 메서드를 호출한다.
그래서 키를 추가했을 때 선택한 것과 동일한 맵을 키를 조회할 때 얻는다.
@Override
public V put(K key, V value) {
MyLinearMap<K, V> map = chooseMap(key);
return map.put(key, value);
}
@Override
public V get(Object key) {
MyLinearMap<K, V> map = chooseMap(key);
return map.get(key);
}
n개의 엔트리를 K개의 하위맵으로 나누면 맵당 엔트리는 평균 n/K개가 된다.
키를 조회할 때 해시코드를 계산해야하는데, 이때 시간이 걸린다.
그 다음 키에 맞는 하위 맵을 검색한다.
MyBetterMap에 있는 엔트리 목록은 MyLinearMap에 있는 엔트리 목록보다 K배 빠르므로 검색도 K배 빠를 것이라고 기대할 수 있다.
하지만 실행시간은 여전히 n에 비례하므로 MyBetterMap 클래스는 선형이다.
해싱의 동작
해시함수의 근본적인 요구사항은 같은 객체는 매번 같은 해시 코드를 만들어야한다.
불변객체 immutable Object일때 상대적으로 쉽지만, 가변객체 mutable Object일때는 좀 더 고민해야한다.
- 불변객체
public class SillyString {
private final String innerString;
public SillyString(String innerString) {
this.innerString = innerString;
}
public String toString() {
return innerString;
}
@Override
public boolean equals(Object other) {
return this.toString().equals(other.toString());
}
@Override
public int hashCode() {
int total = 0;
for (int i=0; i<innerString.length(); i++) {
total += innerString.charAt(i);
}
System.out.println(total);
return total;
}
/**
* @param args
*/
public static void main(String[] args) {
Map<SillyString, Integer> map = new MyBetterMap<SillyString, Integer>();
map.put(new SillyString("Word1"), 1);
map.put(new SillyString("Word2"), 2);
Integer value = map.get(new SillyString("Word1"));
System.out.println(value);
for (SillyString key: map.keySet()) {
System.out.println(key + ", " + map.get(key));
}
}
}
SillyString 클래스는 equals와 hashCode 메서드를 오버라이드 한다.
equals와 hashCode 메서드와 일치해야한다.
두 객체가 같다면, equals 메서드가 true를 반환하면 두 객체의 해시 코드 또한 같아야한다.
하지만 이 요구사항은 단방향이다.
두 객체의 해시코드가 같더라도 같은 객체일 필요는 없다.
equlas 메서드는 innerString를 반환하는 toString 메서드를 호출하여 동작한다.
따라서 두 객체의 innerString 인스턴스 변수가 같다면 SillyString 객체도 같다.
hashCode 메서드는 String에 있는 문자(character)에 반복문을 실행하고 문자를 모두 더한다.
어떤 문자를 int(정수형)에 더하면 자바는 유니코드의 코드 포인트(code point)를 사용하여 문자를 정수로 변환한다.
이 해시 함수는 요구사항을 만족한다.
두 SillyString 객체의 내장 문자열이 동일하다면 두 객체는 같은 해시 코드를 얻게 된다.
이 해시 함수는 정확하게 동작한다. 하지만 좋은 성능은 보장하지 않는다.
이는 많은 서로 다른 문자열을 위해 같은 해시 코드를 반환하기 때문이다.
두 문자열에 같은 문자가 순서만 다르게 포함되어 있다면 이들은 해시 코드가 같다.
심지어 같은 글자가 아니더라도 ab와 bb는 합계가 같다.
많은 객체가 동일한 해시 코드를 갖는다면 결국은 하위 맵으로 몰리게 된다.
어떤 하위 맵에 다른 맵보다 많은 엔트리가 있으면 K개의 하위 맵으로 인한 성능향상은 k보다 줄어들게 된다.
그래서 해시 함수의 목표중 하나는 균등하게 uniform 한다는 것이다.
즉, 일정범위에 있는 어떤 값으로 고루 퍼지도록 해시 코드를 생성해야한다
해싱과 변형
String 클래스는 불변이며 innerString 변수가 final로 선언되었기 때ㅣ문에 SillyString 클래스 또한 불변이다.
일단 SillyString 객체를 생성하면 innerString 변수는 다른 String 객체를 참조할 수 없고 이 변수가 참조하는 String 객체 또한 변경할 수 없다.
따라서 항상 같은 해시 코드를 갖게된다.
가변 객체에서는 어떤일이 일어나는지 확인해보자.
SillyArray 클래스로 인스턴스 변수를 String이 아닌 문자 배열을 사용한다.
public class SillyArray {
private final char[] array;
public SillyArray(char[] array) {
this.array = array;
}
public String toString() {
return Arrays.toString(array);
}
public void setChar(int i, char c) {
this.array[i] = c;
}
@Override
public boolean equals(Object other) {
return this.toString().equals(other.toString());
}
@Override
public int hashCode() {
int total = 0;
for (int i=0; i<array.length; i++) {
total += array[i];
}
System.out.println(total);
return total;
}
/**
* @param args
*/
public static void main(String[] args) {
Map<SillyArray, Integer> map = new MyBetterMap<SillyArray, Integer>();
SillyArray array1 = new SillyArray("Word1".toCharArray());
map.put(array1, 1);
//
// // what happens if we mutate a key while it's in the Map?
array1.setChar(0, 'C');
//
Integer value = map.get(array1);
System.out.println(value);
//
for (SillyArray key: map.keySet()) {
System.out.println(key + ", " + map.get(key));
}
}
}
SillyArray 클래스 또한 setChar 메서드를 제공하여 배열에 있는 문자를 변경할 수 있다.
public void setChar(int i, char c) {
this.array[i] = c;
}
SillyArray 객체를 생성하고 맵에 추가한다.
SillyArray array1 = new SillyArray("Word1".toCharArray());
map.put(array1, 1);
해시코드는 461이다.
배열의 내용을 변경한다.
array1.setChar(0, 'C');
Integer value = map.get(array1);
변경후 해시 코드는 441이다.
해시 코드가 달라서 잘못된 하위 맵을 조회할 수 있다.
이런 상황에서는 키가 맵에 있어도 찾을 수 없다.
일반적으로 MyBeeterMap과 HashMap을 포함하여 해싱을 사용하는 자료구조에서 가변 객체를 키로 사용하는 것은 위험하다.
키가 맵에 있는 동안 변형되지 않는다는 보장할 수 있거나 어떤 변화가 해시 코드에 미치지 않으면 괜찮다.
하지만 그렇다고 하더라도 이러한 경우는 피하는 것이 좋다.
테스트
public class MyLinearMapTest {
protected Map<String, Integer> map;
/**
* @throws java.lang.Exception
*/
@Before
public void setUp() throws Exception {
map = new MyLinearMap<String, Integer>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
map.put(null, 0);
}
/**
* Test method for {@link MyLinearMap#clear()}.
*/
@Test
public void testClear() {
map.clear();
assertThat(map.size(), is(0));
}
/**
* Test method for {@link MyLinearMap#containsKey(java.lang.Object)}.
*/
@Test
public void testContainsKey() {
assertThat(map.containsKey("Three"), is(true));
assertThat(map.containsKey(null), is(true));
assertThat(map.containsKey("Four"), is(false));
}
/**
* Test method for {@link MyLinearMap#containsValue(java.lang.Object)}.
*/
@Test
public void testContainsValue() {
assertThat(map.containsValue(3), is(true));
assertThat(map.containsValue(0), is(true));
assertThat(map.containsValue(4), is(false));
}
/**
* Test method for {@link MyLinearMap#get(java.lang.Object)}.
*/
@Test
public void testGet() {
assertThat(map.get("Three"), is(3));
assertThat(map.get(null), is(0));
assertThat(map.get("Four"), nullValue());
}
/**
* Test method for {@link MyLinearMap#isEmpty()}.
*/
@Test
public void testIsEmpty() {
assertThat(map.isEmpty(), is(false));
map.clear();
assertThat(map.isEmpty(), is(true));
}
/**
* Test method for {@link MyLinearMap#keySet()}.
*/
@Test
public void testKeySet() {
Set<String> keySet = map.keySet();
assertThat(keySet.size(), is(4));
assertThat(keySet.contains("Three"), is(true));
assertThat(keySet.contains(null), is(true));
assertThat(keySet.contains("Four"), is(false));
}
/**
* Test method for {@link MyLinearMap#put(java.lang.Object, java.lang.Object)}.
*/
@Test
public void testPut() {
map.put("One", 11);
assertThat(map.size(), is(4));
assertThat(map.get("One"), is(11));
map.put("Five", 5);
assertThat(map.size(), is(5));
assertThat(map.get("Five"), is(5));
}
/**
* Test method for {@link MyLinearMap#putAll(java.util.Map)}.
*/
@Test
public void testPutAll() {
Map<String, Integer> m = new HashMap<String, Integer>();
m.put("Six", 6);
m.put("Seven", 7);
m.put("Eight", 8);
map.putAll(m);
assertThat(map.size(), is(7));
}
/**
* Test method for {@link MyLinearMap#remove(java.lang.Object)}.
*/
@Test
public void testRemove() {
map.remove("One");
assertThat(map.size(), is(3));
assertThat(map.get("One"), nullValue());
}
/**
* Test method for {@link MyLinearMap#size()}.
*/
@Test
public void testSize() {
assertThat(map.size(), is(4));
}
/**
* Test method for {@link MyLinearMap#values()}.
*/
@Test
public void testValues() {
Collection<Integer> keySet = map.values();
assertThat(keySet.size(), is(4));
assertThat(keySet.contains(3), is(true));
assertThat(keySet.contains(0), is(true));
assertThat(keySet.contains(4), is(false));
}
}
public class MyBetterMapTest extends MyLinearMapTest {
/**
* @throws java.lang.Exception
*/
@Before
public void setUp() throws Exception {
map = new MyBetterMap<String, Integer>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
map.put(null, 0);
}
}
기존 MyLinearMapTest에서 테스트 전 @Before를 통해
MyBetterMap으로 생성하여 기존 테스트로 진행하면된다.
- 출처: Think Data Structures (자바로 배우는 핵심자료구조와 알고리즘) 저자: 앨런B.다우니 지음, 유동환 옮김-
반응형
'Algorithm & problem solving' 카테고리의 다른 글
| Map 인터페이스와 MyLinearMap 구현 (0) | 2018.08.13 |
|---|---|
| 연결리스트 알고리즘 (0) | 2018.07.03 |
| 선택정렬 알고리즘 (0) | 2018.07.03 |
| 컴퓨터 알고리즘 (0) | 2018.05.18 |