해시 (HashMap/HashSet)

저장과 검색 등에서 자주 활용되는 자료구조

Hash: 입력데이터를 고정된 길이의 데이터로 변환된 값

Ex) Key(1232434) ⇒ 해시 함수 ⇒ 해시값(nnn)

해시 값은 해시 함수에 의해서 얻게 됨 데이터의 key 값이 함수를 통해서 변환된 간단한 정수

정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 할 때 활용

Hash 특징

• 키(key)에 데이터(value)를 매핑할 수 있는 데이터 구조
• 해시 함수를 통헤 키의 데이터(value)를 저장할 수 있는 주소를 계산
• 키를 통해 저장된 데이터를 빠르게 찾음, 속도의 획기적 증가
• 일반 배열 탐색 시간: O(n)
• 해시 탐색 시간: O(1)

문자열, 빈도수, 중복 검사 ⇒ 보통 해시를 활용

JAVA에서는 HashMap과 HashSet을 사용

• HashMap (빈도수 / 매핑)

  • key → value 형태의 저장

    HashMap<String, Integer> map = new HashMap<>();
    
    map.put("apple", 3); //해시에 데이터 삽입
    map.put("banana", 5);
    
    map.get("apple"); //3  -> 키 값으로 value 가져오기 없으면 null
    
    map.remove(key); // 키로 삭제
    
    map.getOrDefault(key, 기본값) // key가 있으면 value 가져오고 아니면 기본값
    
    map.containsKey("apple") // 키 존재 여부 확인
    
    map.keySet(); // 모든 key값 HashSet으로 가져옴 
    
    map.values(); // 모든 value 가져오
    
    map.size(); //개수 확인
    
    map.entrySet(); // key와 value 동시에 순회
    ex)
    for(Map.Entry(String, Integer> entry : map.entrySet()) {
    	entry.getKey() //키출력
    	entry.getValue() //value 출력
    }

• HashSet (중복 제거 / 존재 확인)

  • 중복 없는 데이터 저장

    HashSet<Integer> set = new HashSet<>();
    
    set.add(1); // 해시셋에 데이터 저장(중복 불가)
    set.add(2); 
    set.add(1);
    set의 결과 => 1, 2 //중복을 자동으로 제거
    
    set.contains(value); // 값이 있는지 확인 boolean으로 return
    
    set.remove(value); // 해시셋에서 데이터 삭제
    
    set.size(); // 해시 개수 확인
    
    HashSet은 인덱스가 없음
    for(int num : set) { //for-each , iterator도 가능은 
    이런 반복 방식으로 순
    }
    
    // 배열에 있는 반복을 제거 하고 싶다면?
    for(int num : arr) {
    	set.add(num) // 중복이 제거되며 저
    }
    
    // 두배열의 교집합
    for(int num : arr1) {
    	set.add(num) 
    }
    for(int num : arr2) {
    	if(set.contains(num){} 
    }

Hash 대표 문항

• 빈도 수 세기

  		arr = apple, banana, apple, orange, apple
  
  		HashMap<String, Integer> map = new HashMap<>();
  
  		for(String s : arr) {
  			map.put(s, map.getDefault(s,0)+1);
  		}