저희 스터디 그룹은 이번주에 해쉬(Hash)에 대해서 공부했습니다.
자바에서 그냥 아무 생각없이 HashMap, HashSet 등을 사용했는데, 이번주에 해쉬에 대한 강의를 들으면서 그 개념에 대해 이해하게 되었습니다.
일단, 이 해쉬라는 것을 요약하자면 주어진 키(Key)를 통해 실제 데이터가 저장된 주소를 직접적으로 계산해내는 것을 말합니다. 즉, 데이터 개수와 무관하게 단번에 원하는 데이터를 찾아내겠다는 것을 의미합니다. 그렇기 때문에 저장 및 탐색 속도가 빠릅니다.
주어진 데이터의 키에 해쉬 함수(Hash Function)를 가하면 그 데이터가 저장되어 있는 인덱스(고정된 길이의 값)가 반환되며, 이러한 인덱스를 이용하여 직접 접근이 가능한 데이터 구조인 해쉬 테이블(Hash Table)에서 데이터를 확인할 수 있습니다.
해쉬 테이블 장점
- 데이터 저장/읽기 속도가 빠릅니다.
- 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽습니다.
위와 같은 장점으로 검색이 많이 필요한 경우 또는 저장, 삭제, 읽기가 빈번한 경우에 많이 사용되며, 중복 확인 쉽기 때문에 캐쉬 구현 시에 주로 사용됩니다.
해쉬 테이블 단점
- 일반적으로 저장공간이 좀 더 많이 필요합니다.
- 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요합니다.
위 단점에서 충돌을 해결하기 위해 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법인 Close Hashing 의 종류 중 하나인 선형 탐사(Linear Probing) 방식이 있습니다. 또한 해쉬 테이블 저장공간 외의 공간을 활용하는 기법인 Open Hashing의 종류 중 하나인 체인(Chaining) 방식이 있습니다.
이 선형 탐사에 대해서 간단하게 설명하자면, 충돌이 일어나면 그 다음 빈 곳을 찾아가는 방식입니다.
체인은 충돌이 일어나면, 저번에 설명드렸던 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 방식입니다.
위에서 간단히 설명한 해쉬에 대해서 자바에서는 해쉬 테이블 구조를 활용하여 구현된 HashMap 같은 컬렉션 프레임워크를 제공하고 있습니다. 이를 활용하여 알고리즘 문제를 풀었습니다.
그 과정에서 내부 Hash 값에 따라 Key 순서가 정해지기 때문에 순서가 정해져 있지 않은 HashMap과 더블 링크드 리스트 자료구조로 저장되고, 또한 링크드 리스트 구조이므로 넣은 순서대로 출력되는 LinkedHashMap에 대해서 알게 되었습니다.
그리고 또한 릿코드 문제 중, 페이지 교체 알고리즘 중 하나인 LRU(Least Recently Used) 에 대한 문제가 있었습니다. 이는 LinkedHashMap로 쉽게 구현할 수 있었습니다. 바로 생성자 파라미터로 accessOrder 라는 값을 받음으로써 해결할 수 있었습니다.
accessOrder는 기본값이 false이며, 만약 true로 설정한다면 LinkedHashMap의 접근 빈도에 따라서 순서가 바뀌게 됩니다. 이를 이용하면 가장 참조되지 않은 데이터를 쉽게 알 수 있습니다.
그룹원 중 한 분이 LinkedHashMap의 accessOrder라는 것을 이용하여 해결하셨는데, 이 신기한 존재를 알게되어 감사했습니다.
그리고 LinkedHashMap을 사용하면서 가장 앞에 있는 데이터를 알고 싶어 방법을 찾다가 알게된 것이 있습니다.
가장 앞에 있는 Key를 반환하고 싶을 때,
linkedHashMap.keySet().iterator().next();
가장 앞에 있는 Value를 반환하고 싶을 때,
lnkedHashMap.values().iterator().next();
를 이용하면 된다는 것을 배웠습니다.
이제 점점 내용이 어려워지고 있는 것 같고 문제를 풀 때, 개념이 아직 덜 잡혔는지 시간이 좀 오래걸리는 것 같습니다. 정신을 바짝 차려야 할 것 같습니다.
