이번 주 공부할 내용인 해시 테이블 자료구조에 대해 정리해보겠습니다. 먼저 해시 테이블과 해싱(Hashing)이 무엇인지 알아보겠습니다. 그다음 자바에서 어떻게 적용되어 있는지 알아본 후 대표적인 클래스와 그 메서드를 알아보겠습니다.
해시 테이블(Hash Table)
해시 테이블이란 키와 값의 쌍으로 이루어진 자료구조입니다. 해당 자료구조에는 해싱이라는 과정을 통해서 데이터가 저장됩니다. 그리고 원리적으로는 데이터 양이 아무리 많아지더라도 자료의 검색과 삭제에 O(1)의 시간이 걸립니다. 때문에 커다란 데이터에서 특정한 값을 검색할 때 해시 테이블을 사용하는 것이 유리합니다.
여기서 해싱(Hashing)이란 해시 함수(Hash Function)를 이용해 데이터를 저장하고 검색하는 기법을 말합니다. 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다. 예를 들어 해시 함수 중 하나인 SHA-256의 경우 해당 함수에 한 글자를 넣던 백 글자를 넣던 입력값의 길이에 상관없이 256비트의 결괏값이 출력됩니다. 좀 더 간단히는 아래의 그림과 같이 표현할 수 있습니다.
해시 테이블은 자료 검색에 사용하기 위한 자료구조라 키값에 중복이 있으면 안 됩니다. 하지만 해시 함수는 어떤 값을 입력으로 넣든 간에 같은 길이의 결괏값을 반환하기 때문에 낮은 확률일지라도 서로 다른 값을 입력으로 넣었지만 같은 값이 출력되는 경우가 있습니다.
위의 그림과 같으며 이를 해시 충돌이라고 합니다. 해시 충돌을 방지하기 위해서 체이닝이나 이중 해시같은 방법이 사용됩니다. 다음과 같이 간단히 해시에 대해 알아보았습니다. 다음으로는 자바에서의 해시에 대해 알아보겠습니다.
자바에서의 해싱
자바에서 해싱을 구현한 클래스로는 HashSet, HashMap, Hashtable 등이 있습니다. 이중 컬렉션 프레임워크가 등장하기 전에 사용하던 Hashtable은 이전 소스와의 호환성 문제로 남겨두고 있으니 이제는 HashMap을 사용하는 것이 좋습니다. 그리고 HashSet은 리스트와 달리 저장 순서를 유지하지 않습니다. 저장 순서를 유지하고자 한다면 LinkedHashSet을 사용하면 됩니다.
자바에서 해싱을 사용하는 자료구조는 배열과 LinkedList의 조합으로 되어 있습니다. 해시 함수를 통해 나온 해시 코드는 키로써 배열의 인덱스가 되고 값은 해당 배열에 연결된 LinkedList에 저장됩니다. 때문에 키값으로 배열의 해당 인덱스에 있는 연결 리스트에 있는 값을 빠르게 찾을 수 있습니다.
해시 함수에서 해시 충돌이라는 것에 대해서 이야기를 했었습니다. 자바에서는 해시 함수로 Object 클래스에 정의된 hashCode() 메서드를 사용합니다. 해당 메서드는 객체의 주소를 이용하는 알고리즘이라 모든 객체에 대해 유일한 값을 반환합니다. 때문에 해시 충돌의 걱정을 덜 수 있습니다. 그리고 String 클래스의 경우에는 오버라이딩한 hashCode() 메서드를 사용합니다. 이 메서드는 같은 내용의 문자열을 가졌다면 같은 해시 코드를 반환합니다. 이상으로 해싱은 마치고 클래스와 메서드에 대해 정리하겠습니다.
HashSet
- 중복된 요소를 저장하지 않습니다.
- 저장 순서를 유지하지 않습니다.
메서드 설명
| boolean add(Obeject o) | 새로운 객체를 저장합니다. |
| boolean addAll(Collection c) | 주어진 컬렉션에 저장된 모든 객체를 추가합니다. |
| void clear() | 저장된 모든 객체를 삭제합니다. |
| Object clone() | 얕은 복사해 반환합니다. |
| boolean contains(Object o) | 지정된 객체를 포함하고 있는지 알려줍니다. |
| boolean containsAll(Collection c) | 컬렉션 c에 저장된 모든 객체를 포함하는지 알려줍니다. |
| boolean isEmpty() | 비어있는지 알려줍니다. |
| Iterator iterator() | iterator를 반환합니다. |
| boolean remove(Object o) | 지정된 객체를 삭제합니다. |
| boolean removeAll(Collection c) | 주어진 컬렉션에 저장된 모든 객체와 동일한 것을 삭제합니다. |
| boolean retainAll(Collection c) | 주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제합니다. |
| int size() | 저장된 객체의 수를 반환합니다. |
| Object[] toArray() | 저장된 객체들을 객체 배열의 형태로 반환합니다. |
| Object[] toArray(Object[] a) | 저장된 객체들을 주어진 객체 배열 a에 담습니다. |
HashMap
메서드 설명
| void clear() | 저장된 모든 객체를 삭제합니다. |
| Object clone() | 얕은 복사해 반환합니다. |
| boolean containsKey(Object key) | 지정된 키가 있는지 알려줍니다. |
| boolean containsValue(Object value) | 지정된 값이 있는지 알려줍니다. |
| boolean remove(Object key) | 지정된 키로 된 저장된 값을 삭제합니다. |
| Object replace(Object key, Object value) | 지정된 키의 값을 value 값으로 대체합니다. |
| boolean replace(Object key, Object oldValue, Object newValue) | 지정된 키와 oldValue가 일치하는 경우에만 newValue 값으로 대체합니다. |
| int size() | 저장된 객체의 수를 반환합니다. |
| Collection values() | 저장된 모든 값을 컬렉션의 형태로 반환합니다. |
| Object put(Object key, Object value) | 지정된 키와 값을 저장합니다. |
| void putAll(Map m) | 맵에 저장된 모든 요소를 HashMap에 저장합니다. |
| Set keySet() | HashMap에 저장된 모든 키를 Set으로 반환합니다. |
| boolean isEmpty() | 비어있는지 알려줍니다. |
| Object get(Object key) | 지정된 키의 값을 반환합니다. 못찾을 경우 null을 반환합니다. |
| Object getOrDefault(Object key, Object defaultValue) | 지정된 키의 값을 반환합니다. 못찾을 경우 기본값으로 지정된 객체를 반환합니다. |
'Java' 카테고리의 다른 글
| 자바에서의 스택과 큐 (0) | 2022.09.23 |
|---|---|
| 자바의 정렬 Arrays.sort() (2) | 2022.09.14 |
| Bootstrap5 modal 버튼없이 다루기 (0) | 2022.08.02 |
| spring scheduler 이용해서 매시각 메서드 실행하기 (0) | 2022.08.02 |
| JSTL foreach 한 리스트에서 객체 두 개씩 뽑아 사용하기 (0) | 2022.07.20 |