HashMap

2019/03/20 - [프로그래밍 노트/JAVA] - [JAVA] 동기화된 컬렉션(thread-safe collection), 병렬처리 가능한 컬렉션 Hashtable 클래스는 동기화할 수 있으며 병렬처리에 효율적이다. 하지만 오버헤드 때문에 성능이 상당히 저하된다. HashMap은 오버헤드의 문제는 없지만, 동기화할 수 없다는 특징이 있다. 따라서 동시성 요구든 용도에 맞게 map 클래스를 사용해야 한다. 병렬 환경에서의 Map 인터페이스를 사용하는 곳에는 ConcurrentHashMap(자바5이상)를 사용하는 것이 좋다.
Map 인터페이스 구현 MyHashMaphashing을 이용한 MyBetterMap은 여전히 성장차수는 선형이었다. (MyBetterMap 포스팅) n개의 엔트리와 k개의 하위 맵이 있다면 하위 맵의 크기는 평균 n/k가 되고, 여전히 n에 비례하게 된다.하지만, n과 함께 k를 늘려간다면 n/k의 크기를 제한할 수 있다. 하위 맵당 엔트리의 개수가 일정하면 단일 하위 맵은 상수시간으로 검색이 가능(해시 함수를 계산하는 것 => 상수시간)MyHashMap 클래스는 MyBetterMap 클래스를 확장하므로 MyBetterMap에 정의된 메서드를 상속한다. 123456789101112131415161718192021222324252627282930public class MyHashMap extends MyB..
Map 인터페이스 구현 (MyBetterMap)MyLinearMap클래스보다 Map 인터페이스를 더 잘 구현한 MyBetterMap 정의 MyBetterMap을 좀 더 효율적으로 만든 해싱(hashing)을 소개 해싱(hashing)MyLinearMap 클래스의 성능 향상을 위해 MyLinearMap 객체의 컬렉션을 포함하는 MyBetterMap이라는 새로운 클래스를 정의내장된 맵에 따라 키를 나누므로 각 맵의 엔트리 개수는 더 줄어들고, 이 것은 findEntry 메서드와 그 것을 호출하는 메서드의 속도를 빠르게 함.123456789101112131415161718public class MyBetterMap implements Map { protected List maps; MyBetterMap(int..
Map 인터페이스의 구현 (MyLinearMap) Map 인터페이스의 여러 구현 중 하나는 해시 테이블(hash table)에 기반을 두는데 지금까지 발명된 자료구조 중 단연 으뜸이다. 해시 테이블을 설명하기에 앞서 키-값 쌍으로 이루어진 리스트를 사용하여 간단한 Map 인터페이스를 구현해 본다. MyLinearMap 객체에는 단일 인스턴스 변수 entries가 있는데 Entry객체들을 담은 ArrayList이다. (Entry 클래스는 MyLinearMap의 inner class) public class MyLinearMap implements Map { // MyLinearMap 기본 구현 private List entries = new ArrayList(); public class Entry impl..
Map의 Value데이터 기준으로 정렬하기 TreeSet을 이용하면 Key 기준으로 쉽게 정렬할 수 있으나, Value로 정렬해주는 컬렉션은 존재하지 않는다. Value로 map을 정렬을 하려면 Comparator 인터페이스를 이용해야 한다. 밑에 예제는 Value를 기준으로 내림차순으로 정렬을 하고, Value가 같다면 Key를 기준으로 오름차순으로 정렬하는 예제이다. package sort; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.LinkedList; im..
Map 구현체 HashMapHashtable과 HashMap은 Vector와 ArrayList와 같은 관계이다. (새로운 버전인 HashMap을 사용할 것을 권장하고 있다.)Map의 특징, 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖고있다.그리고 해싱(hashing)을 사용하기 때문에 데이터검색에 뛰어난 성능을 보인다. 12345678public class HashMap extends AbstractMap implements Map, Cloneable, Serializable{ transient Entry[] table; static class Entry implements Map.Entry{ final Object key; Object value; }}Col..
깡냉쓰
'HashMap' 태그의 글 목록