1. 개요

이 기사에서는 Java에서 HashMap 을 사용하는 방법 과 내부적으로 어떻게 작동하는지 살펴 보겠습니다.

HashMap 과 매우 유사한 클래스 는 Hashtable 입니다. java.util.Hashtable 클래스 자체와 HashMap 과 Hashtable 의 차이점 에 대해 자세히 알아 보려면 다른 기사 몇 개를 참조하십시오 .

2. 기본 사용법

먼저 HashMap 이 맵 이라는 것이 무엇을 의미하는지 살펴 보겠습니다 . 맵은 키-값 매핑입니다. 즉, 모든 키가 정확히 하나의 값에 매핑되고 키를 사용하여 맵에서 해당 값을 검색 할 수 있습니다.

단순히 List에 값을 추가하지 않는 이유를 묻습니다. 왜 HashMap이 필요한 가요? 간단한 이유는 성능입니다. List에서 특정 요소를 찾으려면 시간 복잡도는 O (n) 이고 List이 정렬되면 예를 들어 이진 검색을 사용하여 O (log n)가 됩니다.

HashMap 의 장점은 값을 삽입하고 검색하는 시간 복잡도가 평균 O (1)이라는 것 입니다. 나중에 어떻게 이룰 수 있는지 살펴 보겠습니다. 먼저 HashMap 사용 방법을 살펴 보겠습니다 .

2.1. 설정

기사 전체에서 사용할 간단한 클래스를 만들어 보겠습니다.

public class Product {

    private String name;
    private String description;
    private List<String> tags;
    
    // standard getters/setters/constructors

    public Product addTagsOfOtherProduct(Product product) {
        this.tags.addAll(product.getTags());
        return this;
    }
}

2.2. 놓다

이제 String 유형의 키 와 Product 유형의 요소를 사용하여 HashMap 을 만들 수 있습니다 .

Map<String, Product> productsByName = new HashMap<>();

그리고 HashMap 에 제품을 추가합니다 .

Product eBike = new Product("E-Bike", "A bike with a battery");
Product roadBike = new Product("Road bike", "A bike for competition");
productsByName.put(eBike.getName(), eBike);
productsByName.put(roadBike.getName(), roadBike);

2.3. 가져 오기

키로 맵에서 값을 검색 할 수 있습니다.

Product nextPurchase = productsByName.get("E-Bike");
assertEquals("A bike with a battery", nextPurchase.getDescription());

맵에 존재하지 않는 키 값을 찾으려고하면 null 값을 얻게됩니다 .

Product nextPurchase = productsByName.get("Car");
assertNull(nextPurchase);

같은 키로 두 번째 값을 삽입하면 해당 키에 대해 마지막으로 삽입 된 값만 가져옵니다.

Product newEBike = new Product("E-Bike", "A bike with a better battery");
productsByName.put(newEBike.getName(), newEBike);
assertEquals("A bike with a better battery", productsByName.get("E-Bike").getDescription());

2.4. 키로 Null

HashMap 을 사용하면 null 을 키로 사용할 수도 있습니다 .

Product defaultProduct = new Product("Chocolate", "At least buy chocolate");
productsByName.put(null, defaultProduct);

Product nextPurchase = productsByName.get(null);
assertEquals("At least buy chocolate", nextPurchase.getDescription());

2.5. 동일한 키를 가진 값

또한 다른 키를 사용하여 동일한 객체를 두 번 삽입 할 수 있습니다.

productsByName.put(defaultProduct.getName(), defaultProduct);
assertSame(productsByName.get(null), productsByName.get("Chocolate"));

2.6. 값 제거

HashMap 에서 키-값 매핑을 제거 할 수 있습니다 .

productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));

2.7. 키 또는 값이 맵에 있는지 확인

Map에 키가 있는지 확인하려면 containsKey () 메서드를 사용할 수 있습니다 .

productsByName.containsKey("E-Bike");

