HashMap이란? / 해시 충돌(Hash Collision) /HashMap 메서드 정리

HashMap이란 Java의 내장 자료구조로, "Map" 인터페이스를 구현한 클래스이다. 키(key)와 값(value)를 하나의 쌍으로 저장하는 자료구조인데 이러한 키와 값의 쌍을 엔트리(Entry)라고 합니다.

 

https://www.codespeedy.com/initialize-a-hashmap-in-java/

 

---

 

HashMap의 특징

 

 

장점

1. 키와 값의 쌍으로 이루어진 데이터 저장  
2. 중복 키 허용 안함 : 동일한 키로 데이터를 저장하면 기존의 값을 덮어쓴다
3. 키에 대한 null 값 허용: 키가 null인 경우, 해당 키에 연결된 값은 HashMap의 0번째 버킷(Bucket)에 저장된다

 

 

단점

1. 순서를 유지하지 않는다 : 데이터의 순서가 중요한 경우에는 LinkedHashMap을 사용하면 된다
2. 멀티스레드 환경에서의 동시성 제어 : HashMap은 멀티스레드 환경에서 여러 스레드가 동시에 HashMap을 조작하는 것을 안전하게 제어하지 않는다. 여러 스레드에서 동시에 HashMap을 사용해야 하는 경우엔 ConcurrentHashMap을 사용하거나 외부에서 동기화를 제공해야 한다.
3. 해시 충돌 : 해시 함수가 서로 다른 두 키에 대해 동일한 해시 값을 반환하는 경우 해시 충돌이라고 한다. 해시 충돌이 발생하면 HashMap의 성능이 저하될 수 있다.
4. 부분적 탐색 불가능 : 특정 범위의 값을 찾는 것이 불가능하거나 매우 복잡하다. 이건 TreeMap에서는 가능하다

HashMap은 데이터 저장, 검색, 삭제 등의 작업이 빠르게 이루어져야 하는 경우에 사용된다. 그래서 키를 통해 데이터에 빠르게 접근할 수 있어야 하는 많은 알고리즘과 어플리케이션에서 유용하게 사용된다.

 

 

---

HashMap의 내부 동작 원리

 

1. 데이터 추가 : HashMap에 데이터를 추가하려고 하면, 먼저 키의 해시코드를 계산한다. 이 해시코드는 해시 함수에 의해 변환되어 인덱스 값으로 사용된다. 이 인덱스는 내부의 '버킷' 배열에서 특정 위치를 가리킨다. 여기에 데이터(키-값 쌍)이 저장된다.

 

HashMap<String, Integer> map = new HashMap<>();
map.put("One", 1); // "One" -> hashCode() -> hash function -> index

 

2.데이터 조회 : 키를 이용하여 값을 조회할 때도 키의 해시코드가 먼저 계산된다. 그 다음, 해시 함수를 통해 변환된 인덱스를 이용해 해당 위치를 찾고, 그 위치에 지정된 값을 반환한다.

 

int value = map.get("One"); // "One" -> hashCode() -> hash function -> index

 

 

---

 

해시 충돌(Hash Collision)

해시 충돌은 두 개 이상의 키가 동일한 위치에 매핑될 때 발생하는 현상이다. 이는 모든 키가 고유한 해시 코드를 생성할 수 없기 때문에 발생하는데 이는 해시 함수의 도메인이 해시 코드의 범위보다 크기 때문이다. 

예를 들어 : 모든 가능한 문자열을 고유한 32 비트 정수에 매핑하는건 불가능하다.

 

이런 해시 충돌은 데이터의 조회, 삽입, 삭제 시간을 느리게 만들 수 있어서, 해시 충돌을 관리하는건 중요하다

 

해시 충돌 처리 방법

해시 충돌을 해결하는 방법에는 체이닝과 오픈 어드레싱이다.

 

두 방법 모두 장단점이 있다. 체이닝은 구현이 간단하지만 충돌이 많이 발생하는 경우 연결 리스트가 길어져 성능이 저하될 수 있다. 

반면에 오픈 어드레싱은 해시 테이블의 크기를 넘어서는 데이터를 저장할 수 없지만 메모리를 더 효율적으로 사용하고, 캐시 효율성이 높다.

 

1. 체이닝(Chaining) : 각 버킷에 연결 리스트를 저장하여, 해시 충돌이 발생하면 해당 버킷의 연결 리스트에 데이터를 추가하는 방식이다. 

예제 코드 : 

import java.util.*;

public class HashMapExample {
    public static void main(String[] args) {

        // 해시 맵 생성
        HashMap<Integer, String> map = new HashMap<>();

        // 추가
        map.put(1, "Apple");
        map.put(2, "Banana");
        map.put(3, "Cherry");

        // 맵에 더 추가하기
        map.put(4, "melon");
        map.put(5, "orange");

        // 사이즈 출력
        System.out.println("Size of map is: " + map.size());
        System.out.println(map);
    }
}

이런 식으로 key-value 쌍이 HashMap에 추가되면 HashMap은 key에 대한 해시 코드를 계산하고, 이를 사용하여 데이터를 저장할 버킷의 인덱스를 결정한다. 만약 동일한 해시코드를 가진 다른 key-value 쌍이 추가되면, HashMap은 체이닝 방식을 통해 동일한 버킷에 데이터를 저장한다.

 

체이닝 방식을 활용한 예시를 보자면

import java.util.HashMap;

public class HashCollisionExample {

    static class Key {
        Integer id;

        Key(Integer id) {
            this.id = id;
        }

        @Override
        public int hashCode() {
            return id % 10; // 간단한 해시 함수
        }

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

