hash 는 내부적으로 배열을 사용해 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
데이터를 검색할 때 사용할 key 와 실제 데이터 값 value 이 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환된다.
특정한 값을 검색하는데 데이터 고유의 인덱스로 접근하게 되므로 평균적으로 O(1) 의 시간복잡도를 갖는다.
(항상 O(1)은 아니고 평균적으로 O(1)이다. 항상 O(1)이 아닌 이유는 충돌 때문이다.)
하지만 문제는 인덱스로 저장되는 key 값이 불규칙하다는 것이다.
그래서 특별한 알고리즘을 이용해 저장할 데이터와 연관된 고유한 숫자를 만들어 내고 이를 key 로 이용한다.
특정 데이터가 저장되는 인덱스는 해당 데이터만의 고유한 위치이기 때문에, 데이터를 삽입할 때 다른 데이터의 사이에 저장되거나, 삭제 시 다른 데이터로 채울 필요가 없어 추가적인 연산 비용이 없도록 만들어졌다.
Hash Function
데이터의 value 를 배열의 인덱스인 key 로 변환하기 위해 일련의 과정이 필요한데, 이 과정에서 사용하는 함수/메소드를 hash method 또는 hash function 이라고 한다.
이 메소드에 의해 반환된 데이터의 고유한 key값을 hashcode 라고 한다.
저장되는 value 값을 해시 함수를 통해 정수형의 값들로 바꿔준다.
충분히 확인되지 않은 어설픈 해시 함수를 사용해 key 값들을 결정한다면 동일한 값이 도출될 수 있다.
이렇게 되면 동일한 key 값에 복수개의 데이터가 하나의 해시 배열에 존재할 수 있게 되는 것인데 이를 충돌(Collision) 이라고 한다.
즉, 충돌은 서로 다른 두 개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 되는 것을 말한다.
✅ hash function 의 조건
일반적으로 좋은 해시 함수는 key 의 일부분을 참조해 해시값을 만들지 않고 키 전체를 참조해 해시 값을 만들어 낸다.
하지만 좋은 해시 함수는 key 가 어떤 특성을 가지고 있느냐에 따라 달라진다.
해시 함수를 무조건 1:1로 만드는 것보다 충돌을 최소화하는 방향으로 설계하고, 발생하는 충돌에 대비해서 어떻게 대응할 것인가가 더 중요하다.
1:1 대응이도록 만드는 것이 거의 불가능하기도 하고 그런 해시 함수를 만든다면 보통의 배열과 다를바 없고 메모리를 너무 차지하게 된다.
충돌이 많아질수록 검색에 필요한 시간복잡도가 O(1)에서 O(N)에 가까워진다.
어설픈 해시 함수는 해시를 해시답게 사용하지 못하도록 한다.
좋은 해시 함수를 선택하는 것은 hash table 의 성능 향상에 필수적인 것이다.
따라서 hashing된 인덱스에 이미 다른 값이 들어 있다면 새 데이터를 저장할 다른 위치를 찾은 뒤에 저장할 수 있는 것이다.
따라서 충돌 해결은 필수이다.
Resolve Conflict
Open Address 방식 (개방주소법)해시 충돌이 발생하면(삽입하려는 해시 버킷이 이미 사용 중이라면), 다른 해시 버킷에 해당 자료를 삽입하는 방식이다.
버킷 : 바구니. 데이터를 저장하기 위한 공간
개방주소법 알고리즘은 충돌이 발생하면 데이터를 저장할 장소를 찾는다.
Worst Case 의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아올 수 있다.
이 과정에서도 여러 방법들이 존재하는데, 일반적으로 다음 세 방법으로 처리된다.
Linear Probing : 순차적으로 탐색하여 비어있는 버킷을 찾을 때까지 계속 진행된다.
Quadratic Probing : key값을 제곱하여 비어있는 버킷을 찾는다.
Double Hashing Probing : 하나의 해시 함수에서 충돌이 발생하면 2차 해시 함수를 이용해 새로운 주소를 할당한다. 위의 두 방법에 비해 많은 연산량이 발생한다.
Separate Chaining 방식 (분리연결법)
일반적으로 개방주소법은 분리연결법보다 느리다.
개방주소법은 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높아진다.
반면 분리연결법은 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워지는 빈도를 줄일 수 있다.
→ Java7에서는 분리연결법을 사용해 HashMap 을 구현하고 있다.
✅ 보조 해시 함수
보조 해시 함수 supplement hash function 의 목적은 key 의 해시 값을 변형해 해시 충돌 가능성을 줄이는 것이다.
분리연결법 방식을 사용할 때 함께 사용되며 보조 해시 함수로 Worst Case 에 가까워지는 경우를 줄일 수 있다.
분리연결법은 두가지 구현 방식이 존재한다.
Linked List 를 사용각각의 버킷들을 연결 리스트로 만들어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식이다.
연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다.
또한 버킷을 계속해서 사용하는 개방주소법 방식에 비해 테이블 확장을 늦출 수 있다.
하지만 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다는 단점이 있다.
Tree 를 사용
기본적인 알고리즘은 분리연결법 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다.
연결 리스트를 사용할지 트리를 사용할지에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다.
트리는 기본적으로 메모리 사용량이 많기 때문에 데이터의 개수가 적다면 연결 리스트를 사용하는 것이 맞다.
데이터 개수가 적을 때의 Worst Case 는 트리와 연결 리스트의 성능 상 차이가 거의 없다.
따라서 메모리 측면에서는 트리보다 연결 리스트가 유리하다.
✅ 데이터가 적다는 것은?어떤 자료구조를 해시 테이블에 사용할지에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다.
이 key-value 쌍의 개수가 6개, 8개를 기준으로 결정한다.
연결 리스트의 기준과 트리의 기준을 6과 8로 결정한 것은 변경하는데 소요되는 비용을 줄이기 위함이다.
예시로, 기준을 6과 7로 설정한 경우에서 어떤 해시 버킷에 6개의 key-value 쌍이 들어있다.
그리고 하나의 값이 추가되어서 7개가 된다면 자료구조를 연결 리스트에서 트리로 변경해야 한다.
그 이후에 바로 하나의 값이 삭제된다면 다시 트리에서 연결 리스트로 자료구조를 변경해야 한다.
각 자료구조로 넘어가는 기준 차이가 1이라면 자료구조를 Switching 하는 데 사용되는 비용이 많이 필요하게 되는 것이다.
그래서 2라는 여유를 남기고 기준을 잡은 것이다.
따라서 데이터의 개수가 6개에서 7개로 증가했을 때는 연결 리스트의 자료구조일 것이고, 8개에서 7로 감소했을 때는 트리의 자료구조일 것이다.
Open Address vs Separate Chaining
두 방식 모두 Worst Case 에서 O(N) 이다.
하지만 개방주소법은 연속된 공간에 데이터를 저장하기 때문에 분리연결법에 비해 캐시 효율이 높다.
따라서 데이터의 개수가 충분히 적다면 개방주소법이 분리연결법보다 더 성능이 좋다.
한 가지 차이점은 분리연결법에 비해 개방주소법이 버킷을 계속 사용한다는 것이다.
따라서 분리연결법으로 테이블의 확장을 보다 늦출 수 있다.
해시 버킷의 동적 확장 (Resize)
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다.
그래서 HashMap 은 key-value 쌍 데이터의 개수가 일정 개수 이상이 된다면 해시 버킷의 개수를 두 배로 늘린다.
이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
해시 버킷 크기를 두 배로 확장하는 임계점인 '일정 개수 이상' 이란, 데이터의 개수가 해시 버킷의 개수의 75%가 될 때이다.
0.75 는 load factor 라고도 불린다.
추가
개방 주소법 - Double Hashing Probing
개방 주소법에서 해시 충돌이 발생한다면, 다른 해시 함수를 사용해서 새로운 해시를 할당 받는다.
여기서 새로운 해시를 할당 받는 다른 해시 함수를 보조 해시 함수라고도 부른다.
분리 연결법 - 보조 해시 함수
기본적인 개념은 충돌이 발생할 경우 비어있는 버킷을 찾아서 저장하지 않고, 버킷에 데이터를 추가하는 방법이다.
처음 해시 키값을 연산할 때, 보조적인 해시 함수를 사용할 수도 있다. 즉, 필수적으로 사용되는 것은 아님.
두 부분의 차이점이라고 한다면, 더블 해싱은 개방주소법에서 해시 충돌 시 사용되는 검색 방법 중 하나이며, 해시 충돌이 발생했을 경우 보조 해시 함수로 다른 해시코드를 생성한다.
분리 연결법은 보조 해시 함수를 사용해 해시 키값을 계산할 수도 있고, 아닐 수도 있다.
khyunjiee
commented
3 years ago
해시
Hash Table
hash는 내부적으로 배열을 사용해 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 데이터를 검색할 때 사용할key와 실제 데이터 값value이 한 쌍으로 존재하고,key값이 배열의 인덱스로 변환된다. 특정한 값을 검색하는데 데이터 고유의 인덱스로 접근하게 되므로 평균적으로 O(1) 의 시간복잡도를 갖는다. (항상 O(1)은 아니고 평균적으로 O(1)이다. 항상 O(1)이 아닌 이유는 충돌 때문이다.) 하지만 문제는 인덱스로 저장되는key값이 불규칙하다는 것이다.그래서 특별한 알고리즘을 이용해 저장할 데이터와 연관된 고유한 숫자를 만들어 내고 이를
key로 이용한다. 특정 데이터가 저장되는 인덱스는 해당 데이터만의 고유한 위치이기 때문에, 데이터를 삽입할 때 다른 데이터의 사이에 저장되거나, 삭제 시 다른 데이터로 채울 필요가 없어 추가적인 연산 비용이 없도록 만들어졌다.Hash Function
데이터의
value를 배열의 인덱스인key로 변환하기 위해 일련의 과정이 필요한데, 이 과정에서 사용하는 함수/메소드를hash method또는hash function이라고 한다. 이 메소드에 의해 반환된 데이터의 고유한 key값을hashcode라고 한다. 저장되는value값을 해시 함수를 통해 정수형의 값들로 바꿔준다.충분히 확인되지 않은 어설픈 해시 함수를 사용해
key값들을 결정한다면 동일한 값이 도출될 수 있다. 이렇게 되면 동일한key값에 복수개의 데이터가 하나의 해시 배열에 존재할 수 있게 되는 것인데 이를충돌(Collision)이라고 한다. 즉, 충돌은 서로 다른 두 개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 되는 것을 말한다.✅
hash function의 조건 일반적으로 좋은 해시 함수는key의 일부분을 참조해 해시값을 만들지 않고 키 전체를 참조해 해시 값을 만들어 낸다. 하지만 좋은 해시 함수는key가 어떤 특성을 가지고 있느냐에 따라 달라진다.해시 함수를 무조건 1:1로 만드는 것보다 충돌을 최소화하는 방향으로 설계하고, 발생하는 충돌에 대비해서 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이도록 만드는 것이 거의 불가능하기도 하고 그런 해시 함수를 만든다면 보통의 배열과 다를바 없고 메모리를 너무 차지하게 된다.
충돌이 많아질수록 검색에 필요한 시간복잡도가 O(1)에서 O(N)에 가까워진다. 어설픈 해시 함수는 해시를 해시답게 사용하지 못하도록 한다. 좋은 해시 함수를 선택하는 것은
hash table의 성능 향상에 필수적인 것이다. 따라서 hashing된 인덱스에 이미 다른 값이 들어 있다면 새 데이터를 저장할 다른 위치를 찾은 뒤에 저장할 수 있는 것이다. 따라서 충돌 해결은 필수이다.Resolve Conflict
Open Address 방식 (개방주소법) 해시 충돌이 발생하면(삽입하려는 해시 버킷이 이미 사용 중이라면), 다른 해시 버킷에 해당 자료를 삽입하는 방식이다. 버킷 : 바구니. 데이터를 저장하기 위한 공간
개방주소법 알고리즘은 충돌이 발생하면 데이터를 저장할 장소를 찾는다.
Worst Case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아올 수 있다. 이 과정에서도 여러 방법들이 존재하는데, 일반적으로 다음 세 방법으로 처리된다.Separate Chaining 방식 (분리연결법) 일반적으로 개방주소법은 분리연결법보다 느리다. 개방주소법은 해시 버킷을 채운 밀도가 높아질수록
Worst Case발생 빈도가 높아진다. 반면 분리연결법은 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면Worst Case에 가까워지는 빈도를 줄일 수 있다. → Java7에서는 분리연결법을 사용해HashMap을 구현하고 있다.✅ 보조 해시 함수 보조 해시 함수
supplement hash function의 목적은key의 해시 값을 변형해 해시 충돌 가능성을 줄이는 것이다. 분리연결법 방식을 사용할 때 함께 사용되며 보조 해시 함수로Worst Case에 가까워지는 경우를 줄일 수 있다.분리연결법은 두가지 구현 방식이 존재한다.
Linked List를 사용 각각의 버킷들을 연결 리스트로 만들어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식이다. 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다. 또한 버킷을 계속해서 사용하는 개방주소법 방식에 비해 테이블 확장을 늦출 수 있다. 하지만 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다는 단점이 있다.Tree를 사용 기본적인 알고리즘은 분리연결법 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결 리스트를 사용할지 트리를 사용할지에 대한 기준은 하나의 해시 버킷에 할당된key-value쌍의 개수이다. 트리는 기본적으로 메모리 사용량이 많기 때문에 데이터의 개수가 적다면 연결 리스트를 사용하는 것이 맞다. 데이터 개수가 적을 때의Worst Case는 트리와 연결 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면에서는 트리보다 연결 리스트가 유리하다.✅ 데이터가 적다는 것은? 어떤 자료구조를 해시 테이블에 사용할지에 대한 기준은 하나의 해시 버킷에 할당된
key-value쌍의 개수이다. 이key-value쌍의 개수가 6개, 8개를 기준으로 결정한다. 연결 리스트의 기준과 트리의 기준을 6과 8로 결정한 것은 변경하는데 소요되는 비용을 줄이기 위함이다.예시로, 기준을 6과 7로 설정한 경우에서 어떤 해시 버킷에 6개의
key-value쌍이 들어있다. 그리고 하나의 값이 추가되어서 7개가 된다면 자료구조를 연결 리스트에서 트리로 변경해야 한다. 그 이후에 바로 하나의 값이 삭제된다면 다시 트리에서 연결 리스트로 자료구조를 변경해야 한다. 각 자료구조로 넘어가는 기준 차이가 1이라면 자료구조를 Switching 하는 데 사용되는 비용이 많이 필요하게 되는 것이다. 그래서 2라는 여유를 남기고 기준을 잡은 것이다. 따라서 데이터의 개수가 6개에서 7개로 증가했을 때는 연결 리스트의 자료구조일 것이고, 8개에서 7로 감소했을 때는 트리의 자료구조일 것이다.Open Address vs Separate Chaining
두 방식 모두
Worst Case에서 O(N) 이다. 하지만 개방주소법은 연속된 공간에 데이터를 저장하기 때문에 분리연결법에 비해 캐시 효율이 높다. 따라서 데이터의 개수가 충분히 적다면 개방주소법이 분리연결법보다 더 성능이 좋다. 한 가지 차이점은 분리연결법에 비해 개방주소법이 버킷을 계속 사용한다는 것이다. 따라서 분리연결법으로 테이블의 확장을 보다 늦출 수 있다.해시 버킷의 동적 확장 (Resize)
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다. 그래서
HashMap은key-value쌍 데이터의 개수가 일정 개수 이상이 된다면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다. 해시 버킷 크기를 두 배로 확장하는 임계점인 '일정 개수 이상' 이란, 데이터의 개수가 해시 버킷의 개수의 75%가 될 때이다.0.75는load factor라고도 불린다.추가
개방 주소법 - Double Hashing Probing
개방 주소법에서 해시 충돌이 발생한다면, 다른 해시 함수를 사용해서 새로운 해시를 할당 받는다. 여기서 새로운 해시를 할당 받는 다른 해시 함수를 보조 해시 함수라고도 부른다.
분리 연결법 - 보조 해시 함수
기본적인 개념은 충돌이 발생할 경우 비어있는 버킷을 찾아서 저장하지 않고, 버킷에 데이터를 추가하는 방법이다. 처음 해시 키값을 연산할 때, 보조적인 해시 함수를 사용할 수도 있다. 즉, 필수적으로 사용되는 것은 아님.
두 부분에서 사용되는 보조 해시 함수는 크게 분리하지 않아도 될 것 같습니다!