HashTable이란?
(Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 내부적으로 배열(bucket)을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 제공한다.
bucket 혹은 slot이란?
해시 테이블은 각각 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용하여 값을 저장하거나 검색한다. 이때, 실제값이 저장되는 장소를 bucket 혹은 slot이라고 한다.
해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수 1번만 수행하면 되므로 빠른 속도로 저장/삭제/조회가 가능하다.
따라서 해시테이블의 평균 시간복잡도는 O(1)이다.
Hash 함수
해시 함수는 크게 3가지가 있다.(1~3까지)
1. Division Method : (주소 = 입력값 % 테이블의 크기) 다음과 같이 입력값을 테이블의 크기로 나누어 계산하는 나눗셈을 이용하는 방법
2. Digit Folding : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법
3. Multiplication Method : 숫자로 된 Key값과 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 h(k)=(kAmod1)xm을 이용하는 방법
4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법
시간이 되면 해시 충돌과 분리 연결법, 개방 주소법도 조사하도록 하자
HashMap이란?
Map 인터페이스를 구현하고 있는 대표적인 클래스로 Key-Value쌍으로 구성되어있다.
Key와 Value에 Null값을 허용한다.
각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다.
HashMap을 사용하면 삽입, 검색에 시간복잡도 O(1)을 가지기 떄문에 List 대신 HashMap을 사용하여 성능을 높인다.
HashTable과 HashMap의 차이점
HashTable과 HashMap의 차이점은
- HashTable은 Key값에 Null을 허용하지 않지만, HashMap은 Key값에 Null을 허용한다.
- HashTable은 Thread-safe하지만, HashMap은 Thread-safe하지 않다. 따라서 멀티스레드 환경이라면 HashTable이 더 성능이 좋지만, 멀티스레드 환경이 아니라면 HashMap의 성능이 더 좋다. => 동기화 문제
HashTable은 동기화를 지원하지만 HashMap은 동기화를 지원하지 않는다. - HashMap은 보조해시를 사용하기 때문에 HashTable에 비해 해시 충돌이 덜 발생할 수 있다.
- HashTable은 Not Fail-Fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않는다.
Thread-safe란?
멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없음을 뜻한다.
하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 동시에 함께 실행되더라도 각 스레드의 함수의 결과가 올바르게 나오는 것으로 정의한다.
Fail-Fast Iterator란?
Fail-Fast는 Iterator를 이용한 순환 중 데이터가 변경되었을 때 즉시 ConcurrentModificationException 에러를 발생시킨다.
이와 반대로 Fail-Safe는 에러를 발생시키지 않는다.
Fail-Safe Iterator의 경우 실제 Collection의 복제본을 사용하기 때문에 에러를 발생시키지도 않고 Collection에 업데이트 된 데이터를 반환하지도 않는다.
HashSet이란?
Set 인터페이스에서 지원하는 구현 클래스로 Key의 중복을 허용하지 않고, Key값으로 Null을 허용하지 않는다.
또한, 순서 없이 Key로만 데이터를 저장하며 중복을 자동으로 제거해준다.
Set은 비선형구조여서 인덱스가 존재하지 않기 떄문에 값을 삽입 삭제 시 Set 내부에 있는지 검색 후 삽입 삭제 해야하기 때문에 속도가 느리다.
참고
