[JAVA] Hashmap, Iterator

https://programmers.co.kr/learn/courses/30/lessons/42577?language=java 

코딩테스트 연습 - 전화번호 목록

 

java 의 자료구조가 아직 익숙하지 않아서 기초 알고리즘 문제부터 풀어보려고 한다. Hash Table 이라는 key-value 쌍으로 이루어진 자료구조를 이용한 hash 카테고리의 문제를 풀어보려 했다. 처음부터 막혀서 아직은 문제를 풀기보다는 메소드, 자료구조를 익히는 정도로 공부해야겠다는 생각이 들었다. 

[Hash Table]

(Key, Value) 쌍으로 데이터를 저장하는 자료구조. 데이터를 빠르게 검색할 수 있는 자료구조. 해시 테이블이 빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하는 이유 때문이다. 해시 테이블은 각 Key 값에 Hash 함수를 적용하여 배열의 고유한 index를 생성, 이렇게 생성한 index를 활용해 값을 저장하고 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 

index 계산 법

H("Key") % 16 을 index 값으로 계산하여 array[index] = "value" 로 값을 저장한다. Key 값으로 데이터를 찾을 때 해시함수 1번만 수행하여 값을 찾으므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시 테이블의 평균 시간복잡도는 O(1)이다. 

[Hash Map]

Hash Table 과 비슷하지만 다른 자료구조. 해시테이블과 달리 synchronized 가 안되어 병렬 프로그래밍할 때 동기화를 지원하지 않음. 이는 함수를 처리하는 시간이 조금 지연되는 것을 의미함. 병렬 처리를 하면서 자원의 동기화를 고려하는 상황이라면 해시테이블을 사용해야 하고, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵을 사용해야 한다.

 

해시 알고리즘 문제를 풀 때 iterator 사용법을 꼭 알아야할 것 같아서 정리해보고자 한다.

public static void main(String[] args) {


    String[] phone = { "119", "97674223", "1195524421", "1" };


    Map map = new HashMap();

    int i = 0;
    for(String p: phone) {
        map.put(p, i++);

    }

    Iterator<String> keys = map.keySet().iterator();
    
    while( keys.hasNext() ){
        String key = keys.next();
        System.out.println( String.format("키 : %s, 값 : %d", key, map.get(key)) );
    }

}

으로 HashMap 을 출력해보면

키 : 97674223, 값 : 1
키 : 1, 값 : 3
키 : 1195524421, 값 : 2
키 : 119, 값 : 0

와 같이 넣은 순서대로 값이 삽입되지 않는다. 위에서 말했듯이 키의 해시값을 인덱스로 사용하여 값을 저장하기 때문이다. 넣은 순서를 보장받고 싶다면 LinkedHashMap 을 사용하면 된다. 

문제로 돌아가서 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는 지 확인하려면 전화번호를 substring 으로 잘라서 substring이 hashmap에 존재하는 지 확인하면 그대로 검색을 멈추고 false 를 return 하면 된다. 

여기서 ContainsKey 메소드를 이용하면 쉽게 찾을 수 있다. 

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map map = new HashMap();
        
        for(String p: phone_book) {
            map.put(p, 0);
        }
        
        Iterator<String> keys = map.keySet().iterator();
        
        while( keys.hasNext() ){
            String key = keys.next();
            for(int j = 1; j < key.length(); j++) {
                String tmp = key.substring(0, j);
                if (map.containsKey(tmp)) {
                    return false;
                }
            }
        }
        
        return answer;
    }
}

 

map.keySet() : map의 key 값들을 담은 배열을 출력

map.keySet().iterator() : 각 키의 iterator

keys.hasNext() : 다음 값이 있으면 true 출력

keys.next() :  다음 값을 출력

 

System.out.println(map.keySet().iterator().hasNext());
System.out.println(map.keySet().iterator().next());

true
97674223

 

위에서 hashmap 전체 출력한 것 보면 제일 첫번째 값이 출력되는 것을 알 수 있다.