[Data Structures] HashMap

MAP을 상속받아 구현되어 Entry (Key : Value) 구조로 데이터가 저장된다. 키 값을 기준으로 검색하기 때문에 내부 데이터를 순회하며 조회하기 위한 자료 구조가 아니다.

---

HashMap 사용 고려 기준

HashMap은 주로 DAT로 활용하는데, 아래의 세 가지 경우 Array 타입 대신 HashMap을 이용해 DAT를 구성한다.

• 인덱스의 값이 정수가 아닌 경우 사용한다.
• 저장하고 싶은 값이 음수인 경우 사용한다.
• 저장할 데이터의 양이 1,000만 개를 넘기는 경우 사용한다.
    ※ int 타입 Array 기준 1억 개 공간 확보 시 380MB 소요

 

HashMap의 시간 복잡도

• Array와 동일하게 O(1)의 시간 복잡도를 가지지만 상대적으로 느리다.
• 키 값을 hashcode에 넣어 연산 후 나오는 숫자로 bucket을 선정해 데이터를 넣기 때문에 상대적으로 느리다.

 

HashMap 사용 Tip

• HashMap은 KEY 값이 Unique 하게 구성되어 있어야 한다.
• 1개의 KEY 값에 1개의 VALUE만 저장되기 때문에 같은 KEY로 데이터를 다시 넣으면 기존 데이터에 덮어쓰게 된다.
• 하나의 KEY 값에 여러 개의 값을 넣고 싶은 경우 ArrayList<> 또는 Custom Data Type을 구성해서 관리한다.
• Hasing을 통해 Unique KEY 값을 생성할 때는 문자열이 아닌 정수 값으로 바꾸는 것이 성능에 더 효율적이다.
    ※ 문자열을 이어 붙이는 연산 속도가 정수 연산 보다 느리기 때문에 최적화를 위해 정수형으로 바꾸는 것이 좋다.
• HashMap의 조회 함수(.get())는 최대한 적게 사용할 수록 좋다.
    ※ 조회 함수의 결과를 변수에 담아서 다른 곳에서 사용하는 것이 효율이 더 좋다.
• 데이터를 초기화 할 떄 신규 객체를 초기화하여 할당하는 것보다 .clear() 함수를 사용하는 것이 효율이 좋다.

 

HashMap 기본 사용 예제코드

• 변수 초기화

HashMap<String, Integer> map = new HashMap<>();

• 기본 연산

// #1. 삽입
map.put("GilDong", 1);
map.put("GilDong", 2);	// → 같은 key로 데이터를 다시 넣으면 덮어쓰기 됨

// #2. 조회
map.get("홍길동")		// → Key 값에 맵핑된 값이 없으면 null 반환

// #3. 삭제
map.remove("홍길동")	// → Key 값에 맵핑된 값이 없으면 null 반환

// #4. 사이즈
map.size()				// → Entry(데이터)의 개수 반환

// #5. 데이터 초기화
map.clear()				// map = new HashMap<>(); → 객채 초기화 보다 .clear() 함수 효율이 좋음

• KEY 중복을 피하기 위해 삽입/조회 복합 사용

// if문에서 map.get("GilDong")을 두 번 처리하는 것보다 
// 변수에 담아서 처리하는 코드가 효율이 더 좋다.
Integer id = map.get("GilDong");
if (id == null) {
	map.put("GilDong", 3);
}
else if (id != null) {
	map.put("GilDong", id + 1 );
}

 

 

ArrayList와 HashMap 복합 사용 예제 코드

• 변수 초기화

HashMap<String, ArrayList<Integer>> map = new HashMap<>();

• 데이터 삽입

// GilDong 이라는 1개의 키에 {1, 10} 값 모두 저장
if (map.get("GilDong") == null) map.put("GilDong", new ArrayList<>());
map.get("GilDong").add(1);
map.get("GilDong").add(10);

 

Custom Data Type과 HashMap 복합 사용 예제 코드

• Custom Data Type 생성

class Person {
	String address;
	int age;

	public Person (String address, int age) {
		this.name = address;
		this.age = age;
	}
}

• HashMap 변수 초기화

HashMap<String, Person > map = new HashMap<>();

• 데이터 삽입

map.put("GilDong", new Person("Chosun", 30))

 

Custom Data Type, ArrayList, HashMap 복합 사용 예제 코드

아래의 2차원 배열을 입력 받아 저장한 후 정수 값을 추가로 입력 받아 2차원 배열에서 좌표 값의 정보를 출력하는 문제를 해결 할 때 Custom Data Type과 ArrayList, HashMap을 통해 해결할 수 있다.

// 2차원 배열
15 11 -7
55 -7 11
-7 -55 -9

// 추가로 들어오는 정수 값
-7

• Custom Data Type 생성 (좌표 값 저장용)

 static class Node {
        int row;
        int col;

        public Node(int row, int col) {
            this.row = row;
            this.col = col;
        }
 }

• HashMap 변수 초기화 

// 같은 값이 중복해서 저장될 수 있기 때문에 ArrayList로 값을 관리한다.
static HashMap<Integer, ArrayList<Node>> map = new HashMap<>();

• 데이터를 받아서 저장

 for (int i=0; i<row; i++) {
     st = new StringTokenizer(br.readLine());
     for (int j=0; j<col; j++) {
         Integer key = Integer.parseInt(st.nextToken());
         // KEY 마다 이전에 저장된 데이터가 없을 경우 배열을 초기화 후 저장 한다.
         if (map.get(key) == null) map.put(key, new ArrayList<>());
         map.get(key).add(new Node(i, j));
     }
 }

• 좌표 정보 출력

int key = Integer.parseInt(st.nextToken());

for (Node idx : map.get(key)) {
     System.out.print("(" + idx.row + "," + idx.col + ")" + " ");
 }
 // 출력 결과: (0,2) (1,1) (2,0)