[자료구조] Java - 해시테이블(HashTable) 이론정리

해싱(Hashing)이란?

해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.

 

---

해시테이블(HashTable)이란?

해시 테이블은 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

 

이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다.

 

---

Java의 HashMap(해시맵)과 HashTable(해시테이블) 차이

Java에서 HashTable과 HashMap의 차이는 동기화 지원 여부에 있다.

병렬 프로그래밍을 할때 동기화를 지원해준다는 것을 의미하는 Synnchronized 키워드가 해시테이블의 메서드에는 붙어있는데, 이것은 해당 함수를 처리하는 시간이 조금 지연됨을 의미한다.

 

따라서 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하고, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.

 

 

 

📗참고사이트

[DS] 해쉬 테이블(Hash Table)이란?

 

[자료구조] 해시테이블(HashTable)이란?