HashMap으로 빠른 비교 목록

해시맵 사용법을 기억하고 있기 때문에 관련 항목과 함께 정리해보려고 한다.우선 해시맵이 무엇인지 억제하고 구체적인 예를 통해 어떤 상황에서 사용할지 생각해 보자.

해시맵이란?

Map 인터페이스의 데이터 구조를 실시한다.기타도 dictionary 또는 unordered map 등으로 불리지만 자바의 표준 라이브러리에서 HashMap와 같은 종류를 사용한다.
우세하다
약점
기본적으로 빠른 검색 기능[1]
상황에 따라 소요 시간[2]key유연성
불일치 요소 저장 순서
-value를 키로 검색key한 경우 모든 요소를 순환하는 데 시간이 소요됩니다.
-
링크드 리스트를 실현했기 때문에 각 데이터는 메모리에 인접하지 않습니다[3]
https://www.interviewcake.com/concept/java/hash-map

Map

Map는 Collection 중의 하나다.스토리지에는 key 및 value 쌍의 요소가 있으며 key 를 제공하면 해당 요소를 검색할 수 있습니다 value.
여기서 주의해야 할 것은 key 아니다index.index 각 요소에 대해 저장된 순서에 따라 자동으로 번호를 분배한다.예를 들어 패턴의 경우 index를 축sort()으로 컴포넌트를 재배열할 수 있지만 Map의 경우에는 이 방법이 없습니다.자유는 때때로 자유롭지 않다!

HashMap 및 TreeMap

Java에서 일반적인 implementation ofMap는 HashMap와 TreeMap이다.두 인터페이스 모두 실현Map.
HashMap
TreeMap
저장 방법의 차이
순서가 달라요.put 순으로 스토리지
특기 분야TreeMap보다 조금 빠르다.보통 순서대로 안 써요.
보존 순서에 얽매인 경우TreeMap 선택

해시맵의 등장 시간.

두 목록 비교

두 개의 저장 문자열 목록이 있습니다:.(길이가 달라도 됨)

List<String> strings = List.of("aba", "baba", "aba", "xzxb");
List<String> queries = List.of("aba", "xzxb", "ab");

strings의 순서 검사를 통해 queries 내의 각 요소와 얼마나 일치하는지 알고 싶습니다.
상술한 예를 들어 말하자면

abastrings내 2개

xzxbstrings내 1개

ab 0에서 0개
따라서 구한 배열은

[2,1,0]

.

흔한 예: 수조에 따라 for-loop 회전

public static List<Integer> matchingStrings(List<String> strings, List<String> queries) {
	// (1) queries内の全要素を調べ、その要素の数だけ(2)countStr()を呼び出し、
	// その結果をsolに書き出す
	List<Integer> sol = new ArrayList<>();
	for (String s : queries)
		sol.add(countStr(s, strings));
	return sol;
}

// (2) strings内の全要素を調べ、sと合致した回数を返す
public static Integer countStr(String s, List<String> strings) {
	int count = 0;
	for(String x: strings)
		if(s.equals(x))
		count++;
	return count;
}

public static void main(String[] args) {
	List<String> strings = List.of("aba", "baba", "aba", "xzxb");
	List<String> queries = List.of("aba", "xzxb", "ab");
	System.out.println(matchingStrings(strings, queries));
}

HashMap 사용 예

public static List<Integer> matchingStrings2(List<String> strings, List<String> queries) {

	// (1) dicの作成
	// dic = {key: queries内の各要素, value: strings内にそのkeyがいくつあるか}
	Map<String, Integer> dic = new HashMap<>();
	for(String str: strings){ // O(n)
	    int temp = dic.getOrDefault(str, 0);
	    dic.put(str, ++temp);
	    System.out.println("dic "+ dic);
	}
	// dic = {baba=1, aba=2, xzxb=1}

	// (2) queriesの各要素をkeyとして、dicのvalueを取り出し、solに書き出す
	List<Integer> sol = new ArrayList<>();
	for (String s : queries) {
	    sol.add(dic.getOrDefault(s,0)); // O(m)
	}
	return sol;
}

public static void main(String[] args) {
	List<String> strings = List.of("aba", "baba", "aba", "xzxb");
	List<String> queries = List.of("aba", "xzxb", "ab");
	System.out.println(matchingStrings2(strings, queries));
}

비교

strings의 요소수를 m로 설정하고queties의 요소수를 n으로 설정하여 이 두 가지 방법의 차이를 조사하여 해시맵을 사용하는 것이 더 빠르다.Big O-notation으로

흔한 예는 O(m*n)

HashMap 사용의 예는 O(m+n)

흔한 예: 수조에 따라 for-loop 회전의 기본 방침은 조사strings 내의 모든 요소를 이 요소의 수량queries만 호출하고 그 결과를 countStr()에 기록하는 것이다.이 중 매번 호출sol할 때마다 countStr()의 모든 요소를 검사해야 한다.즉 O(m*n).
반면HashMap 사용 예

strings를 한 바퀴 돌면서 각 문자열이 몇 번 나왔는지 알 수 있는 해시맵strings을 만든다.

를 비교한 다음dic와 dic를 비교하여 결과를 배열한다.

두 단계로 나누다.즉, 각 순환은 독립적이기 때문에 O(m+n)
따라서 요소수가 많을수록 이 두 가지 방법의 처리 효율의 차이는 지수적으로 커진다.
각주
표준 상황에서 O(1)↩︎
최악의 경우 O(n)↩︎
Aray는 메모리에 데이터가 인접해 있기 때문에 비교로 이런 차이가 나타날 것이라고 생각한다.무슨 뜻인지 알겠지만 왜 약점으로 계산했는지 이해가 안 돼서 이해가 되면 기사를 업데이트한다.↩︎