Hash Table 과 Hash Map

💻 computer science/🧐 data structure 2022. 12. 4. 14:57

📍 Hash, Hash Function

해시(Hash)

데이터를 다루는 기법 중 하나

해시 함수

데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

해시 함수 특징

같은 입력값에 대해서 같은 출력값이 보장된다.
서로 다른 입력값으로부터 동일한 출력값이 나올 가능성이 희박하므로 입력값에 대한 무결성이 보장된다.
일방향성을 갖는다.

📌 해시 테이블 (Hash Table)

키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조

즉, 키와 배열의 인덱스(index)를 이용하여 키를 저장하는 자료구조

해시 테이블은 해시 함수(hash function)으로 계산하여 그 값을 배열의 인덱스로 사용한다.

해시 함수로 의해 반환된 데이터의 고유 숫자 값을 해시 값 또는 해시 코드라고 한다.

⇒ key 값을 해시 함수를 통해 배열의 인덱스로 바꾸고 그 자리에 데이터를 저장한다.

💡 과정

원래 데이터의 값(key) → Hash Function → Hash Function의 결과 = Hash Code
→ Hash Code를 배열의 index로 사용 → 해당하는 Index에 data 넣기

⚠️ 인덱스 값이 중복될 수 있다 ⇒ 충돌(collision)

장점

적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
배열의 인덱스를 사용해 검색, 삽입, 삭제가 빠르다. (평균 시간복잡도 O(1))
- ❓ 삽입 삭제는 왜 O(1) ??
  - 인덱스는 데이터만의 고유한 위치이다.
  - 따라서 삽입이나 삭제를 한다해도 다른 데이터로 채울 필요가 없다.
  - 삽입이나 삭제시 데이터를 이동할 필요가 없기 때문
키와 해시 값이 연관성이 없어 보안에 많이 사용된다.
데이터 캐싱에 많이 사용된다.
- get, put 에서 캐시 로직을 추가하면 자주 hit 하는 데이터를 바로 찾을 수 있다.

단점

충돌
공간 복잡도가 커진다.
순서가 있는 배열에는 어울리지 않는다.
해시 함수 의존도가 높다.

⚡ 해시 충돌(Collision)

서로 다른 문자열이 Hash function을 통해 Hash 한 결과가 같은 경우(중복되는 경우)

해시 함수가 서로 다른 두 개의 입력값에 대해 같은 출력값을 내는 상황
충돌을 줄여주는 해시 함수를 사용하는 것이 좋다.
충돌이 많아질 수록 탐색의 시간 복잡도가 O(1) → O(n)에 가까워진다.

해결방법

Chaining
Open addressing

Chaining

같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트로 연결하여 관리한다.

원소를 검색할 때는 해당 연결리스트의 원소들을 차례로 지나가면서 탐색한다.

이 방법은 JDK 내부에서도 사용하고 있는 충돌 처리 방식이다.

Linked List와 Red-Black Tree를 사용한다.

data가 6개 이하이면 Linked list 사용
data가 8개 이상이면 tree 사용

왜 6과 8으로 2 이상의 차이를 두나❓

차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제 되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문

단점

hash table을 사용시 기존의 저장된 값들과 비교하는 과정없이 바로 해시 함수를 통해서 해시 값을 통해 접근 가능한 것이 장점이였지만 체인이 길어진다면 모든 체인에 대한 원소들을 비교해야 한다.

Open addressing

체이닝과 달리 어떻게든 주어진 테이블 공간에서 해결한다.

모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다.

비어있는 버킷을 찾아간다.

비어있는 버킷을 어떤식으로 찾아가는지에 따른 여러가지 방법이 존재한다.

Linear probing
Quadratic probing
Double hashing

Linear probing (선형 조사)

가장 간단한 충돌 해결 방법
충돌이 일어난 자리에서 바로 다음 자리를 본다.
순차적으로 증가하면서 빈 버킷을 찾는다.
테이블의 경계를 넘어간 경우 맨 앞으로 돌아간다.

Quadratic probing (이차원 조사)

바로 뒷자리를 보는 것이 아닌 보폭을 2차 함수로 넓혀가면서 본다
특정 영역에 원소가 몰려도 그 영역을 빠르게 벗어날 수 있다.

Double hashing

두 개의 함수를 사용
하나의 함수는 최초의 해시값을 얻을 때만 사용
다른 하나의 함수는 해시 충돌이 일어났을 때 이동할 폭을 얻을 때 사용
첫 번째 해시값이 같더라도 두 번째 해시값까지 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.

vs 해시 맵 (Hash Map)

Hashtable : JDK 1.0 부터 있던 Java의 API

HashMap : Java 2에서 선보인 Java Collections Framework에 속한 API

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

Key에 대한 해시값을 사용해 값을 저장하고 조회하는 것은 동일하다.

해시 테이블	해시 맵
병렬 처리를 할 때 사용(동기화를 고려)	병렬 처리를 하지 않을 때 사용(동기화를 고려하지 않음)
NULL 값 허용하지 않는다.	NULL 값을 허용

Hashtable은 Thread-safe 하고 HashMap은 Thread-safe 하지 않다.

Hashtable의 모든 data 변경 메소드는 syncronized로 선언되어 있다.
- 메소드 호출 전 스레드간 동기화 락을 통해 멀티 스레드 환경에서 data의 무결성을 보장
멀티 스레드 환경이 아니라면 Hashtable은 HashMap보다 성능이 떨어진다.

HashMap은 보조 해시를 사용해 보조 해시 함수를 사용하지 않는 Hashtable에 비해 해시 충돌이 덜 발생할 수 있다.

상대적으로 성능상 이점이 있다.

❗ ConcurrentHashMap

Hashtable 클래스보다는 빠르고 Multi-thread 환경에서 쓸 클래스???

→ ConcurrentHashMap

Hashtable 클래스의 단점을 보완하면서 Multi-thread 환경에서 사용할 수 있도록 나온 클래스
HashMap, Hashtable, ConcurrentHashMap 클래스 모두 Map의 기능적으로만 보면 큰 차이는 없습니다.

특징

Hashtable과 다르게 synchronized 키워드가 메소드 전체에 존재하는 것을 볼 수 있다.
- get() 메소드에는 synchroinzed 가 존재하지 ❌
- put() 메소드에는 중간에 synchroinzed 키워드가 존재
읽기 작업에는 여러 스레드가 동시에 읽을 수 있다.
쓰기 작업에는 특정 세그먼트 or 버킷에 대한 lock을 사용한다.