[자료구조] Hash, HashMap, HashTable

김의진·2022년 2월 8일
5

1. Hash란?

해시(Hash)란 단방향 암호화 기법인 해시함수(HashFunction)을 이용하여 생성된 고정된 길이의 비트열을 의미한다.
(단방향 암호화 기법은 암호화는 수행하지만 복호화는 불가능한 암호화 기법이다.)

해시를 만들기 위해서는 해시 함수가 필요한데 해시 함수는 입력된 임의의 데이터를 고정된 길이의 데이터 변경하여 출력해준다.

변경전 원래 데이터 값을 키(key), 변경 후 데이터의 값을 해시값(Hash value), 키(key)와 값(value)로 변환되는 과정을 해싱(Hashing)이라고 한다.

변환이 이루어진 후 변환된 값이 중복되는 경우가 발생할 수 있는데 이를 '해시충돌(Hash Collision)' 이라고 한다.
해시 충돌을 해결할 수 있는 방법에는 대표적으로 체이닝(Chaining), 개방 주소법(Open Addressing)이 있다.

2. HashTable, HashMap이란?

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(Index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시 테이블(Hash Table) 혹은 해시맵(Hash Map) [자바에서는 두 자료구조가 다름]이라고 한다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다.

3. Java에서 HashMap, HashTable의 차이

자바에서 Hashmap과 HashTable의 가장 큰 차이는 Thread-safe이다. Hashtable의 모든 Data 변경 메소드는 syncronized로 선언되어 있다. 즉 메소드 호출 전 스레드간 동기화 락을 통해 멀티 쓰레드 환경에서 data의 무결성을 보장해준다.
하지만 HashMap의 경우 Thread-safe하지 않기 때문에 멀티 스레드 환경에서 동시에 객체의 data를 조작하는 경우 data가 깨질 수 있다.

아래는 HashTable의 get 메서드

아래는 HashMap의 get 메서드

두 자료구조의 메서드를 보면 ynchronized의 차이를 확인할 수 있다.
다만 HashMap이 동기화를 지원하지 않는다하여 HashTable을 쓰는 것보다는 동기화가 필요하다면 ConcurrentHashMap을 사용하는 것이 더 좋은 방법이다. 이유는 HashTable은 Collection Framework이 나오기 이전부터 존재한 구형버전이기때문에 HashMap에 비해 느리다고 한다.

이외의 차이로 HashMap은 key에 null을 허용하지만 HashTable의 경우 key에 null을 허용하지 않는다.

https://hee96-story.tistory.com/48

profile
3년차 Spring, Java 주니어 백엔드 개발자입니다.

0개의 댓글