[자료구조] 해싱

N = int(input())
hash = dict()
for line in range(N):
    directives = list(input().split())
    cmd = directives[0]
    if cmd == 'add':
        add_key = directives[1]
        add_value = directives[2]
        # hash.setdefault(directives[1], directives[2])
        hash[add_key] = add_value
    elif cmd == 'remove':
        remove_key = directives[1]
        hash.pop(remove_key)
    elif cmd == 'find':
        find_key = directives[1]
        find_value = hash.get(find_key)
        if find_value != None:
            print(find_value)
        else:
            print(None)

 

- 해시 함수 : 임의의 데이터를 받아, 해당 데이터를 고정된 길이의 특정 값으로 반환하는 함수

=> 어떤 값을 넣더라도 특정 범위에 해당하는 값을 반환함

 

- 만약 해시 함수의 반환값을 0부터 시작하는 양의 정수가 되도록 함수를 조절한다면, 특정 값을 배열에 넣기 위해선 해시 함수에 그 값을 넣고, 반환하는 값에 해당하는 인덱스에 그 값을 넣어주는 방법을 사용

 

- 삭제, 삽입, 검색 모두 해시 함수를 한 번 만 통과하여 나온 인덱스만 관리 : O(1)

-  사용할 수 없는 경우

1) 각 타입 (문자열, 숫자 등등) 에 맞는 해시 함수를 사용하여 해시 값으로 바꾸는데,

대응할 수 없는 타입도 있음. 대표적인 예시로 배열이 있습니다. 배열 내 값의 갯수가 불분명하므로

해시 함수에선 배열 같은 타입은 다루지 않음.

2) 특정 데이터가 들어온 순서 상관 없이 삽입, 삭제, 검색이 자주 발생하는 경우에 사용하기 좋음.

배열의 장점 : index 기반으로 담고 있는 데이터 간의 순서가 확실하게 매겨져 있음. 순서 상관 없이 

각각의 데이터가 자주 들어오고 나가는 경우에 해싱이 꼭 필요하다 !

 

Java 의 HashMap

- 해싱을 기반으로 데이터들을 관리해주는 자료 구조.

- HashMap 은 (key, value) 쌍 형태로 들어가 있어, key 와 그 key 에 따른 value 값을 동시에 저장.

- HashMap 의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)

- HashMap 은 TreeMap 보다 속도가 빠르지만, 값 자체에만 관심이 있지 그 순서에는 관심 X

import java.util.HashMap;

HashMap<K, V> name = new HashMap<>();

HashMap을 이용할 때 자주 사용되는 것은 다음 3가지 입니다. HashMap<Integer, Integer> m;로 선언되어 사용될 때를 예로 설명해보겠습니다.

1. m.put(K, V)

HashMap에 쌍(K, V)를 추가합니다.

1. m.remove(K)

현재 HashMap에 들어있는 데이터 중 key가 K인 쌍을 찾아 제거합니다.

1. m.get(K)

현재 hashmap에 key가 K인 쌍을 찾아 값 V를 반환합니다. 해당하는 쌍이 없다면 에러가 발생하기 때문에 미리 m.containsKey(K)를 확인하여 true인 경우에만 m.get(K)를 사용하셔야 합니다.

이런 문제를 한번에 해결하기 위해서는 m.getOrDefault(K, D) 함수를 사용하시면 됩니다. K에 해당하는 key가 없을 시에는 값 D를 기본으로 반환해줍니다.

Side Note

만약 key를 문자열로 하는 경우는 어떨까요?
마치 배열 index가 문자열이 된 것 처럼 사용할 수 있게 됩니다! HashMap<String, Integer> 타입으로 선언하면 사용이 가능합니다.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, Integer> m = new HashMap<>();
        m.put("banana", 6);
        m.put("helloworld", 2);
        m.put("apple", 5);

        System.out.println(m.get("banana")); // key가 banana인 쌍의 value 출력 (6)
    }
}

 

Python  의 dictionary

Python에서는 dict라는 class가 있습니다. dict는 HashMap 자료구조로 되어있으며, HashMap의 경우 해싱을 기반으로 데이터들을 관리해주는 자료구조 입니다. HashMap은 (key, value) 쌍 형태로 들어가 있어, key와 그 key에 따른 value 값을 동시에 저장하는 형태입니다. 따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(1)입니다. HashMap은 빠르지만, 구조 특성상 들어온 값들간의 순서를 나타내주지 못합니다.

다만 여기서도 key로 가능한 type은 immutable한 값들 뿐입니다. 즉, list와 같이 mutable한 type은 가변적이므로 절대 dict의 key가 될 수 없습니다.

d3와 같이 {}안에 key:value형태로 미리 (key, value) 쌍을 초기값으로 넣어줄 수 있습니다.
다만 여기서도 key로 가능한 type은 immutable한 값들 뿐입니다. 즉, list와 같이 mutable한 type은 가변적이므로 절대 dict의 key가 될 수 없습니다.

dict를 이용할 때 자주 사용되는 것은 다음 3가지 입니다. d = dict()를 가정하고 살펴보겠습니다.

1. d[K] = V

hashmap에 쌍(K, V)를 추가합니다.

1. d.pop(K)

현재 hashmap에 들어있는 데이터 중 key가 K인 쌍을 찾아 제거합니다.

1. K in d

현재 hashmap에 key가 K인 쌍이 있는지를 확인합니다. 있다면 True, 아니라면 False를 반환합니다. 마찬가지 이유로 K not in d라는 구문 역시 사용 가능합니다.

 

 

# hashmap