[Java] 자료구조 HashMap의 특징 및 핵심 원리

Java

[Java] 자료구조 HashMap의 특징 및 핵심 원리

하부루 2024. 9. 18. 12:00

HashMap

HashMap 은 키(Key)와 값(value)쌍을 저장하는 자료 구조
각 키는 고유하며, 키를 사용하여 해당하는 값을 빠르게 검색할 수 있음

HashMap의 특징

키 기반의 빠른 액세스 : 키를 사용하여 값을 빠르게 검색하거나 수정할 수 있음
순서를 보장하지 않음 : 'HashMap' 은 내부적으로 키의 순서를 보장하지 않음
키의 중복 불가 : 이미 존재하는 키에 대해 값을 저장하면 기존 값이 덮어씌워짐
null 키와 값 : 'HashMap'은 null 키와 null 값을 저장할 수 있음 하지만 키는 중복이 불가하므로 null 키는 하나만 저장될 수 있음
키 기반의 유연성 : 어떤 객체든 키로 사용할 수 있음
해싱 충돌 : 두 개 이상의 키가 동일한 해시 코드를 가질 때 충돌이 발생

HashMap 주요 메서드

// 새로운 HashMap 생성
	Map<String, Integer> exMap = new HashMap<>();

// HashMap에 데이터 추가
	exMap.put("홍길동", 27);
	exMap.put("김유신", 30);
	exMap.put("김춘추", 42);

	System.out.println("get(홍길동) : " + exMap.get("홍길동"));


// HashMap에 지정된 key값의 vlaue값 삭제
	exMap.remove("김유신");
	
	System.out.println("get(김유신) : " + exMap.get("김유신"));


// HashMap에 지정된 key값이 있는지 확인
	boolean ex1 = exMap.containsKey("김유신");
	boolean ex2 = exMap.containsKey("김춘추");
	
	System.out.println("containsKey(김유신) : " + ex1);
	System.out.println("containsKey(김춘추) : " + ex2);


// HashMap의 크기 (key-value 쌍의 수)
	int size = exMap.size();
	
	System.out.println("exMap.size() : " + size);


// HashMap이 비어있는지 확인
	boolean ex3 = exMap.isEmpty();
	
	System.out.println("exMap.isEmpty() : " + ex3);

// HashMap에 포함된 모든 키를 반환
	Set<String> keys = exMap.keySet();
	
	System.out.println("exMap.keySet() : " + keys);


// HashMap에 포함된 모든 값을 반환
	Collection<Integer> values = exMap.values();
	
	System.out.println("exMap.values() : " + values);

// HashMap의 모든 key-value 쌍을 제거
	exMap.clear();

HashMap 핵심 원리

HashMap의 핵심 원리는 해싱(Hashing)
Hash란 주어진 입력 데이터를 고정된 크기의 고유한 값(보통 정수)으로 변환하는 과정
해싱 함수(Hashing Function)는 키(Key)를 받아서 정수값인 해시코드(Hashcode)를 반환
반환된 해시코드는 Hash 배열의 각 요소인 버킷(Bucket)의 인덱스가 됨
해시코드(Hashcode)는 HashTable, HashSet, HashMap 같은 자료 구조에서 사용

💡 하지만 해시코드를 생성하는 해시 함수는 완벽하지 않기 때문에 키 값이 달라도 해시코드가 동일한 경우가 존재 함

해시 충돌 (Hash Collision) 해결 방법

해싱 충돌은 서로 다른 키들이 동일한 해시 값을 가지게 되어 동일한 버킷에 저장될 때 발생
해시 기반 데이터 구조에서는 해시 충돌을 효율적으로 해결하기 위해 여러 가지 방법을 사용

[ 체이닝 (Chaining) ]

체이닝은 각 버킷이 자체적으로 하나의 연결 리스트를 가지는 방식
충돌이 발생하면 해당 버킷의 리스트에 새로운 요소를 추가
동일한 해시 값을 가진 요소들은 이 리스트에 추가
충돌이 빈번하게 발생해도 리스트에 요소를 추가할 수 있어, 특정 버킷의 크기에 제한이 없음
많은 충돌이 발생하면 리스트가 길어져 검색 시간이 느려질 수 있음

체이닝을 이용해 같은 해시 값에 여러개의 버킷이 저장되어 있는 경우

get(”강감찬”)을 실행하게 되면 먼저 44498432 해시 값을 가진 [김유신,30]을 찾고

key값이 일치하지 않기 때문에 다음 요소인 [강감찬, 42]를 찾아 반환한다.

[ 개방 주소법 (Open Addressing) ]

충돌이 발생할 경우 다른 빈 버킷을 찾아 데이터를 저장하는 방식
별도의 메모리 공간 없이 hash table 내에서 충돌에 대한 처리가 가능
key-value 1:1 매칭 구조가 유지
데이터가 늘어나는만큼 미리 bucket에 공간확보가 중요
빈 버킷을 찾는 방법
- 선형 탐사(Linear Probing) : 충돌이 발생하면 다음 빈 버킷을 순차적으로 찾음
- 이차 탐사(Quadratic Probing) : 충돌이 발생하면 이차 함수의 간격으로 빈 버킷을 찾음
- 이중 해싱(Double Hashing ): 두 번째 해시 함수를 사용하여 빈 버킷을 찾음

개방 주소법을 이용해 데이터를 조회하는 경우

get(”강감찬”)을 실행하게 되면 먼저 44498432 해시 값을 가진 [김유신,30]을 찾는다.

key값이 일치하지 않기 때문에 탐사법을 사용해 다음 요소들을 순회한다.

key값이 일치하는 [강감찬, 42]를 찾아 반환한다.

[ 재해싱 (Rehashing) ]

해시 테이블이 가득 차거나 충돌이 너무 많이 발생할 경우
해시 테이블의 크기를 늘리고 모든 키-값 쌍을 새로운 크기에 맞게 재삽입하는 방법
메모리 사용량을 늘리는 대신 충돌을 줄이고 성능을 향상시키는 데 효과적

HashMap 장점

데이터의 순서가 중요하지 않을 때 사용하면 좋음
key가 중복되지 않는다는 점을 활용하면 좋음
자료가 많아져도 빠르게 조회가 가능한 장점
키를 기반으로 빠른 데이터 액세스가 필요할 때 사용하면 좋음
어떤 객체든 키로 사용할 수 있다는 장점도 있음