또는Map에 값이 있는지 확인하기 위해 containsValue () 메서드를 사용할 수 있습니다 .

productsByName.containsValue(eBike);

두 메서드 호출 모두이 예제에서 true 를 반환 합니다 . 매우 비슷해 보이지만이 두 메서드 호출 간의 성능에는 중요한 차이가 있습니다. 키가 있는지 확인하는 복잡성은 O (1) 이고, 요소를 확인하는 복잡성 은 맵의 모든 요소를 ​​반복해야하므로 O (n) 입니다.

2.8. HashMap 반복

HashMap의 모든 키-값 쌍을 반복하는 세 가지 기본 방법이 있습니다 .

모든 키 세트를 반복 할 수 있습니다.

for(String key : productsByName.keySet()) {
    Product product = productsByName.get(key);
}

또는 모든 항목 집합을 반복 할 수 있습니다.

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
    Product product =  entry.getValue();
    String key = entry.getKey();
    //do something with the key and value
}

마지막으로 모든 값을 반복 할 수 있습니다.

List<Product> products = new ArrayList<>(productsByName.values());

3. 열쇠

HashMap 의 키로 모든 클래스를 사용할 수 있습니다 . 그러나Map가 제대로 작동하려면 equals () 및 hashCode ()에 대한 구현을 제공해야합니다 . 제품을 키로, 가격을 값으로 사용하는Map를 원한다고 가정 해 보겠습니다.

HashMap<Product, Integer> priceByProduct = new HashMap<>();
priceByProduct.put(eBike, 900);

equals () 및 hashCode () 메소드를 구현해 보겠습니다 .

@Override
public boolean equals(Object o) {
    if (this == o) {
        return true;
    }
    if (o == null || getClass() != o.getClass()) {
        return false;
    }

    Product product = (Product) o;
    return Objects.equals(name, product.name) &&
      Objects.equals(description, product.description);
}

@Override
public int hashCode() {
    return Objects.hash(name, description);
}

참고 해시 코드 () 와 같음 () 우리가Map 키로뿐만 아니라Map의 값으로 사용되는 클래스를 사용하려는 경우에만 클래스를 오버라이드 (override) 할 필요가 있습니다. 이 기사의 섹션 5에서 이것이 필요한 이유를 살펴 보겠습니다.

4. Java 8의 추가 메소드

Java 8은 HashMap 에 몇 가지 기능 스타일 메서드를 추가했습니다 . 이 섹션에서는 이러한 방법 중 일부를 살펴 보겠습니다.

각 방법에 대해 두 가지 예를 살펴 보겠습니다. 첫 번째 예는 새로운 방법을 사용하는 방법을 보여주고 두 번째 예는 이전 버전의 Java에서 동일한 방법을 사용하는 방법을 보여줍니다.

이러한 방법은 매우 간단하므로 더 자세한 예제는 보지 않겠습니다.

4.1. 각각()

foreach는 방법은Map에있는 모든 요소를 반복 기능 - 스타일의 방법이다 :

productsByName.forEach( (key, product) -> {
    System.out.println("Key: " + key + " Product:" + product.getDescription());
    //do something with the key and value
});

Java 8 이전 :

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
    Product product =  entry.getValue();
    String key = entry.getKey();
    //do something with the key and value
}

우리의 기사 자바 8 설명서 대해 forEach는 커버 foreach는 보다 상세하게 루프를.

4.2. getOrDefault ()

getOrDefault () 메서드를 사용하여 Map에서 값을 가져 오거나 지정된 키에 대한 매핑이없는 경우 기본 요소를 반환 할 수 있습니다.

Product chocolate = new Product("chocolate", "something sweet");
Product defaultProduct = productsByName.getOrDefault("horse carriage", chocolate); 
Product bike = productsByName.getOrDefault("E-Bike", chocolate);

Java 8 이전 :

Product bike2 = productsByName.containsKey("E-Bike") 
    ? productsByName.get("E-Bike") 
    : chocolate;
