Hash란?
자바 알고리즘을 공부하다 보면 가장 많이 나오는 단어 중 하나가 Hash입니다.
Hash란 데이터를 다루는 기법 중 하나입니다. 특히 Hash는 검색과 저장에서 아주 우수한 성능을 보여 많은 쓰임새를 얻고 있습니다.
Hash의 핵심은 KEY와 VALUE 입니다. Key와 Value가 한 쌍으로 존재합니다.
또한 우리는 Key와 Value의 쌍을 Hash Table이라고 부릅니다.
Key는 Hash에서 매핑할 때 사용하는 인덱스라고 생각하시면 됩니다. Key는 절대로 중복되지 않는다는 특징을 가지고 있습니다.
만약 같은 Key에 값을 넣으면 이전 값은 사라지고 나중에 들어온 값만 남습니다. <- 이 부분은 뒤에서 다시 설명할께요!!
Value는 Key로 매핑했을 때 나오는 값을 말합니다.
Hash는 배열의 인덱스와 다르게 순차적으로 저장되는 것이 아니라 전 영역에 고루 분포된다는 특징을 가지고 있습니다.
따라서, 배열보다 빠르게 값을 찾을 수 있다는 장점을 가지고 있습니다.
Hash코드, Hash함수
Hash로 값을 생성하면 고유의 주소 값이 생기는데 이것을 숫자로 변환한 것을 우리는 해시코드라고 부릅니다.
즉, 자바에서 해시코드는 Heap 영역의 인스턴스에 대한 참조 값이라고도 부를 수 있습니다.
Hash 함수란 데이터의 효율적 관리를 위해 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터를 매핑해주는 함수입니다.
예를 들어 군대에서는 언어를 모스부호로 바꿔 암호화하여 전달합니다. 여기서 모스부호로 바꾸는 과정을 '해시함수'라고 이해하면 쉽습니다.
위에 그림에서 보듯이 Keys가 들어와서 Hash Function을 거쳐 Hash Value가 나타납니다.
Hash Collision
위에서 잠깐 거론한 말이 있는데 바로 "같은 Key에 값을 넣으면 이전 값은 사라지고 나중에 들어온 값만 남는다" 입니다.
우리는 이러한 문제를 'Hash Collision' 즉 해시충돌이라고 부릅니다.
해시 충돌이 발생하게 되면 검출 속도를 느리게 만들고 버킷 오버플로우를 발생시키는 문제가 나타납니다.
버킷 오버플로우란 버킷의 크기가 작으면 서로 다른 키를 해시함수하여 같은 해시 값이 나와 버킷이 크기를 넘을 수 있음
따라서 우리는 해시 충돌을 해결한 방법이 필요합니다.
-
Chaining : 해시 충돌이 일어나면 연결 리스트를 이용해 데이터들을 연결하는 방식
Chaining은 추가적인 메모리를 이용해 동일한 Bucket에 연결 리스트로 하나씩 순차적으로 저장하는 것을 의미합니다.
즉, 꼬리잡기 게임처럼 연결 리스트 내에서 하나의 노드가 되어 차례대로 연결되는 것을 의미합니다.
Chaining은 연결리스트만 사용하면 되서 복잡하지 않고 같은 주소 값을 그대로 사용할 수 있다는 장점이 있습니다.
but, 특정 주소에 계속 쌓이게 되면 성능이 현저하게 낮아지고 많은 메모리 공간을 잡아 먹는다는 단점이 있습니다.
-
Open Addressing : 해시 충돌이 일어나면 다른 Bucket에 삽입하는 방식
개방 주소법은 대표적으로 3가지의 방법을 추가적으로 가지고 있습니다.
- Linear Probing : 해시 충돌 발생 시 다음 bucket이나 몇 개의 bucket을 건너 뛰어 데이터를 삽입하는 방식
- Quadratic Probing : 해시 충돌 발생 시 제곱만큼 건너 뛰어 데이터를 삽입하는 방식
- Double Hashing : 해시 충돌 시 다른 해시함수를 한번 더 적용시킴
개방 주소법은 chaining처럼 추가적인 메모리가 필요없다는 장점을 가지고 있습니다.
또한 데이터를 직접 모두 읽어 오기 때문에, 포인터를 쓸 일이 없어 포인터를 사용함으로써 나타나는 오버헤드를 방지할 수 있습니다.
