해시란?
key : value의 값을 가지는 하나의 자료구조
예) 전화번호부 ⇒ 검색창에 이름을 입력하면 전화번호 결과가 나옴
무언가를 찾기 위한 검색어 (이름) = key
그 검색어로 나온 결과 (전화번호) = value
해시가 왜 필요한가?
배열로는 오직 정수로만 접근이 가능함
int[] phonebook = new int[5];
phonebook[0];친구의 이름을 알더라도 이름을 기반으로 전화번호를 찾을 수 없음
String name = "hyunwoo";
phonebook[name] // error그렇기 때문에 해시가 없던 시절 유일하게 할 수 있었던 방법은 0부터 끝까지 하나하나 열어보며 찾는 친구가 맞는지 확인하는 방법뿐이었음
for (int i = 0; i < n; i++) {
// phonebookName[i] == name?
}해시는 배열과 달리 String 타입이나 다른 어떤 데이터형을 기반으로 자료구조를 접근하고 데이터를 관리할 수 있도록 해줌
⚠️ **코딩테스트에서 중요한 점**해시는 모든 데이터 타입으로 접근이 가능함
get / put / getOrDefault 함수 꼭 기억할 것
- getOrDefault함수!
public String solution(String[] participant, String[] completion) { String answer = ""; HashMap<String,Integer> hm = new HashMap<>(); for(String player : participant){ hm.put(player,hm.getOrDefault(player,0)+1); } //for(int i=0;i<completion.length;i++){ //if(!hm.containsKey(completion[i])){ //hm.put(completion[i],1); //}else{ //hm.replace(completion[i],hm.get(completion[i])+1); //} //} for(int j=0;j<participant.length;j++){ if(!hm.containsKey(participant[j]) || hm.get(participant[j]) == 0){ answer = participant[j]; }else{ hm.replace(participant[j],hm.get(participant[j])-1); } } return answer; }- 위의 코드에서 주석된 부분처럼 키가 있는지 확인하고 없으면 초기값으로 넣고 있으면 1 더하는 코드를 한 줄로 간단하게 작성할 수 있다.
어떤 문제에서 해시를 써야할까?
➡️ **String을 기반으로 정보를 기록하고 관리해야 될 때**String을 기준으로 정보를 기록하고 관리하려면 단순 배열을 쓸 수 없으니 Hash를 활용하자
Hash 관련 코드
- [기본]
// 선언 HashMap<타입 ,타입> hm = new HashMap<>(); // 카피 - 타입이 모두 같아야 함. HashMap<타입, 타입> hm2 = new HashMap<>(hm); // 크기 지정 HashMap<타입, 타입> hm3 = new HashMap<>(크기);package codingtest; import java.awt.print.Printable; import java.util.*; import java.util.Scanner; import org.omg.CORBA.PolicyListHelper; public class Main { public static void main(String[] args) { Map<String, Integer> hm = new HashMap<>(); // 데이터 추가 hm.put("data1", 1); hm.put("data2", 2); hm.put("data3", 3); hm.put("data4", 4); hm.put("data5", 3); hm.put("data6", 6); // 데이터 삭제 - key hm.remove("data1"); // 데이터 삭제 - values // (**동일한 값이 존재하는 경우 가장 늦게 들어온 오직 한 개의 요소만 삭제**) // hm.values().remove(3); // 결과 : {data6=6, data4=4, data3=3, data2=2} // 데이터 삭제 - values - 한 번에 여러 요소 삭제 // value가 2,3인 모든 데이터를 삭제한다. // hm.values().removeAll(Arrays.asList(2,3)); // 크기 hm.size(); // 모든 내용 삭제 // hm.clear(); // 데이터 변경 hm.replace("data2", 10); hm.replace("data6", 6, 12); // 키의 값이 일치해야 값 변경 가능 // 데이터 추출 hm.get("data2"); // 키로 값 추출 // 키 존재 유무 확인 true|false hm.containsKey("data6"); // 키 기준 hm.containsValue(12); // 값 기준 } } - [정렬]
public class Main { public static void main(String[] args) { Map<String, Integer> hm = new HashMap<>(); Map<String, String> map = new HashMap<>(); map.put("Nepal", "Kathmandu"); map.put("United States", "Washington"); map.put("India", "New Delhi"); map.put("England", "London"); map.put("Australia", "Canberra"); List<String> valueList = new ArrayList<>(map.values()); valueList.sort(String::compareTo); // 알파벳 순으로 정렬 for (String value : valueList) { System.out.println("Value: " + value); } } } /* Value: Canberra Value: Kathmandu Value: London Value: New Delhi Value: Washington */public class Main { public static void main(String[] args) { Map<String, Integer> hm = new HashMap<>(); hm.put("data1", 5); hm.put("data2", 6); hm.put("data3", 4); hm.put("data4", 4); hm.put("data5", 7); hm.put("data6", 1); List<Integer> valueList = new ArrayList<>(hm.values()); valueList.sort(Integer::compareTo); for (int value : valueList) { System.out.println("Value: " + value); } } } /* Value: 1 Value: 4 Value: 4 Value: 5 Value: 6 Value: 7 */ - HashSet
package codingtest; import java.awt.print.Printable; import java.util.*; import java.util.Scanner; import org.omg.CORBA.PolicyListHelper; public class Main { public static void main(String[] args) { // HashSet 선언 HashSet<Integer> setTest = new HashSet<>(); // 데이터 삽입 setTest.add(10); setTest.add(20); setTest.add(30); setTest.add(40); setTest.add(50); // 중복을 허용하지 않음 setTest.add(10); setTest.add(20); setTest.add(30); System.out.println(setTest); // [50, 20, 40, 10, 30] // remove Element setTest.remove(40); // Element 존재 확인 System.out.println(setTest.contains(10)); // true // isEmpty() System.out.println(setTest.isEmpty()); // false // size() System.out.println(setTest.size()); // 4 // get iterator() Iterator setIter = setTest.iterator(); while (setIter.hasNext()) { System.out.println(setIter.next()); } // Removes all of the elements from this set. setTest.clear(); } }
dkssud!