Hash & Hash Table

문지원(JiwonMoon)·2022년 6월 15일
0
post-thumbnail

🤔 목적

컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.

해시(Hash)란?

해시는 데이터를 다루는 기법 중의 하나로, 검색과 저장을 빠르게 하는 자료구조이다.
데이터를 저장할 때 Key-Value 형태로 데이터가 존재하고, Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어나게 된다.

해시의 학습에서는 크게 해시 함수(hash function), 해싱(hashing), 해시 테이블(hash table)이렇게 3가지로 파트 나뉘어 진다.

해시 함수(hash function)란?

해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다.

즉, 해시 함수는 Key값을 고정된 길이의 hash로 변환하는 역할을 한다.

해싱(hashing)이란?

해시 함수에서 Key값을 hash로 변환하는 과정을 해싱(hashing)이라고 한다.
해시 함수에서는 Key값을 해싱 과정을 통해 해시 값(hash value) 또는 해시코드(hash code)으로 변경하며, 이 해시 값이 저장 위치가 된다고 생각하면 된다.

서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

해시 테이블(hash table)이란?

해시 테이블은 연관 배열구조를 이용하여 데이터를 Key와 Value로 저장하는 자료구조이다.
해시 테이블은 해시 함수를 사용하여 인덱스를 버킷이나 슬롯의 배열로 계산한다.

연관 배열구조?
연관 배열은 자료구조의 하나로, 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있다.

연관 배열은 일반적으로 다음의 명령을 지원한다.

  • 키와 값이 주어졌을 때, 연관 배열에 그 두 값을 저장하는 명령
  • 키가 주어졌을 때, 연관되는 값을 얻는 명령
  • 키와 새로운 값이 주어졌을 때, 원래 키에 연관된 값을 새로운 값으로 교체하는 명령
  • 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 명령

장점 & 단점

장점

  • 중복을 제거할 수 있다.
  • 데이터 캐싱, 보안에 주로 사용된다.
  • 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠르다.

단점

  • 공간 복잡도가 커진다.
  • 충돌이 발생할 수 있다
    • 충돌이 발생할 경우 시간 복잡도는 O(n)에 가까워 진다.
  • 순서가 있는 배열에는 어울리지 않는다.

해시 테이블(Hash Table) vs 해시 맵(Hash Map)

해시맵에 대해 포스트 한 적이 있지만 해시 테이블과 비교하여 작성해볼 예정이다.
해시 맵에 자세한사항은 여기 를 참고하면 된다.

Java에서 HashTable과 HashMap의 차이는 동기화 지원 여부이다. 키(Key)에 대한 해시(Hash)값을 사용하여 값을 저장, 조회 하는 것은 동일하다.

  • 해시 테이블(Hash Table)
    • 병렬 처리를 할 때 (동기화를 고려해야하는 상황)
    • Null 값을 허용하지 않는다.
  • 해시 맵(Hash Map)
    • 병렬 처리를 하지 않을 때 (동기화를 고려하지 않는 상황)
    • Null 값을 허용한다.

즉, 대표적으로 두가지 차이점이 존재하는데 첫번째는 동기화이슈, 두번째는 반환값이슈로 보면 된다.

HashMap 사용법

1. put

key와 value가 String 형태인 HashMap을 만들고,
put을 사용해서 값을 부여한다

HashMap<String, String> map = new HashMap<>(); // 생성

// map.put(String, String);
// map.put(key, value);
map.put("people", "사람"); 
map.put("baseball", "야구");

2. get

key에 해당되는 value값을 얻기 위해 사용한다.

System.out.println(map.get("people"));  // "사람" 출력
System.out.println(map.getOrDefault("people", "자바"));  // getOrDefault을 사용하면 Null 값 제외하고 출력 

3. containsKey

containsKey 메소드는 맵(Map)에 해당 키(key)가 있는지를 조사하여 그 결과값을 리턴한다.

System.out.println(map.containsKey("people"));  // true 출력

4. remove

remove 메소드는 맵(Map)의 항목을 삭제하는 메소드로 key값에 해당되는 아이템(key, value)을 삭제한 후 그 value 값을 리턴한다.

System.out.println(map.remove("people"));  // "사람" 출력

5. size

size 메소드는 Map의 갯수

System.out.println(map.size());  // 1 출력

6. keySet

Map의 모든 Key를 모아서 Set 자료형으로 리턴한다.

List<String> keyList = new ArrayList<>(map.keySet());

References (참고 자료)

0개의 댓글