Product defaultProduct2 = productsByName.containsKey("horse carriage") 
    ? productsByName.get("horse carriage") 
    : chocolate;

4.3. putIfAbsent ()

이 방법을 사용하면 새 매핑을 추가 할 수 있지만 지정된 키에 대한 매핑이 아직없는 경우에만 가능합니다.

productsByName.putIfAbsent("E-Bike", chocolate);

Java 8 이전 :

if(productsByName.containsKey("E-Bike")) {
    productsByName.put("E-Bike", chocolate);
}

우리의 기사 Merging Two Maps with Java 8 에서는이 방법을 자세히 살펴 봅니다.

4.4. merge ()

그리고 함께 병합 () , 우리는 매핑이 존재하는 경우 해당 키의 값을 수정하거나 새 값을 달리 추가 할 수 있습니다 :

Product eBike2 = new Product("E-Bike", "A bike with a battery");
eBike2.getTags().add("sport");
productsByName.merge("E-Bike", eBike2, Product::addTagsOfOtherProduct);

Java 8 이전 :

if(productsByName.containsKey("E-Bike")) {
    productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2);
} else {
    productsByName.put("E-Bike", eBike2);
}

4.5. 계산 ()

으로 계산 () 에있어서, 우리는 소정의 키 값을 계산할 수있다 :

productsByName.compute("E-Bike", (k,v) -> {
    if(v != null) {
        return v.addTagsOfOtherProduct(eBike2);
    } else {
        return eBike2;
    }
});

Java 8 이전 :

if(productsByName.containsKey("E-Bike")) {    
    productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2); 
} else {
    productsByName.put("E-Bike", eBike2); 
}

merge () 및 compute () 메소드 가 매우 유사하다는 점은 주목할 가치가 있습니다. 컴퓨팅 () 메소드는 : 두 개의 인수 받아 키 와 BiFunction 다시 매핑에 대한합니다. 그리고 merge () 는 세 개의 매개 변수를받습니다 : key , 키가 아직 존재하지 않는 경우 맵에 추가 할 기본값 , 리매핑을위한 BiFunction .

5. HashMap 내부

이 섹션에서는 HashMap 이 내부적으로 어떻게 작동하는지 , 예를 들어 간단한 List 대신 HashMap 을 사용하면 어떤 이점이 있는지 살펴볼 것입니다.

지금까지 살펴본 것처럼 키로 HashMap 에서 요소를 검색 할 수 있습니다 . 한 가지 접근 방식은 List을 사용하고 모든 요소를 ​​반복하고 키가 일치하는 요소를 찾을 때 반환하는 것입니다. 이 접근법의 시간 및 공간 복잡성은 모두 O (n) 입니다.

함께 HashMap에 , 우리의 평균 시간 복잡도 달성 할 수 O (1) 에 대한 풋 과 수 의 운영 및 공간 복잡도 O (n)을 . 어떻게 작동하는지 봅시다.

5.1. 해시 코드와 같음

모든 요소를 ​​반복하는 대신 HashMap 은 키를 기반으로 값의 위치를 ​​계산하려고합니다.

순진한 접근 방식은 가능한 한 많은 요소를 포함 할 수있는 List을 갖는 것입니다. 예를 들어 키가 소문자라고 가정 해 봅시다. 그러면 크기 26의 List이 있으면 충분하며 키 'c'를 사용하여 요소에 액세스하려면 위치 3에있는 요소임을 알고 직접 검색 할 수 있습니다.

그러나이 접근 방식은 키 스페이스가 훨씬 더 큰 경우 그다지 효과적이지 않습니다. 예를 들어, 우리의 키가 정수라고합시다. 이 경우 List의 크기는 2,147,483,647이어야합니다. 대부분의 경우 요소가 훨씬 적으므로 할당 된 메모리의 상당 부분이 사용되지 않습니다.

HashMap 은 소위 버킷에 요소를 저장하고 버킷 수를 용량 이라고 합니다 .

