해싱

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(int k) {
      makeMaps(k);
   }

   /**
    * 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>());
      }
   }

이 실습의 요점은 Map 인터페이스를 효율적으로 구현하는 것입니다.

더 나은 접근법은 해시 함수을 사용하는 것입니다. 이 함수는 Object 객체를 인자로 받아 해시 코드라는 정수를 반환합니다. 중요한 점은 같은 Object 객체에 대해서는 항상 같은 해시 코드를 반환해야 합니다. 이러한 방식으로 해시 코드를 사용하여 키를 저장하면 키를 조회할 때 항상 같은 해시 코드를 얻게 됩니다. 

 

자바에서 모든 Object 객체는 hashCode라는 메서드를 제공하여 해시 함수를 계산합니다. 이 메서드의 구현은 객체의 종류에 따라 달라집니다. 

하위 맵을 고르는 헬퍼 메서드

index는 항상 maps의 유효한 인덱스가 되고 chooseMap 메서드는 서낵한 맵의 참조를 반환합니다.

@Override
public V get(Object key) {
   MyLinearMap<K, V> map = chooseMap(key);
   return map.get(key);
}

@Override
public V put(K key, V value) {
   MyLinearMap<K, V> map = chooseMap(key);
   return map.put(key, value);
}

 

해싱의 동작 방식

해시 함수의 근본적인 요구사항은 같은 객체는 매번 같은 해시 코드를 만들어야 한다는 것입니다. 불변 객체일 때는 상대적으로 쉽지만, 가변 객체일 때는 좀 더 고민해봐야 합니다.

/**
 *
 */
package com.allendowney.thinkdast;

import java.util.Map;

/**
 * @author downey
 *
 */
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));
      }
   }
}

많을 객체가 동일한 해시 코드를 갖는다면 결국 같은 하위 맵으로 몰리게 됩니다. 어떤 하위 맵에 다른 맵보다 많은 엔트리가 있으면 k개의 하위 맵으로 인한 성능 향상은 k보다 줄어들게 됩니다. 그래서 해시 함수의 목표 중 하나는 균등해야 한다는 것입니다. 즉 일정 범위에 있는 어떤 값으로 고루 퍼지도록 해시 코드를 생성해야 합니다.

 

String 클래스는 불변이며 innerString 변수가 final로 선언되었기 때문에 SillyString 클래스 또한 불변입니다. 일단 SillyString 객체를 생성하면 innerString 변수는 다른 String 객체를 참조할 수 없고 이 변수가 참조하는 String 객체 또한 변경할 수 없습니다. 따라서 항상 같은 해시 코드를 갖게 됩니다. 

 

가변 객체에서는 어떤일이 일어나는지 알아보겠습니다. 

 

/**
 * 
 */
package com.allendowney.thinkdast;

import java.util.Arrays;
import java.util.Map;

/**
 * @author downey
 *
 */
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));
      }
   }
}

 일반적으로 MyBetterMap과 HashMap을 포함하여 해싱을 사용하는 자료구조에서 가변 객체를 키로 사용하는 것은 위험합니다. 키가 맵에 있는 동안 변형되지 않는다고 보장할 수 있거나 어떤 변화가 해시 코드에 영향을 미치지 않으면 괜찮습니다. 하지만 그렇다고 하더라도 이러한 경우는 피하는 것이 좋습니다.