Hash Table
해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조이다. 단순하게 key-value로 이루어진 자료구조라고 생각하면 된다.
용어 헷갈려!
Hash, Hash Function
key를 해시함수라는 함수에 Input으로 넣어서 Ouput으로 나오는 것이 Hash(해시)라고 생각하면 되고, 이 Hash(해시)가 저장위치 즉, 배열의 index(인덱스)로 변환한다고 생각하면 된다.
Hash Function는 key를 hash(해시)로 만들어내는 함수이다.
구성
출처 : 위키백과-해시테이블
key
- 고유한 값, hash function의 Input이 된다.
- key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야한 공간도 따로 마련해야 하기 때문에(key의 길이가 제각각 일수 있다.), 고정된 길이의 해시로 변경한다.
hash function
- key를 고정된 길이의 hash로 변경해주는 역할을 한다.
- 서로 다른 key가 hashing 후 같은 hash값이 나오는 경우가 있다. 이를
해시충돌이라고 부른다. 해시 충돌 발생확률이 적을 수록 좋다. - 해시충돌이 균등하게 발생하도록 하는것도 중요하다. 모든 키가 같은 해시값이 나오게 되면 데이터 저장시 비효율성도 커지고 보안이 취약해져서 좋지 않다.
- 유명한 해쉬함수 SHA(Secure Hash Algorithm, 안전한 해쉬 알고리즘)
, SHA-256 등이 있다.
그외 해시함수들은 Division Method, Digit Folding, Multiplication Method, Univeral Hashing 등이 있다.
value
- 저장소(버킷,슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어진다.
hash table
- 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.
- 데이터가 저장되는 곳을
버킷,슬롯이라고 한다.
정리
해시는 색인 또는 인덱스, hash function은 key->hash로 만들어 주는 함수, 해시테이블은 hash를 주소로 삼아 데이터를 저장하는 자료구조이다.
Hash table의 장단점
장점
- 데이터 저장/읽기 속도가 빠르다. => 검색 속도가 빠르다.
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
- 충돌이 없다면 해쉬테이블은 시간복잡도 O(1)로 짧다!
단점
- 일반적으로 저장공간이 좀더 많이 필요하다.
- 여러 키에 해당하는 주소가 동일한 경우 충돌을 해결하기 위한 별도 자료구조가 필요함.
- 데이터 충돌이 발생한다면 Chaining에 연결된 리스트들까지 모두 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.
주요용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인 쉽기 때문)
Hash funtion
1. 나눗셈 법
- h(k) = k mod m
- 입력받은 key의 각 문자를 유니코드로 변환 후 HashMap의 size로 나눈 나머지 값으로 사용한다.
- m은 HashMap의 크기이며 소수를 사용한다. (2의 제곱수와 거리가 먼 소수)
2. 곱셈 법
- h(k) = (kA mod 1) * m
- k는 숫자로 된 키, 0 < A < 1
- m은 중요하지 않으며 보통 2의 제곱 수로 정한다.
- 나눗셈 법보다는 느리고 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해시함수이다.
3. Universal Hashing
- 다수의 해시 함수를 만들고 이 해시함수의 집합에서 무작위로 해시함수를 선택해 해시값을 만드는 기법
- 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키 값을 임의의 해시값에 매핑할 확률을 1/m으로 만드는 것이 목적이다.
4. MD5 (Message - Digest Algorithm)
- 임의의 길이의 값을 입력받아 128 비트의 고정 길이 해시값을 출력하는 알고리즘
- 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다.
- 단방향 암호화이기 때문에 해시값을 복호화는 할 수 없다.
5. SHA (Secure Hash Algorithm)
- 미국 국립표준기술연구소에서 표준으로 채택한 암호학적 해시 함수
- 해시 길이에 따라 SHA-256, SHA-384, SHA-512 비트를 선택해 사용할 수 있으며, 해시 길이가 길수록 안전하다
Hash Collision(해쉬충돌)
만약 A,B 두가지 key가 있다고 하자. A와 B를 hash function으로 해시 값을 얻었는데 hash값이 2로 똑같이 나왔다. 이런 현상을 해쉬 출동 이라고 한다.
해시 함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1로 매핑되어야 하는 해시 테이블의 특성에 위배된다.
통계적으로 해시 테이블의 공간 사용률이 70% ~ 80%정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.
출처: https://mangkyu.tistory.com/102 [MangKyu's Diary]
해쉬충돌의 문제점을 정리하자면,
1) Hashing을 해서 삽입하려 했으나 이미 다른 원소가 자리를 차지하고 있는 상황
2) 충돌은 해싱의 검색 속도를 떨어뜨리게 하여 버킷의 크기를 넘어 저장하게 되어 오버플로우가 발생할 수 있다
Hash collision 해결 알고리즘
1) Separate Chaining 기법(폐쇄형) : 각 인덱스에 할당된 것이 값이 아니라 키와 값을 가진 LinkedList(연결리스트)로 추가적인 공간을 활용하는 것
Sandra가 들어가는데 충돌이 일어나니 기존에 있던 John의 값에 연결시켰다.
체이닝(Chaining)은 자료 저장 시, 저장소(bucket)에서 충돌이 일어나면 해당 값을 기존 값과 연결시키는 기법이다.
위의 사진에서 Sandra를 저장할 때 충돌이 일어났고, 기존에 있던 John에 연결시켰다. 이 때 연결리스트(Linked List) 자료구조를 이용한다. 해쉬충돌이 일어날 때 다음에 저장된 자료를 기존의 자료 다음에 위치시키는 것이다.
Separate Chaining 장단점
장점 :
1) 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
2) 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.
3) 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.
단점 :
1) 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율이 낮아질 수 있다.
2) 외부 저장 공간을 사용한다.
3) 외부 저장 공간 작업을 추가로 해야 한다.
2) Open Addressing 기법(개방형) : 충돌 발생시, 인접한 다른 비어있는 해시 버킷을 찾아 삽입하는 방법
Open Addressing(개방주소법)에서의 해시테이블은 1개의 해시와 1개의 값(value)가 매칭되어 있는 형태로 유지된다.
위의 그림을 보면, Sandra가 저장될때 해시가 John으로 채워져 있어서 그 다음 Hash에 Sandra를 저장했다. 그리고 Ted의 해시도 Sandra가 저장되어 있으므로 그 다음 해시에 Ted를 저장했다. 이처럼 비어있는 해시를 찾아 저장하는 방법을 Open Addressing라고 한다.
이 때, 비어있는 해시(Hash)를 찾는 과정은 동일해야 한다.(일정한 규칙을 따라 찾아가야 한다.)
i: index
- 선형 탐색(Linear Probing):
고정폭으로 이동 : 다음 해시(+1)나 i개(+i)를 건너뛰어 비어있는 버킷에 데이터를 저장한다.단, 군집현상이 일어나기 쉬워! - 제곱 탐색(Quadratic Probing):
제곱수로 이동 : 충돌이 일어난 해시에서 제곱(+i^2)나 ((i+1)^2)을 한 비어있는 곳의 버킷에 데이터를 저장한다.
자세한 내용은 이블로그에서. 이 블로그
Open Addressing의 장단점
장점 :
1) 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
2) 또 다른 저장공간에서의 추가적인 작업이 없다.
단점 :
1) 해시 함수(Hash Function)의 성능에 전체 해시테이블의 성능이 좌지우지된다.
2) 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.
자바에서 사용하는 Hash
HashTable이란 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java2에서 처음 선보인 Java Collections Framework에 속한 API이다.
HashTable 또한 Map 인터페이스를 구현하고 있기때문에 HashMap과 HashTable이 제공하는 기능은 같다.
차이점(HashMap vs HashTable)
- 보조 해시 함수
HashMap은 보조 해시함수를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충동(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다. - 동기화
HashMap의 경우 동기화를 지원하지 않는다.그래서 Hash Table은 동기화 처리라는 비용때문에 HashMap에 비해 더 느리다고 한다. 프로그래밍상의 편의성 때문에 멀티쓰레드 환경에서도 HashTable을 쓰기보다는 HashMap을 다시 감싸서Map m == Collections.syschronizedMap(new HashpMap());과 같은 형태가 더 선호된다.
HashMap
- HashMap의 작동 방식?
HashMap의 내부는 배열로 이루어져 있다. HashMap은 Key-Value 형식이기 때문에, Key는 배열의 인덱스가 되고, 이 배열은 해시 버킷이다.
먼저 key값을 hashcode()라는 메소드를 통해 int형의 해쉬값으로 바꾸고 이를 버킷의 사이즈인 M으로 나눈 나머지가 해시 버킷의 진짜 인덱스가 된다.
int index = hashcode() % M;
HashMap에서 사용하는 충돌기법 방식은 Seaparate Chaining 이다. Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데 HashMap에서 remove()메서드는 비번하게 호출될 수 있기 때문이다.
게다가 HashMap에 저자된 key-value 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing은 버킷의 밀도가 높아질수록 Worst Case 빈도가 높아지지만, Chaining은 해시 출동이 잘 발생하지 않도록 조정하면 Worst Case를 줄일 수 있다.
자바 8부터는 Seperate Chaining에서 데이터 개수가 많아지면 LinkedList대신 Tree(red black tree)를 사용해 성능적으로 더 좋아지게 하였다.
즉, 처음에는 해시 버킷을 LinkedList로 하고 8개 이상의 키-값 쌍이 모이면 LinkedList(O(N))를 Tree(O(logN))구조로 바꾼다. 만약 데이터가 삭제되어 버킷이 6개에 이르게 되면 다시 LinkedList 구조로 변경한다.
HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 수를 두배로 늘린다. 해시 버킷의 수를 늘려서 해시 충돌의 확률을 줄이는 것이다.
hashMap의 시간복잡도
- 일반적으로 충돌을 최소화하도록 잘 구현된 경우 :
O(1) - 충돌이 자주 발생하는 경우(최악의 경우) :
O(N) - 균형 이진 탐색 트리를 사용한 경우 :
O(logN)
-> 이 방법은 배열의 크기를 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용하고, 키의 집합을 특정 순서로 차례대로 접근할 수 있다.
참고