맵에 값을 넣을 때 키의 hashCode () 메서드는 값이 저장 될 버킷을 결정하는 데 사용됩니다.

값을 검색하기 위해 HashMap 은 hashCode ()를 사용하여 동일한 방식으로 버킷을 계산합니다 . 그런 다음 해당 버킷에서 찾은 객체를 반복하고 키의 equals () 메서드를 사용하여 정확히 일치하는 항목을 찾습니다.

5.2. 키의 불변성

대부분의 경우 변경 불가능한 키를 사용해야합니다. 또는 최소한 변경 가능한 키 사용의 결과를 알고 있어야합니다.

Map에 값을 저장하기 위해 키를 사용한 후 키가 변경 될 때 어떤 일이 발생하는지 살펴 보겠습니다.

이 예에서는 MutableKey를 만듭니다 .

public class MutableKey {
    private String name;

    // standard constructor, getter and setter

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        MutableKey that = (MutableKey) o;
        return Objects.equals(name, that.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}

그리고 여기에 테스트가 있습니다.

MutableKey key = new MutableKey("initial");

Map<MutableKey, String> items = new HashMap<>();
items.put(key, "success");

key.setName("changed");

assertNull(items.get(key));

보시다시피 키가 변경되면 더 이상 해당 값을 가져올 수 없으며 대신 null 이 반환됩니다. HashMap 이 잘못된 버킷에서 검색 하기 때문 입니다.

위의 테스트 케이스는 HashMap 이 내부적 으로 어떻게 작동 하는지 잘 이해하지 못한다면 놀랍습니다 .

5.3. 충돌

이것이 올바르게 작동하려면 동일한 키가 동일한 해시를 가져야하지만 다른 키가 동일한 해시를 가질 수 있습니다 . 두 개의 다른 키에 동일한 해시가있는 경우 해당 키에 속하는 두 값이 동일한 버킷에 저장됩니다. 버킷 내부에서 값은 List에 저장되고 모든 요소를 ​​반복하여 검색됩니다. 비용은 O (n) 입니다.

Java 8 ( JEP 180 참조 )부터는 버킷에 8 개 이상의 값이 포함 된 경우 한 버킷 내부의 값이 저장되는 데이터 구조가 List에서 균형 트리로 변경되고, 다음과 같은 경우 List으로 다시 변경됩니다. 어떤 점에서는 버킷에 6 개의 값만 남습니다. 이것은 성능을 O (log n)로 향상시킵니다 .

5.4. 용량 및 부하율

값이 여러 개인 버킷이 많지 않도록하려면 버킷의 75 % (로드 비율)가 비어 있지 않으면 용량이 두 배가됩니다. 부하율의 기본값은 75 %이고 기본 초기 용량은 16입니다. 둘 다 생성자에서 설정할 수 있습니다.

5.5. Put 및 Get 작업 요약

넣기 및 가져 오기 작업이 어떻게 작동 하는지 요약 해 보겠습니다 .

맵에 요소를 추가하면 HashMap 이 버킷을 계산합니다. 버킷에 이미 값이있는 경우 해당 버킷에 속한 List (또는 트리)에 값이 추가됩니다. 부하율이Map의 최대 부하율보다 커지면 용량은 2 배가됩니다.

맵에서 값을 얻으려면 HashMap 이 버킷을 계산하고 List (또는 트리)에서 동일한 키로 값을 가져옵니다.

6. 결론

이 기사에서는 HashMap 을 사용하는 방법과 내부적으로 어떻게 작동하는지 살펴 보았습니다 . 함께 ArrayList를 , HashMap의는 그것이 후드를 작동하는 방법을 사용하는 방법의 좋은 지식이 매우 편리이고, 그래서 자바에서 가장 자주 사용되는 데이터 구조 중 하나입니다. 우리의 기사 The Java HashMap Under the Hood 는 HashMap 의 내부를 더 자세히 다룹니다 .

평소처럼 전체 소스 코드는 Github에서 사용할 수 있습니다 .