Map 인터페이스

해시 테이블은 지금까지 발명된 자료구조 중 단연 으뜸입니다. 

TreeMap 클래스와 비슷한 다른 하나는 마법까지는 아니지만, 

요소를 순서대로 반복할 수 있는 추가 기능을 제공합니다. 

 

public class MyLinearMap<K, V> implements Map<K, V> {

   private List<Entry> entries = new ArrayList<Entry>();

Entry 객체는 키-값 쌍을 포함합니다. 

Entry 클래스는 단지 키와 값의 컨테이너입니다. 이 정의는 MyLiearMap 클래스에 중첩되어 있으므로 같은 타입 파라미터인 K와 V를 사용합니다. 

equals 메서드의 실행시간은 target과 키의 크기에 의존하지만, 엔트리 개수에 해당하는 n에는 의존하지 않습니다. 따라서 equals는 상수 시간입니다.

findEntry 메서드에서는 운이 좋으면 처음에 원하는 키를 찾을 수도 있습니다. 하지만 항상 그럴 리는 없습니다. 일반적으로 검색해야 할 엔트리 개수는 n에 비례합니다. 따라서 findEntry 메서드는 선형입니다.