Hash

• 데이터를 빠르게 저장하고 가져오는 기법 중 하나

해시 함수 (짧게는 그냥 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다.

쉽게 말해, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수이다.

 

java의 hashcode 를 이용하면 아래와 같은 결과가 나온다.

위의 1,3번째 "Hello" 는 hashcode 적용 하더라도 같은 데이터를 추출한다.

 

---

Hash Table

key-value 데이터들의 모음집

⇒ key 를 이용하여, 데이터를 저장하거나 or 꺼내온다

 

아래의 예시는 데이터가 Hash Table에 어떻게 저장되는지를 그림으로 표현한다.

 

Key	Value
John Smith	521-1234
Lisa Smith	521-8976
Sandra Dee	521-9655

 

1. Key = (”John Smith”)
2. Key 를 Hash Function(해시함수) 에 넣는다. ⇒ Hash Function의 결과 = Hash Code (02)
3. Hash Code(02)를 배열의 Index(02) 로 사용하여
4. 해당하는 Index(02)에 data(521-1234) 넣는다

좋은 해시함수 기준

Hash의 개념에서 가장 중요한 것은 Hash Function(해시함수) 를 어떻게 만드냐? 는 것이다. 

 

• 키값을 고르게 분포 시킴
• 빠른 계산
• 충돌 최소화 = 충돌이 많아질 수록 탐색의 시간 복잡도가 O(1)에서 O(N)에 가까워지기 때문.

 

---

Hash Collision : 해시충돌

• 비둘기 집 원리

N + 1 개의 물건을 N 개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다

 

1상자에는 2개가 무조건 들어가야..

• 생일 문제

임의의 사람 N 명이 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률

생일의 가능한 경우의 수는 366개 (2월 29일 포함)

 

• 366명이 모여야 생일이 같은 경우가 있을까?
• 실제로는 23명만 나와도 50.7% 의 확률로 존재
• 50명인 경우, 97%

위의 두가지가 의미하는 것은 이러한 해시충돌은 물리적으로 꽤 높은 확률로 있을수 밖에 없다는 것이다.

 

 

HashTable에서는 키 값이 다른데도 불구하고 Hashcode 가 같은 값이 나올수도 있다. 이는 절대 있어서는 안되는 경우이며, 이것을 해시충돌이라고 부른다. 해시충돌을 해결하는 방법은 대표적으로 2가지가 있다.

Lisa Smith , Sandra Dee 가 출동발생

충돌 해결 방법

1. Separating Chaining : 체이닝 방식을 활용하여 충돌을 해결 (가장 기본 방식)

이 방법은 JDK내부에서도 사용하고 있는 충돌 처리 방식인데, LinkedList를 이용하는 방식이다. LinkedList뿐만이 아니라 Tree(Red-Black Tree)를 사용하기도 한다. 이 두가지 방식(LinkedList or Tree)를 사용하는 기준은 Data가 6개 이하이면 LinkedList를 사용하고 8개 이상이면 Tree를 사용한다.

 

왜 7개는 안되고, 6,8개를 기준으로 하는지 아니냐 의문이 들 수 있다. 만약 7개일 때, 데이터를 삭제하게 되면 linked list로 바꿔야 하고 만약 추가되면 tree로 바꿔야한다. 이때 바꾸는데 오버헤드가 있기 때문에 기준이 6, 8개이다.

 

위의 해시충돌을 다시보자.

잘보면 오른쪽의 entries 구성 상태 = List<Node>[] 이다.

전체 구성은 Array 이고, 내부데이터 1개 1개는 List<Node>로 구성되어 있다는 의미.

Array<List<Node>>

• 핵심은 다른 데이터가 같은 인덱스를 가리키고 있을때 어떻게 처리하냐는 것이다.(충돌을 어떻게 처리하겠다는 것인가?)

⇒ Sandra Dee 경우, 이미 John Smith가 152번 인덱스를 점유 하고 있지만, 해당 152번 인덱스의 LinkedList에 노드를 추가하여 값을 삽입한다.

 

아래 처럼 되어 있다는 의미.

John Smith	152	Node   Key : John Smith   value : 521-1234	Node   Key : Sandra Dee   value : 521-9655
Sandra Dee

 

충돌이 계속 되면되면, 아래처럼 처리 된다.

위 그림의 의미는 

• 10번 index 는 A노드 1개만 존재 (충돌 X)

• 12번 index 는 H,E노드 2개 존재 (충돌 1번)

• 13번 index 는 U,X,T노드 3개 존재 (충돌 2번)

있었음을 의미 한다.

 

2. Open addressing : 충돌시 다른 버킷에 데이터 저장

이 방법은 인덱스에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용하는 방법이다. 추가적인 메모리 공간을 사용하지 않기 때문에 Separate chaining방식에 비해서 메모리를 덜 사용한다. Linear Probing, Quadratic Probing, Double hashing 등이 있다.

2-1. Linear Probing : 선형탐색

해시충돌시 N칸을 건너 뛴 다음 버킷에 저장

• 계산 단순
• 검색시간이많이소요
• 데이터들이 특정 위치에만 밀집(clustering)

 

충돌이 발생할 때 인덱스 뒤에 있는 버킷중에 빈 버킷을 찾아서 데이터를 넣는다.

1. 그림에서 Sandra Dee(key)의 인덱스는 152이다.
2. 하지만 키 John과 충돌이 나기 때문에 그 다음 인덱스인 153에 데이터를 넣는다.(1칸 이동. 또 충돌 나면 빈칸을 찾을때까지 이동)
3. Linear Probing방식에서의 탐색은, Sandra(key)에 대해서 검색을 하면, index가 152가 나온다.
4. key가 일치하지 않기 때문에, 뒤의 index를 검색해서 같은 키가 나오거나 또는 Key가 없을때 까지 검색.
5. 삭제는 더미 노드를 넣어서 검색할 때 다음 인덱스까지 검색을 연결해주는 역할을 해줘야한다. (즉, 삭제가 어렵다.)

2-2. Quadratic Probing (N^2) : 제곱 탐색

위 방법에서 그다음 인덱스 칸에 데이터를 넣는 것이 아니라, N^2 칸에 더 띄어서 넣는것.

• N2칸(1,4,9,16,...)을 건너 뛴 버킷에 데이터를 저장

• 데이터들이 특정 위치에 밀집하는 문제를 해결

• 하지만 처음 해시값이 같다면 여전히..

2-3. Double Hashing : 이중 해싱

해시 한 값에 한번더 해시 적용

• Hashfunction1(): 최초의 해시 값을 구함
• Hashfunction2(): 충돌 발생시 이동 폭을 구함

• 최초 해시 값이 같더라도 이동 폭이 다르기 때문에 clustering 문제 해결 가능

 

---

Hash Table 의 장점

1. 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
2. 배열의 인덱스(index)를 사용해서 검색, 삽입, 삭제가 빠르다. 
   
   • 하지만 삽입, 삭제는 왜 O(1)인가? : 여기서의 인덱스는 데이터만의 고유한 위치이기 때문에 만약 삽입이나 삭제를 한다고 해도 다른 데이터로 채울 필요가 없다. 즉, ArrayList처럼 삽입이나 삭제할 때 데이터를 이동할 필요가 없기 때문이다.
3. 키(key)와 해시값(Hash)이 연관성이 없어 보안에도 많이 사용된다.
4. 데이터 캐싱(Data Caching)에 많이 사용된다.
   • get(key), put(key)에 캐시 로직을 추가하면 자주 hit하는 데이터를 바로 찾을 수 있다.
5. 중복을 제거하는데 유용하다.

Hash Table 의 단점

1. 충돌
2. 공간 복잡도가 커진다. (리스트 중간중간 비어있는 공간 있음)
3. 순서가 있는 배열에는 어울리지 않는다.
4. 해시 함수 의존도가 높아진다.

---

HashMap과 Hashtable 차이점

• Thread-safe 여부
  • Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다는 특징을 가지고 있습니다. 그렇기에 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다는 단점을 가지고 있습니다.
• Null 값 허용 여부
  • Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용합니다.
• Enumeration 여부
  • Hashtable은 not fail-fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않습니다.
• HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있습니다.
• 최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있습니다.

조금 더 자세히 알고 싶다면 Java HashMap은 어떻게 동작하는가? 를 참고하면 좋습니다.