[Algorithm][Java] 해시테이블 (HashMap, HashSet)

해시테이블이란?

효율적인 탐색(빠른 탐색)을 위한 자료구조 key-value 데이터 쌍 형태로 저장
”h(k)는 키 k의 해시값이다 .”

• 시간 복잡도
  • 저장 - O(1)
  • 삭제 - O(1)
  • 검색 - O(1)
• 모든 데이터에 key 값은 무조건 존재해야 하며, 중복되는 key 값이 있으면 안된다.

 

HashMap

: Java에서는 Map 인터페이스와 HashMap 구현 클래스를 이용해 해시테이블을 만든다.

 

✔ HashMap 선언

Map<String, String> hashtable = new HashMap<>();

Map<String, String> hashtable = new HashMap<>() {{
    put("P1001", "인사과");
    put("P1002", "경영과");
}};

 

 

 

✔  HashMap 연산

// key-value 쌍 추가
hashtable.put("P1001", "인사과");

// key값이 "P1001"인 value 값 접근
hashtable.get("P1001");

// key값이 "P1001"인 value 값을 "이승규"로 수정
hashtable.replace("P1001","이승규");

// 제거
hashtable.revmoe("P1001");

// 해당 key가 존재하는지 확인(containsKey() - 시간복잡도 O(1))
if (hashtable.containsKey("P1001")) {
		System.out.println(hashtable.get("P1001"));
} else {
		System.out.println("저장된 키가 없습니다.");
}

 

 

✔ Map 정렬

• key 값이나 value 값으로만 정렬 가능

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

List<String> keyList = new ArrayList<>(map.keyset());
Collections.sort(keyList);

for (String key : keyList){
		Integer value = map.get(key);
}

 

 

 

---

 

 

해시셋(HashSet)

key만을 저장하는 자료구조

 

✔ HashSet 선언

Set<String> hashSet = new HashSet<>();
Set<String> hashset = new HashSet<>() {{
		add("홍길동");
		add("오미자");
}};

 

✔ HashSet 연산

hashset.add("홍길동"); // 추가
hashset.remove("오미자"); // 제거
hashset.contains("홍길동"); // true