    public static void main(String[] args) {
        HashMap<Key, String> map = new HashMap<>();
        map.put(new Key(1), "Key with ID is 1");
        map.put(new Key(11), "Key with ID is 11");
        map.put(new Key(21), "Key with ID is 21");

        System.out.println(map.get(new Key(1)));
        System.out.println(map.get(new Key(11)));
        System.out.println(map.get(new Key(21)));
    }
}

이 코드는 Key 라는 클래스를 만들고 Integer id를 필드로 가지고 있다. 그리고 해시 코드는 id를 10으로 나눈 나머지로 계산한다. 그렇게 되면 1, 11, 21인 Key 객체는 동일한 해시 코드를 가지게 된다. 그래서 이들은 HashMap에 동일한 버킷에 위치하게 되는데

HashMap은 LinkedList를 사용하여 동일한 버킷에 있는 항목들을 저장하므로, 각 키를 사용하여 올바른 값을 검색할 수 있다. 이게 체이닝 방식으로 해시 충돌을 해결하는 방법이다.

 

---

 

 

2.오픈 어드레싱(Open Addressing) : 모든 데이터를 해시 테이블 자체에 저장하며, 충돌이 발생하면 다른 버킷을 찾아 데이터를 저장하는 방식이다. 다른 버킷을 찾는 방법에는 선형 탐사, 제곱 탐사, 이중 해싱 등이 있다.

 

예제 코드 :  간단한 형태의 선형 탐사 코드 예시입니다.

public class OpenAddressing {
    private int M = 31607;  // size of the hash table
    private String[] keys = new String[M];
    private String[] vals = new String[M];

    private int hash(String key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public void put(String key, String val) {
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                break;
        keys[i] = key;
        vals[i] = val;
    }

    public String get(String key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                return vals[i];
        return null;
    }
}

 

public class OpenAddressing {
    private int M = 31607;  // size of the hash table
    private String[] keys = new String[M];
    private String[] vals = new String[M];

M은 해시 테이블의 크기를 정의한다. keys 와 vals 배열은 각각 키와 값을 저장한다. 이 두 배열은 같은 인덱스를 공유하여 키-값 쌍을 관리한다.

 

    private int hash(String key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

'hash()' 메서드는 주어진 키의 해시코드를 계산해서 이를 해시 테이블의 크기'M'으로 나눈 나머지를 반환한다. 

이렇게 해서 모든 키는 해시 테이블 내의 유효한 인덱스를 가지게 된다.

 

    public void put(String key, String val) {
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                break;
        keys[i] = key;
        vals[i] = val;
    }

put() 메서드는 주어진 키-값 쌍을 해시 테이블에 저장한다. 우선 키의 해시코드를 계산해서 시작 인덱스를 찾는다. 그리고 순차적으로 검사해서 첫 번째 빈 위치에 키-값 쌍을 저장한다. 만약 키가 이미 존재하면, 해당 키에 대한 값을 새 값으로 업데이트한다.

 

    public String get(String key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
            if (keys[i].equals(key))
                return vals[i];
        return null;
    }
}

'get()' 메서드는 주어진 키에 해당하는 값을 반환한다. 키의 해시코드를 계산하여 시작 인덱스를 찾고, 이 인덱스부터 순차적으로 해시 테이블을 검사하여 해당 키를 찾는다. 키를 찾으면 대응하는 값을 반환하고, 그렇지 않으면 'null'을 반환한다. 

 

이 코드는 간단한 예시로 실제 스레드에 안전하지 않으므로 동시성을 고려한 상황에서는 동기화를 고려해야 한다.

---

HashMap의 사용법

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("One", 1);
        map.put("Two", 2);
        map.put("Three", 3);
    }
}

HashMap을 만들고 put 메서드를 사용하여 키-값 쌍을 추가할 수 있다.

 

System.out.println(map.get("Two")); // 출력 : 2

 

get 메서드를 사용하여 키를 통해 해당 키에 연결된 값을 검색할 수 있다.

 

 

HashMap에서 값 제거(remove())

map.remove("One"); // 키-밸류 다 삭제한다

 

HashMap의 모든 값 순회(keySet())

for (String key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

keySet() 메서드를 사용하여 HashMap의 모든 키를 가져온다음, 각 키에 대해서 get() 메서드를 사용하여 값을 가져올 수 있습니다.

 

 

HashMap의 크기확인(size())

int size = map.size(); // HashMap에 저장된 키-값 쌍의 수 알아내기

 

 

HashMap이 특정 키를 포함하는지 확인(containskey())

if(map.containsKey("Two")) {
    System.out.println("HashMap contains key 'Two'");
}

containsKey() 메서드를 통해서 HashMap이 특정 키를 포함하고 있는지 확인할 수 있다.

 

 

HashMap이 특정 값을 포함하는지 확인(containsValue())

if(map.containsValue(3)) {
    System.out.println("HashMap contains value 3");
}

 

isEmpty()

boolean isEmpty = map.isEmpty(); // map이 아무것도 없으면 true를 반환

 

values()

Collection<Integer> values = map.values();

HashMap에 있는 모든 값을 컬렉션으로 반환

 

 

entrySet()

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

HashMap에 있는 모든 키-값 쌍을 Set 형태로 반환합니다. 이건 키와 값의 쌍을 동시에 순회하는데 유용합니다.

 

 

putAll()

HashMap<String, Integer> map1 = new HashMap<>();
HashMap<String, Integer> map2 = new HashMap<>();
map1.put("One", 1);
map1.put("Two", 2);
map2.putAll(map1); // map1 을 map2 로 전부 복사

한 HashMap의 모든 요소를 다른 HashMap에 복사합니다

 

 

clear()

map.clear(); // 모든 키 벨류 쌍을 제거