[자료구조] 해시(hash) #java

 

 

해시(Hash)

---

• 해시 자료구조 설명
• 해시 자료구조 JAVA 구현

 

해시 (hash) 

---

linkedList 에서 원하는 요소를 찾기 위해선 처음부터 끝까지 모든 요소를 탐색해야 합니다. n개의 요소가 있다면 O(n)의 시간복잡도가 걸리게 됩니다. 이것은 매우 비효율적입니다.

여러 상황에서 빠르게 데이터를 추가하거나 제거하도록 하고 싶었습니다. 그리고 무언가 찾아야 할때 빠르게 찾을 수 있어야 했습니다. 해시는 이러한 단점을 해결 할 수 있습니다.

 

Hash는 Key, 그리고 연관된 Value를 가지고 있습니다. 모든 요 소를 살펴본 후 동일한 노드를 찾는 LinkedList와 달리 Hash는 Key가 주어지면 빠르게 Value를 찾을 수 있습니다.

 

 

Hash는 Key와 Value를 저장하기 위해 연상배열(Associative Arrays)을 사용합니다. 연상 배열은 Key의 인덱스에 따라 Value값을 참조하는 독특한(?) 배열입니다.

 

예를 들어 Key-전화번호, Value-이름을 연상배열에 저장한다면 다음과 같이 저장 할 수 있습니다.

 

 

 

해시 함수(Hash Function)

---

해시 함수는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. KEY 값이 너무 길다면 데이터를 저장하는데 많은 메모리를 사용하게 될 수도 있습니다.

 

해시 함수는 다음과 같은 특징을 갖습니다.

 

▶ property of the data

데이터의 속성을 나타낼 수 있어야 합니다. 즉,유일한 값이 되도록 해시 함수를 구성해야 합니다.

 

▶ be fast to compute

해시함수를 이용해서 빠르게 계산할 수 있어야 합니다.

 

▶if two things are "equal", should return the same value

동일한 무언가를 해시함수를 돌리면 몇 번을 해시함수를 돌려도 동일한 값이 나와야 합니다.

 

▶ always return the same value. during one run of the code

프록그램이 동작하는동안 해시 함수는 항상 동일한 값이 나와야 합니다.

 

▶ it is possible to return different values for an object in separate runs.

개별적인 프로그램 실행시에는 다른 값이 반환되는 것이 가능합니다. 자바의 Object 클래스는 override 가능한 여러 함수들이 있습니다. 그 중 hashcode 함수는 객체의 메모리 주소를 반환합니다. hashcode 함수를 재정의하지 않는다면 프로그램을 실행할 때마다 다른 값이 반환 될 수 있습니다.

💡 참고 Object의 hashcode함수는 int를 반환합니다!

 

▶ minimize collisions

해시함수는 해시충돌을 최소화 해야합니다.

 

 

해시 충돌(Hash Collisions)

---

해시 충돌은 해시함수를 통해 반환된 Key 값이 충돌하는 경우를 말합니다. 동일한 Key 값을 저장 할 수 없으니 이는 문제가 됩니다. 따라서 해시 충돌이 발생하지 않도록 해시함수의 분포를 더 넓게 펼칠 수 있을지 생각해야 합니다.

 

해시 충돌이 나는 예시를 설명해보겠습니다.

 

 

전화번호를 해시에 저장하려고 합니다. 그런데 전화번호가 너무 길어 해시 함수를 통해 길이를 줄이려고 합니다. 전화번호를 3개로 나누어 각 자릿수의 합을 Key값이 되도록 해시 함수를 구성했습니다.

 

 

장장스의 전화번호를 해시함수를 통해 2386 key를 반환받았습니다.

 

제임스의 전화번호를 해시함수를 통해 2386의 Key를 반환받았습니다. 제임스와 장장스의 Key가 같군요? 이와 같이 서로 다른 무언가가 해시 함수를 통해 같은 Key를 얻는 해시 충돌이 발생했습니다!

 

 

 

해시 충돌 방지 방법

---

그렇다면 해시 충돌이 나지 않기 위해 어떻게 해야할까요?

 

해시 크기 최적화

방법 1: 해시의 크기를 홀수로 설정하여 % 연산자를 사용했을 때 다양한 결과가 나오게 합니다.
방법 2: 해시의 크기를 소수로 설정하여 나머지가 다양한 숫자가 나오게 합니다.

 

양수로 반환

해시 값이 음수가 나오는 경우도 있을 겁니다. 배열의 인덱스는 음수일 수 없으니 해시 값은 양수가 나와야 합니다. JAVA에서는 음수를 표현하기 위해 2의 보수를 활용합니다. 이 방법을 사용하여 배열의 어느 위치에 넣을 것인지 결정합니다.

int hashval = data.hashCode(s);
hashval = hashval & ox7FFFFFFF;
hashval = hashval % tableSize;

 

해시 충돌 해결 방법

---

그럼에도 불구하고 해시 충돌이 발생 할 수 있습니다. 해시 충돌을 어떻게 해결할 수 있을까요?

 

1. 선형조사법(linear probing)

채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법입니다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 합니다. 데이터를 삽입하는 것은 단순하나 조회, 삭제시 번거롭다는 문제가 있습니다.

 

2. 2차식 조사법(quadratic probing)
다음 칸 대신 1부터 순서대로 제곱하여 더한 칸( 1^2​ , 2^2​​ , ... )을 확인하는 방법입니다. 테이블의 끝을 넘어간다면 % 연산을 해서 다시 테이블의 범위 안에 들어오게 합니다.

 

3. 이중 해싱(double hashing)
hashCode 함수가 2개 있어 채우려는 공간이 이미 차 있다면 두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법입니다.

이중 해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 더 골고루 넣을 수 있습니다. 하지만 해시 함수가 2개 필요하다는 단점이 있습니다.

 

위 3개의 방법은 해시 테이블이 빠르게 채워지는 문제가 있습니다. 따라서 배열을 계속해서 늘려줘야 합니다. 보통 JAVA에서는 적재율(load factor, λ)가 0.6이될 때 해시 테이블을 늘려주게 됩니다.

 

 

4. 체이닝 (chaining)

위에서 언급한 문제를 연결리스트(linkedlist)를 활용하여 체이닝을 구현함으로서 해결 할 수 있습니다.

 

 

 

 

체인 해시 방법은 최고의 방법입니다. 그러나 주의해야할 점이 있습니다. 해시 테이블에 너무 많은 값이 체인에 연결되면 시작복잡도가 증가하게 됩니다. 최악의 경우 O(n)의 시간복잡도가 될 수 있습니다. 

 

 

재해싱 (Rehashing)

---

체인 해시가 너무 많이 차게 되면 크기 조정을 해야합니다. 보통 크기가 2배인 배열을 만듭니다. 재해싱할 때 체인 해시 값들은 처음부터 다시 위치를 지정해주어야 합니다. 왜 그럴까요?

int idx = x.hashCode(s);
idx = idx & ox7FFFFFFF;
idx = idx % tableSize;

 

해시함수에서 tableSIze가 2배가 되었으니 그 결과또한 달라지게 됩니다. 그러므로 재해싱을 하게 되면 다른 결과값이 나오게 됩니다!

 

 

Post

---

• 2021.10.05 - [DataStructures] - [자료구조] 해시 구현하기 #java

References

---

• 부스트코스 - 자바로 구현하고 배우는 자료구조

 

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)