데이터 크기가 아무리 커져도(대용량 데이터) 연산이 걸리는 시간이 거의 변하지 않는다는 뜻
시간 복잡도(Big-O)란?
알고리즘이 입력 크기 N에 따라 어떻게 수행 시간이 늘어나는지를 수학적으로 표현하는 기호
(대표적인 예시)
O(1): 상수 시간 – N에 무관하게 일정
O(n): 선형 시간 – N에 비례
O(n²): 제곱 시간 – N²에 비례
O(1)의 의미
상수 시간(constant time): 처리할 데이터가 10개든 1,000만 개든, “언제나 대략 같은” 단계 수를 수행한다.
단, 해시 충돌이 심하면 최악의 경우 O(n)으로 느려질 수 있지만,
Java 8 이후 버킷이 트리화되어 대부분 O(1)에 가깝게 동작한다.
예시
// 배열 인덱스 접근
int[] arr = {10, 20, 30, 40, 50};
int x = arr[3]; // arr[3]에 바로 접근 → O(1)
// HashMap 조회/삽입
Map<String, Integer> map = new HashMap<>();
map.put("A", 1); // 키 “A” 해시 → 곧장 버킷에서 저장 → O(1) 평균
Integer v = map.get("A"); // 동일하게 바로 꺼내기 → O(1) 평균
왜 일정 시간인가?
해시 함수가 키를 ‘숫자 인덱스’로 변환
내부 배열(버킷) 중 정확히 그 위치에 바로 접근
반복문·검색 절차 없이 바로 저장·조회 가능
HashMap 탄생
Java 1.2 때 도입된 Collections 프레임워크로 도입되었다.
과거 Hashtable(동기화된 해시 테이블)을 대체하여
성능 향상 + 유연한 확장성을 제공한다
Java8 때 잦은 충돌이 발생해떤 버킷을
트리(Tree) 구조로 전환함에 따라 시간복잡도를 개선하여 성능 안정성 개선하였다.
HashMap 장점
빠른 조회, 삽입: 해시 함수를 통해 인덱스를 바로 계산
유연한 API: getOrDefault, computeIfAbsent, merge 등 편리한 메서드 활용
null 허용: key, value 값에 null을 사용할 수 있음 > 간단한 자료구조로 활용 가능
"apple" 이라는 문자열 키를 넣으면 해시 함수는 이를 내부적으로 (예시) 93084631 같은 정수로 변환한다.
버킷(bucket) 위치 계산
변환된 숫자를 배열 크기로 나눈 나머지(hash%capacity)를 구해서, 실제 데이터를 저장할 배열 인덱스로 사용한다.
예: 93084631 % 16 = 7 → 7번 슬롯에 저장한다
*버킷(bucket): 해시밗으로 결정된 내부 배열(table)의 슬롯
String key = "apple";
int h = key.hashCode(); // .hashCode()가 해시 함수를 호출
System.out.println("key.hashcode(): " + h); // 93029210
int capacity = 16; // HashMap의 기본 초기 버킷 수
int index = (h & 0x7FFFFFFF) % capacity;
// 음수 방지(최상위 비트 제거) 후 capacity로 모듈러(나머지 구하는 연산)
System.out.println("index = " + index); // 10
get()과 put() 사이에 다른 스레드가 끼어들어 덮어쓰기가 발생함에 따라 누락될 수 있다.
// HashMap의 멀티스레드에서 동시에 수정할 경우 (get, put)
Map<String, Integer> map2 = new HashMap<>();
Runnable incr = () -> {
for (int i = 0; i < 1000; i++) {
// null 대신 0을 기본으로 쓰기 때문에 NPE가 사라집니다.
int old = map2.getOrDefault("count", 0);
map2.put("count", old + 1);
}
};
Thread t1 = new Thread(incr);
Thread t2 = new Thread(incr);
t1.start();
t2.start();
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println("map2 count: " + map2.get("count"));
// 2000이 아니라 예상보다 작은 값이 나올 수 있음
만약 멀티스레드 환경이라면 Collections.synchronizedMap / ConcurrentHashMap 중 하나 선택해서 사용
// synchronize 블록 묶기
// Collections.synchronizedMap(new HashMap<>())
Map<String, Integer> map3 = new HashMap<>();
Runnable incr2 = () -> {
for (int i = 0; i < 1000; i++) {
synchronized (map3) { // synchronized(map)로 묶어 두 스레드가 동시에 블록 내부로 진입하지 못하게 막는다.
int old = map3.getOrDefault("count",0);
map3.put("count", old + 1);
}
}
};
Thread t3 = new Thread(incr2);
Thread t4 = new Thread(incr2);
t3.start(); t4.start();
try {
t3.join();
t4.join();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println("synchronized count: " + map3.get("count")); // 항상 2000
ConcurrentHashMap
ConcurrentHashMap<String, Integer> map4 = new ConcurrentHashMap<>();
map.put("count", 0);
Runnable incr4 = () -> {
for (int i = 0; i < 1000; i++) {
// key가 없으면 1, 있으면 old + 1
map4.merge("count", 1, Integer::sum);
}
};
Thread t7 = new Thread(incr4);
Thread t8 = new Thread(incr4);
t7.start(); t8.start();
try {
t7.join();
t8.join();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
System.out.println("ConcurrentHashMap count: " + map4.get("count")); // 항상 2000
메모리 오버헤드 (실제 저장 데이터 크기보다 더 많은 메모리를 사용)
버킷 배열 + 노드 객체 +@(트리 노드)
버킷 배열: 배열(기본 크기 16x8byte), 배열 참조당 8byte
노드 객체: 객체 헤더(16byte), int hash(4byte), K key 참조(8byte), V value(8byte), Node(8byte) → 대략 44byte+@
작은 자료에는 과도할 수 있다. → 단순 배열이나 ArrayList 등이 보다 가벼운 대안으로 고려할 수 있다.
해시 충돌 시 성능 저하 가능
커스텀 객체의 hashCode, equals 구현에 주의
충돌이 잦아질 경우 한 버킷에 몰린 엔트리들을 순차 탐색하는 과정에서 성능이 저하된다.
잘못된 hashcode()는 충돌을 유발할 수 있다. → 항상 상수이거나 일부 필드만 사용하는 경우
// 예시1
class Person {
String name;
int age;
// 잘못된 hashCode: 모든 Person이 같은 해시값을 가짐
@Override
public int hashCode() {
return 42;
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Person)) return false;
Person p = (Person) o;
return name.equals(p.name) && age == p.age;
}
}
좋은 hashcode() / equals() 구현 방법
서로 다른 객체는 가급적 다른 해시값을 내도록 한다.
equals() 에 쓰인 모든 필드를 hashCode() 에도 반영해야 일관성 유지된다.
// ↓↓↓↓↓↓↓↓↓↓↓↓ 좋은 hachcode(), equals 구현 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
// 예시2
class Person {
String name;
int age;
@Override
public int hashCode() {
// name과 age를 모두 이용해 해시값 생성
return Objects.hash(name, age);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person p = (Person) o;
return age == p.age && name.equals(p.name);
}
}
Objects.hash(...) 는 내부적으로 여러 필드를 섞어 좋은 분포의 정수를 만들고,
equals() 와 hashCode() 의 계약(Contract) 을 지켜야,
a.equals(b) 이면 반드시 a.hashCode() == b.hashCode() 이어야 하고
public class ItemList {
private List<Item> items;
private List<Item> fruits = new ArrayList<>();
private List<Item> vegetables = new ArrayList<>();
private List<Item> dairy = new ArrayList<>();
public ItemList(List<Item> items) {
this.items = items;
categorize();
}
private void categorize() {
for (Item item : items) {
switch (item.getCategory()) {
case "fruit":
fruits.add(item);
break;
case "vegetable":
vegetables.add(item);
break;
case "dairy":
dairy.add(item);
break;
}
}
}
}
public static void main(String[] args) {
// 과일 데이터 추가
List<Item> items = Arrays.asList(
new Item("사과", "fruit"),
new Item("바나나", "fruit"),
new Item("당근", "vegetable"),
new Item("브로콜리", "vegetable"),
new Item("우유", "dairy")
);
// List 방식으로 분류 및 출력
ItemList listGrouping = new ItemList(items);
listGrouping.printCategories();
}
HashMap으로 데이터 관리 방법
public class ItemHashmap {
private Map<String, List<Item>> grouped = new HashMap<>();
public ItemHashmap(List<Item> items) {
for (Item item : items) {
grouped
.computeIfAbsent(item.getCategory(), k -> new ArrayList<>())
.add(item);
}
}
}
public static void main(String[] args) {
// 과일 데이터 추가
List<Item> items = Arrays.asList(
new Item("사과", "fruit"),
new Item("바나나", "fruit"),
new Item("당근", "vegetable"),
new Item("브로콜리", "vegetable"),
new Item("우유", "dairy")
);
// HashMap 방식으로 분류 및 출력
ItemHashmap mapGrouping = new ItemHashmap(items);
mapGrouping.printCategories();
}
