해시(Hash)

해시란?

해시(Hash) 함수, 또는 해시 알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑, 변환 해주는 함수이다.

해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드 등인데 간단하게 해시라고한다.

즉 해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값이다

해시 함수?(Hash Function)

데이터를 효율적으로 관리하기 위해, 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다.

임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수입니다. 암호 알고리즘에는 키가 사용되지만, 해시 함수는 키를 사용하지 않으므로 같은 입력에 대해서는 항상 같은 출력이 나오게 됩니다.

해시 함수의 특징

어떤 입력 값에도 항상 고정된 길이의 해시값을 출력한다.
눈사태 효과 : 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다.
출력된 결과 값을 토대로 입력값을 유추할 수 없다.

해시 테이블에 사용되는 대표적인 해시 함수 4가지:
1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.
  - ( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
  - 숫자로 된 키를 해시테이블 크기 m으로 나눈 나머지를 해시값으로 반환. m은,
  - 대개 소수(prime number)를 쓰며 특히 2의 제곱수와 거리가 먼 소수를 사용하는 것이 좋다고 합니다.
  - 다시 말해 해시함수 특성 때문에 해시테이블 크기가 정해진다는 단점이 있다는 이야기입니다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다.
  1. 숫자로 된 키가 𝑘k이고 𝐴A는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의
  2. h(k) = ( kA mod 1 ) × m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

어설픈 hash function을 통해서 key 값들을 결정한다면 동일한 값이 도출될 수가 있다.

이렇게 되면 동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것인데 이를 Collision 이라고 한다.

Collision(충돌) : 서로 다른 두 개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 된다.
Collision을 최소화하고 Collision에 대비해 어떻게 대응하여 해시 함수를 만들것인지가 중요하다.

해시 충돌(Collision) 해결법

기본적인 두 가지 방법부터 알아보자. 해시 충돌을 해결하기 위한 다양한 자료가 있지만, 다음 두 가지 방법을 응용한 방법들이기 때문이다.

1. Open Address 방식 (개방주소법)

해시 충돌이 발생하면, (즉 삽입하려는 해시 버킷이 이미 사용 중인 경우) 다른 해시 버킷에 해당 자료를 삽입하는 방식 이다.

버킷이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.
다른 해시 버킷이란 어떤 해시 버킷을 말하는 것인가?

공개 주소 방식이라고도 불리는 이 알고리즘은 Collision 이 발생하면 데이터를 저장할 장소를 찾아 헤맨다.

Worst Case 의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.

이 과정에서도 여러 방법들이 존재하는데, 다음 세 가지에 대해 알아보자.

Linear Probing(선형 조사) : 충돌이 일어난 원소부터 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.
- 참조
Quadratic probing(이차 조사) : 2 차 함수를 이용해 탐색할 위치를 찾는다. 선형 조사와 비슷하지만 2의 제곱으로 다음 빈 버킷을 찾아 이동한다.
- 참조
Double hashing probing(이중 해싱 조사) : 하나의 해쉬 함수에서 충돌이 발생하면 2 차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구하게 된다.

2. Separate Chaining 방식 (분리 연결법)

일반적으로 Open Addressing(개방 주소법) 은 Separate Chaining 보다 느리다.

Open Addressing 의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다.

반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다.

Java 7 에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다. Separate Chaining 방식으로는 두 가지 구현 방식이 존재한다.

각 index에 데이타를 저장하는 Linked list 에 대한 포인터를 가지는 방식이다.

* [이미지출처](https://en.wikipedia.org/wiki/Hash_table) * 만약에 동일 인덱스로 인해서 충돌이 발생하면 그 인덱스가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다. * 충돌이 발생하더라도 데이타를 삽입하는 데 문제가 없다.
연결 리스트를 사용하는 방식(Linked List)
- 각각의 버킷들을 연결리스트로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식이다.
- 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하다.
- 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다.
- 또 다른 특징으로는, 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.
Tree 를 사용하는 방식 (Red-Black Tree)
- 기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다.
- 연결 리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수이다.
- 데이터의 개수가 적다면 연결 리스트를 사용하는 것이 맞다.
- 트리는 기본적으로 메모리 사용량이 많기 때문이다.
- 데이터 개수가 적을 때 Worst Case 를 살펴보면 트리와 링크드 리스트의 성능 상 차이가 거의 없다.
- 따라서 메모리 측면을 봤을 때 데이터 개수가 적을 때는 링크드 리스트를 사용한다.

해시 테이블이란?(HashTable)

hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받는다.

해시함수 h에 key (key) 값을 입력으로 넣어 얻은 해시값 h(k) 를 위치로 지정하여 key- value 데이터 쌍을 저장하고,

key 값으로 빠르게 value를 가져올 수 있다.

저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다. 최악의경우 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(n)의 시간복잡도를 가진다.

내부적으로 배열(버킷)을 사용하여 데이터를 저장한다.
각각의 key 값에 해시함수를 적용해 배열의 고유한 인덱스를 생성하고, 인덱스로 값을 저장하거나 탐색한다.
동기화를 지원한다.
key, value에 널 값을 허용하지 않는다

하지만, 데이터가 많아지면, 다른 데이터가 같은 해시 값을 가지게 되어 충돌이 발생하게 된다.

해시 테이블의 근본적인 문제는 결국 index의 충돌이다.

해시는 원래 데이터가 같으면 해시값도 항상 같다.

그러나 서로 다른 데이터 또한 동일한 해시값을 가질 수 있기 때문에 해시 충돌이 발생한다.

-> Collision 현상.

그럼에도 해시 테이블을 쓰는 이유?

적은 자원으로 많은 데이터를 효율적으로 관리하기 위함이다.

하드 디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능해진다.

언제나 동일한 해시 값을 리턴, index를 알면 빠른 검색이 가능해진다.
해시 테이블의 시간 복잡도 : O(1) [이진 탐색 트리는 O(logN)]

테이블 종류

Direct-Address-Table (DAT, 직접 주소화 테이블)

키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블

key값으로 k를 갖는 원소는 index k 에 저장하는 방식

즉, 인덱스 값을 키값으로 사용하는것.

U(universe of keys) : 전체 키
K(Actual keys) : 실제 사용하는 키

장점 : 키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다.
단점 : 전체 키가 실제 사용하는 키보다 훨씬 많은경우 사용하지 않는 키들을 위한 공간들까지 마련해야 하기 때문에 메모리 효율성이 떨어진다.
- 불필요한 메모리 낭비가 생긴다.
- key값으로 다양한 자료형을 담을 수 없다.

Hash Table(해시 테이블)

해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조

DAT랑 다르게, 변환할 값을 index로 삼는것.

key는 무조건 존재해야 하며, 중복되는 key가 있어서는 안된다

hash table을 구성하고 있는, (key, value) 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 한다.

해시 함수(hash function)를 통해 변환된 값이 key가 되고 값을 value(buckets or slot)에 저장한다.

좋은 해시 함수의 조건은 뭘까요?
- 각 상황마다 좋은 해시 함수는 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아 충돌이 적야아 하는것
worst case에 시간복잡도는 O(n) 인 상황은 어떤 상황인가?
- n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 연결 리스트가 생성되게 된다.
- 이 때, 특정 key를 찾기 위해서는 길이 n의 연결 리스트를 모두 검색하는 O(n) 시간복잡도와 동일하게 된다.
이중해싱(double hashing)이 무엇인가?
- 이중 해싱은 open addressing(개방 주소법) 방식을 통해 collision(충돌)을 해결할 때, probing(조사)하는 방식중에 하나입니다.
- 참조

자바에서의 해시맵, 해시테이블

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

HashTable은 병렬 프로그래밍을 할 때 동기화를 지원해준다.

따라서 해당 함수를 처리하는 시간이 조금 지연됨을 의미힌다.

병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황 → 해시테이블(HashTable)
병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황 → 해시맵(HashMap)
자바 HashTable 클래스의 put() 메서드를 살펴보면 synchronized 키워드가 붙어있다.

Hashtable<String, String> hashTable = new Hashtable<String, String>(); // Hashtable 선언
Map<String, String> hashMap = new HashMap<>(); // HashMap 선언

'CS > 자료구조(Data Structure)' 카테고리의 다른 글

[자료구조] 그래프와 DFS, BFS (0)	2022.08.14
[자료구조] Heap 힙, 우선순위 큐 (0)	2022.08.14
[자료구조] 트리, B Tree, B+Tree (0)	2022.08.14
[자료구조] 트리, AVL 트리 (0)	2022.08.14
[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree) (0)	2022.08.14

[자료구조] 해시, 해시테이블