2023. 12. 31. 20:06ㆍ프로그래밍 공부/Data Structure
9.1 맵 추상 데이터 타입
맵은 요소들을 키를 사용하여 빠르게 위치를 파악할 수 있도록 해준다.
이러한 검색을 하는 동기는
일반적으로 각 요소가 검색 키 이외에 추가적인 유용한 정보를 저장하지만,
이러한 정보를 얻을 수 있는 유일한 방법은 검색 키를 사용하는 것이다.
구체적으로, 맵은 키-값 쌍(k, v)을 저장하는데,
이것을 우리는 엔트리(entry)라고 부르고,
여기서 k는 키이고 v는 해당 값이다.
또한 맵 ADT는 각 키가 고유해야 하므로
값에 대한 키의 연관성은 맵을 정의한다.
가장 높은 수준의 일반성을 달성하기 위해,
우리는 맵에 저장된 키와 값이 모든 객체 타입이 되도록 허용한다.
(그림 9.1 참조)
학생 기록을 저장하는 맵에서 키는 학생의 ID 번호일 수 있다.
일부 응용 프로그램에서는 키와 값이 동일할 수 있다.
예를 들어 소수를 저장하는 맵이 있다면,
우리는 각 숫자 자체를 키와 값으로 사용할 수 있다.
그림 9.1: 맵 ADT의 개념도.
키(라벨)는 사용자에 의해 값(디켓)에 할당된다.
결과로 나온 항목(라벨 디스켓)은 맵(파일 캐비닛)에 삽입된다.
키는 나중에 값을 가져오거나 제거하는 데 사용될 수 있다.
어떤 경우든 우리는 응용 프로그램이나
사용자가 연관된 값 개체에 할당하는 고유 식별자로 키를 사용한다.
따라서 각 키가 값에 대한 고유 인덱스 주소,
즉 값에 대한 일종의 위치 역할을 하는 개체로 표시되는 상황에서는
맵이 가장 적합하다.
예를 들어, 학생 기록을 저장하려면
학생 ID 개체를 키로 사용하고 싶을 것이다.
즉, 개체와 연관된 키는 해당 개체의 "주소"로 볼 수 있다.
실제로 맵은 연관 저장소로 불리기도 하는데,
이는 개체와 연관된 키가 자료 구조에서
개체의 "위치"를 결정하기 때문이다.
맵 ADT
맵은 객체들의 집합을 저장하기 때문에 키-값 쌍들의 집합으로 보아야 한다.
ADT로서 맵 M은 다음과 같은 방법들을 지원한다:
size():
M의 엔트리 수를 반환한다.
isEmpty():
M이 비어 있는지 여부를 테스트한다.
get(k):
M에 k와 같은 키를 가진 e가 포함되어 있으면 e의 값을 반환하고,
그렇지 않으면 null을 반환한다.
put(k, v):
M에 k와 같은 키를 가진 엔트리가 없는 경우 M에 엔트리 (k, v)를 추가하고 null을 반환한다.
그렇지 않으면 k와 같은 키를 가진 엔트리의 기존 값을 v로 대체하고 이전 값을 반환한다.
remove(k):
키가 k인 엔트리를 M에서 제거하고 값을 반환한다.
M에 해당 엔트리가 없으면 null을 반환한다.
keys():
M에 저장된 모든 키를 포함하는 반복 가능한 컬렉션을 반환한다
(그래서 keys().iterator()는 키의 반복자를 반환한다).
values():
M에 저장된 키와 관련된 모든 값을 포함하는 반복 가능한 컬렉션을 반환한다
(그래서 values().iterator()는 값의 반복자를 반환한다).
entries():
M의 모든 키 값 엔트리를 포함하는 반복 가능한 컬렉션을 반환한다
(그래서 entries().iterator()는 엔트리의 반복자를 반환한다).
k와 같은 키를 가진 엔트리가 없는 맵 M에서
get(k), put(k,v) 및 remove(k) 작업이 수행되면
null을 반환하는 규칙을 사용한다.
이와 같은 특별한 값을 센티넬(sentinel)이라고 한다. (섹션 3.3 참조)
null을 이러한 센티넬로 사용하는 경우의 단점은
이러한 선택이 맵에 null 값을 가진 엔트리(k, null)를 갖기를 원하는 경우
모호성을 만들 수 있다는 것이다.
물론 다른 선택은 누군가가 맵에 없는 키를 요청할 때 예외를 던지는 것이다.
그러나 맵에 없을 수 있는 것을 요청하는 것은 일반적이기 때문에
이는 아마도 예외를 적절하게 사용하지 않을 것이다.
또한 예외를 던지고 받는 것은 일반적으로 센티넬에 대한 테스트보다 느리기 때문에
센티넬을 사용하는 것이 더 효율적이다.
따라서 누락된 키와 관련된 값에 대해 null을 센티넬로 사용한다.
예제 9.1:
다음은 정수 키와 단일 문자 값을 가진 항목을 저장하는 초기 빈 맵에 대한
일련의 연산의 효과를 보여준다.
| 연산 | 출력 | 맵 |
| isEmpty() | true | φ |
| put(5,A) | null | {(5,A)} |
| put(7,B) | null | {(5,A), (7,B)} |
| put(2,C) | null | {(5,A), (7,B), (2,C)} |
| put(8,D) | null | {(5,A), (7,B), (2,C), (8,D)} |
| put(2,E) | C | {(5,A), (7,B), (2,E), (8,D)} |
| get(7) | B | {(5,A), (7,B), (2,E), (8,D)} |
| get(4) | null | {(5,A), (7,B), (2,E), (8,D)} |
| get(2) | E | {(5,A), (7,B), (2,E), (8,D)} |
| size() | 4 | {(5,A), (7,B), (2,E), (8,D)} |
| remove(5) | A | {(7,B), (2,E), (8,D)} |
| remove(2) | E | {(7,B), (8,D)} |
| get(2) | null | {(7,B), (8,D)} |
| isEmpty() | false | {(7,B), (8,D)} |
java.util 패키지의 맵
Java 패키지 java.util은 맵 ADT를 위한 인터페이스를 포함하고 있으며,
이 인터페이스는 java.util.Map이라고 한다.
이 인터페이스는 구현 클래스가 고유한 키를 강제하는 것으로 정의되며,
몇 가지 경우에 다른 메소드 이름을 사용한다는 점을 제외하고는
위에 주어진 맵 ADT의 모든 메소드를 포함한다.
맵 ADT와 java.util. 맵 인터페이스의 대응 관계는 표 9.1과 같다.
표 9.1: 맵 ADT의 메소드와
다른 메소드도 지원하는 java.util.Map 인터페이스의 메소드 간의 대응.
| 맵 ADT 메소드 | java.util.Map 메소드 |
| size() | size() |
| isEmpty() | isEmpty() |
| get(k) | get(k) |
| put(k,v) | put(k,v) |
| remove(k) | remove(k) |
| keys() | keySet() |
| values() | values() |
| entries() | entrySet() |
9.1.1 간단한 리스트 기반 맵 구현
맵을 구현하는 간단한 방법은
n개의 항목을 리스트 S에 저장하고 이중 연결 리스트로 구현하는 것이다.
기본적인 메소드인 get(k), put(k, v), remove(k)를 수행하려면
키가 k인 항목을 찾는 간단한 스캔이 필요하다.
저희는 코드 조각 9.1의 맵 M에서 이러한 메소드를 수행하기 위한 의사 코드를 제공한다.
이 리스트 기반 맵 구현은 간단하지만 매우 작은 맵에만 효율적이다.
각 방법은 최악의 경우 전체 리스트를 검색하는 것을 포함하기 때문에
기본적인 메소드는 모두 n개의 항목이 있는 맵에서 O(n) 시간이 걸린다.
따라서 우리는 더 빠른 것을 원한다.
코드 조각 9.1 : 리스트 S를 가지는 기본적인 맵 메소드에 대한 알고리즘.
Algorithm get(k):
Input: A key k
Output: The value for key k in M, or null if there is no key k in M
for each position p in S.positions() do
if p.element().getKey() = k then
return p.element().getValue()
return null {there is no entry with key equal to k}
Algorithm put(k,v):
Input: A key-value pair (k, v)
Output: The old value associated with key k in M, or null if k is new
for each position p in S.positions() do
if p.element().getKey() = k then
t ← p.element().getValue()
B.set(p, (k, v))
return t { return the old value}
S.addLast((k, v))
n ← n + 1 {increment variable storing number of entries}
return null {there was no previous entry with key equal to k}
Algorithm remove(k):
Input: A key k
Output: The (removed) value for key k in M, or null if k is not in M
for each position p in S.positions() do
if p.element().getKey() = k then
t ← p.element().getValue()
S.remove(p)
n ← n - 1 {decrement variable storing number of entries}
return t { return the removed value}
return null {there is no entry with key equal to k}
9.2 해시 테이블
맵의 값들과 관련된 키들은 보통 그런 값들에 대한 "주소"로 간주된다.
그런 응용의 예로는 컴파일러의 심볼 테이블과 환경 변수의 레지스트리가 있다.
이런 두 구조는 각각의 이름이 변수의 종류와 값에 관한 속성들에 대한
"주소" 역할을 하는 심볼 이름들의 집합으로 구성된다.
그런 경우에 맵을 구현하는 가장 효율적인 방법 중 하나는
해시 테이블(hash table)을 사용하는 것이다.
앞으로 보게 되겠지만
n-엔트리 해시 테이블에서 맵 연산의 최악의 실행 시간은 O(n)이지만,
해시 테이블은 보통 예상 시간 O(1) 안에 이런 연산을 수행할 수 있다.
일반적으로 해시 테이블은
버킷 배열(bucket array)과 해시 함수(hash function)의
두 가지 주요 구성 요소로 구성된다.
9.2.1 버킷 배열
해시 테이블의 버킷 배열(bucket array):
크기가 N인 배열 A이며,
A의 각 셀 = "버킷" (즉, 키-값 쌍들의 집합)
정수 N = 배열의 용량(capacity)
만약 키가 [0,N - 1] 범위에 잘 분포된 정수라면, 이 버킷 배열로 충분하다.
키가 k인 엔트리 e는 단순히 버킷 A[k]에 삽입된다. (그림 9.2 참조)
공간을 절약하려면 빈 버킷을 null 객체로 대체할 수 있다.
그림 9.2:
(1,D), (3,C), (3,F), (3,Z), (6,A), (6,C) 및 (7Q) 항목에 대한 크기 11의 버킷 배열,
키가 [0,N - 1] 범위의 고유한 정수이면
각 버킷은 최대 한 개의 항목을 유지한다.
따라서 버킷 배열에서 검색, 삽입 및 제거에는 O(1) 시간이 걸린다.
버킷 배열의 단점
1. 사용된 공간은 N에 비례한다.
따라서 N이 맵에 실제로 존재하는 항목 n보다 훨씬 크다면 공간 낭비가 있다.
2. 키가 [0, N - 1] 범위의 정수여야 한다는 것인데, 그렇지 않은 경우가 많다.
이 두 가지 단점 때문에
버킷 배열을 키에서 [0, N - 1] 범위의 정수로의 "좋은" 매핑과 함께 사용한다.
9.2.2 해시 함수
해시 테이블 구조의 해시 함수(hash function):
함수 h는 우리 맵의 각 키 k를 [0,N - 1] 범위의 정수로 매핑한다.
N = 이 테이블에 대한 버킷 배열의 용량
그런 해시 함수 h를 갖춘 우리는 임의의 키에 버킷 배열 방법을 적용할 수 있다.
이 접근법의 주된 아이디어는
(버킷 배열 인덱스로 사용하기에는 부적합할 가능성이 가장 높은) 키 k 대신
해시 함수 값 h(k)를 버킷 배열 A의 인덱스로 사용하는 것이다.
즉, 우리는 버킷 A[h(k)]에 항목 (k, v)를 저장한다.
해시 값이 같은 키가 2개 이상일 경우
A의 동일한 버킷에 두 개의 다른 항목이 매핑된다.
= 충돌(collision)이 발생했다
분명히 A의 각 버킷이 하나의 항목만 저장할 수 있다면,
우리는 하나의 버킷에 둘 이상의 항목을 연결할 수 없으므로
충돌의 경우 문제가 된다.
물론 충돌을 처리하는 방법도 있지만,
가장 좋은 전략은 우선 충돌을 피하려고 하는 것이다.
우리는 해시 함수가 가능한 한 충돌을 최소화하기 위해
맵의 키를 매핑하면 "좋다"고 말한다.
현실적인 이유로, 우리는 또한 해시 함수가 빠르고 계산하기 쉽기를 원한다.
자바의 관례에 따라 해시 함수 h(k)에 대한 평가는
키 k를 해시 코드(hash code)라고 하는 정수에 매핑하고
해시 코드를 압축 함수(compression function)라고 하는
버킷 배열의 인덱스 범위([0,N - 1]) 내의 정수에 매핑하는
두 가지 연산으로 구성된다고 된다(그림 9.3 참조)
그림 9.3: 해시 함수의 두 부분, 즉 해시 코드와 압축 함수.
9.2.3 해시 코드
해시 함수가 수행하는 첫 번째 작업은
임의의 키 k를 맵에서 가져와서 정수 값을 할당하는 것이다.
k에 대한 해시 코드(hash code) = 키 k에 할당된 정수
이 정수 값은 [0, N - 1] 범위에 있을 필요는 없으며
심지어 음수일 수도 있지만
키에 할당된 해시 코드 집합은 가능한 한 충돌을 피해야 한다.
키의 해시 코드가 충돌을 일으키면
압축 함수가 이를 피할 수 없기 때문이다.
또한 모든 키와 일치하려면
키 k에 사용하는 해시 코드는 k와 동일한 키의 해시 코드와 같아야 한다.
자바의 해시 코드
자바에 정의된 일반적인 Object 클래스는
각 개체 인스턴스를 해당 개체의 "표현"인 정수에 매핑하는
기본 hashCode() 메소드와 함께 제공된다.
구체적으로 hashCode() 메소드는 int형의 32비트 정수를 반환한다.
이 메소드는 특별히 무시되지 않는 한
자바 프로그램에서 사용되는 모든 객체에서 상속된다.
그러나 이것은 단지 메모리에서 객체의 위치를 정수로 해석하는 것일 수 있기 때문에
기본 Object 버전의 hashCode()를 사용할 때 주의해야 한다.
예를 들어, 메모리에 있는 두 개의 서로 다른 문자열 객체가
실제로 동일할 수 있기 때문에
이러한 타입의 해시 코드는 문자열과 잘 작동하지 않는다.
실제로 Java String 클래스는
Object 클래스의 hashCode 메소드를 문자열에 더 적합한 것으로 재정의한다.
마찬가지로 특정 개체를 맵에서 키로 사용하려면
이러한 개체에 대해 내장된 hashCode() 메소드를 재정의하고
이러한 타입의 개체에 잘 분산되고 일관된 정수를 할당하는 매핑으로 대체해야 한다.
그런 다음 몇 가지 일반적인 데이터 타입과
이러한 타입의 개체에 해시 코드를 할당하는 몇 가지 예제 메소드를 고려해 보겠다.
정수로 캐스팅
우선, 우리는 우리의 정수 해시 코드들만큼의 비트들을 사용하여 표현되는
임의의 데이터 타입 X에 대하여,
우리는 단순히 그 비트들의 정수 해석을
X에 대한 해시 코드로 받아들일 수 있다는 것에 주목한다.
따라서 자바 기본 타입 byte, short, int, char에 대하여,
우리는 이 타입을 int로 캐스팅하는 것만으로 좋은 해시 코드를 얻을 수 있다.
마찬가지로, 기본 float형의 변수 x에 대하여,
우리는 Float.floatToIntBits(x)에 대한 호출을 사용하여
x를 정수로 변환한 다음,
이 정수를 x의 해시 코드로 사용할 수 있다.
성분 합하기
비트 표현이 해시 코드의 double인
long이나 double 같은 기본형의 경우에는
위의 방식을 바로 적용할 수는 없다.
그래도 하나의 가능한 해시 코드,
그리고 실제로 많은 자바 구현에서 사용되는 것은
단순히 형식의 (long) 정수 표현을 해시 코드 크기의 정수로 캐스트하는 것이다.
물론 이 해시 코드는 원래 값에 있는 정보의 절반을 무시하는 것이며,
만약 우리 맵에 있는 많은 키들이 이 비트들만 다를 경우에는
이 간단한 해시 코드를 사용하여 충돌할 것이다.
그런 다음 모든 원래 비트를 고려하는 대안적인 해시 코드는
높은 차수의 비트들의 정수 표현과
낮은 차수의 비트들의 정수 표현을 합하는 것이다.
이런 해시 코드는 자바로 다음과 같이 작성할 수 있다:
static int hashCode(long i) {return(int)(i >> 32) + (int) i;}
//여기부터
실제로 성분의 합은 이진법을
정수의 k-튜플(x0,x1,...,xk_1)로 볼 수 있는 모든 대상 x로 확장할 수 있는데,
이는 x에 대한 해시 코드를 다음과 같이 형성할 수 있기 때문이다.
예를 들어 임의의 부동소수점 수가 주어졌을 때 가수와 지수를 합하여
long 정수들에 대한 해시 코드를 그 결과에 적용할 수 있다.
다항식 해시 코드
위에서 설명한 해시 코드의 합은
xi의 순서가 의미 있는 형태(x0,x1,...,xk-1)의 튜플로 볼 수 있는
문자열이나 다른 가변 길이 객체에는 좋은 선택이 아니다.
예를 들어 s에 있는 문자의 ASCII(또는 유니코드) 값을 합산하는
문자열에 대한 해시 코드를 생각해 보자.
이 해시 코드는 유감스럽게도
공통 문자열 그룹에 대해 원하지 않는 충돌을 많이 생성한다.
특히 temp01과 temp10은 이 함수를 사용하여
"stop", "top", "pots", "spot"과 같이 충돌한다.
더 나은 해시 코드는 어떻게든 xi의 위치를 고려해야 한다.
이를 정확하게 수행하는 대안적인 해시 코드는
0이 아닌 상수인 a≠1을 선택하여
값을 해시 코드로 사용하는 것이다
x0 ak_1+ x1 ak_2 + ...+ xk_2 a + xk_1.
수학적으로 말하면, 이것은 단순히 a에서의 다항식으로,
어떤 대상 x의 성분 (x0,x1,...,xk_1)을 그 계수로 삼는다.
따라서 이 해시 코드를 다항식 해시 코드(polynomial hash code)라고 부른다.
호너의 규칙 (연습 C-4.11 참조)에 의해,
이 다항식은 다음과 같이 쓸 수 있다
xk_1 + a(xk_2 + a(xk_3 + ... + a(x2 + a(x1 + ax0))...)).
직관적으로, 다항식 해시 코드는
이전 구성 요소의 특성화를 보존하는 동시에
값의 튜플에서 각 구성 요소에 대한 "방 만들기"의 방법으로
상수 a에 대한 곱셈을 사용한다.
물론 일반적인 컴퓨터에서 다항식의 평가는
해시 코드의 유한 비트 표현을 사용하기 때문에
그 값은 주기적으로 정수에 사용된 비트를 넘치게 된다.
우리는 다른 키에 대해서도
객체 x가 잘 퍼지는 것에 더 관심이 있기 때문에
그런 오버플로우는 그냥 무시한다.
그래도 우리는 그런 오버플로우가 일어나고 있다는 것을 염두에 두고
상수 a를 선택해서 0이 아닌 낮은 차항의 비트들을 가지고 있어서
우리가 오버플로우 상황에 처해 있을 때도
정보 내용의 일부를 보존하는 역할을 할 것이다.
우리는 영어단어인 문자열을 다룰 때
33, 37, 39, 41이 a에 특히 좋은 선택임을 시사하는
실험적 연구를 수행했다.
실제로 유닉스의 두 가지 변형에서 제공되는
단어 리스트의 결합으로 형성된 50,000개 이상의 영어단어 리스트에서
우리는 a를 33, 37, 39, 41로 하면
각각의 경우에 7개 미만의 충돌이 발생한다는 것을 발견했다.
그렇다면 자바 구현의 많은 경우
a에 대한 상수 중 하나를 사용하여
다항식 해시함수를 문자열의 기본 해시코드로 선택한다는 사실은 놀랄 일이 아니다.
그러나 속도의 문제로 인해 몇몇 자바 구현은
긴 문자열에 있는 문자 중 일부에만 다항식 해시함수를 적용한다.
순환 쉬프트 해시 코드
다항식 해시 코드의 변형은
곱하기 a를 부분합의 순환 이동을 특정 비트 수로 대체한다.
자바의 문자열에 적용되는 그런 함수는 예를 들어 다음과 같다:
static int hashCode(String s) {
int h=0;
for (int i=0; i<s.length (); i++) {
h = (h < 5) | (h >> 27); // 실행 합의 5비트 순환 쉬프트
h + = (int) s.charAt(i); // 다음 문자 추가
}
return h;
}
전통적인 다항식 해시 코드와 마찬가지로
순환 쉬프트 해시 코드를 사용하려면
약간의 미세 조정이 필요하다.
이 경우 우리는 각 새 문자에 대해 쉬프트할 양을 현명하게 선택해야 한다.
표 9.2에서는 다양한 쉬프트 양에 대한 충돌 수를 비교하는
25,000개가 조금 넘는 영어 단어 리스트에 대한
몇 가지 실험 결과를 보여준다.
이전 실험과 상수 a 또는 쉬프트 값을 현명하게 선택하면
다항식 해시 코드 또는 순환 쉬프트 변형은
튜플의 순서가 중요한 튜플로 쓸 수 있는
모든 객체(x0,x1,...,xk1)에 적합하다는 것을 보여준다.
표 9.2: 25,000개가 조금 넘는 영어 단어 리스트에 적용된
다항식 해시 코드의 순환 쉬프트 변형에 대한 충돌 거동 비교.
"Total" 열은 전체 충돌 수를 기록하고
"Max" 열은 어느 하나의 해시 코드에 대한 최대 충돌 수를 기록한다.
순환 쉬프트가 0이면 이 해시 코드는
단순히 모든 문자를 합산하는 코드로 되돌아간다.
| Collisions Shift | Total Collisions | Max Collision |
| 0 | 23739 | 86 |
| 1 | 10517 | 21 |
| 2 | 2254 | 6 |
| 3 | 448 | 3 |
| 4 | 89 | 2 |
| 5 | 4 | 2 |
| 6 | 6 | 2 |
| 7 | 14 | 2 |
| 8 | 105 | 2 |
| 9 | 18 | 2 |
| 10 | 277 | 3 |
| 11 | 453 | 4 |
| 12 | 43 | 2 |
| 13 | 13 | 2 |
| 14 | 135 | 3 |
| 15 | 1082 | 6 |
| 16 | 8760 | 9 |
9.2.4 압축 기능
키 k에 대한 해시 코드는
일반적으로 버킷 배열 A의 법적 인덱스 범위를 초과하므로
버킷 배열과 함께 즉시 사용하기에는 적합하지 않다.
즉, 인덱스가 음수이거나 A의 용량을 초과하기 때문에
해시 코드를 버킷 배열에 인덱스로 잘못 사용하면
배열의 경계 이탈 예외가 발생할 수 있다.
따라서 키 객체 k에 대한 정수 해시 코드를 결정한 후에는
해당 정수를 [0,N - 1] 범위로 매핑하는 문제가 여전히 남아 있다.
이 매핑은 해시 함수가 수행하는 두 번째 작업이며,
좋은 압축 함수는
주어진 해시 코드 집합에서 발생할 수 있는 충돌 수를 최소화하는 작업이다.
나눗셈 메소드
한 가지 간단한 압축 함수(compression function)는
나눗셈 메소드(division method)으로
정수 i를
|i| mod N
으로 매핑하는데,
이때 버킷 배열의 크기인 N은 고정된 양의 정수이다.
추가적으로 N을 소수로 하면 이 압축 함수는
해시 값의 분포를 "퍼뜨리는" 데 도움이 된다.
실제로 N이 소수가 아니라면,
해시 코드 분포의 패턴이 해시 값의 분포에서 반복되어
충돌이 일어날 가능성이 더 높다.
예를 들어,
만약 해시 코드가 {200,205,210,215,220,...,600}인 키를
크기가 100인 버킷 배열에 넣으면,
각각의 해시 코드는 다른 세 개와 충돌하게 된다.
그러나 만약 크기가 101인 버킷 배열을 사용한다면
충돌은 일어나지 않을 것이다.
해시 함수가 잘 선택되었다면,
서로 다른 두 키가 같은 버킷에 해시될 확률이 1/N임을 보장해야 한다.
N을 소수로 선택하는 것만으로는 항상 충분하지 않지만,
pN + q 형태의 해시 코드가
여러 개의 다른 p에 대해 반복되는 패턴을 가진다면
충돌은 계속 발생할 것이다.
MAD 메소드
정수 키 집합에서
반복되는 패턴을 제거하는 데 도움이 되는 더 정교한 압축 함수는
다중 덧셈과 나눗셈(multiply add and divide 또는 "MAD") 메소드이다.
이 메소드는 정수 i를
|ai + b| mod N
에 매핑하고, N은 소수이며,
a > 0(스케일링 팩터(scaling factor)라고 함)과 b ≥ 0(시프트(shift)라고 함)은
a mod N ≠ 0이 되도록 압축 함수가 결정될 때 무작위로 선택된 정수 상수이다.
이 압축 함수는 해시 코드 집합에서 반복되는 패턴을 제거하고 "좋은" 해시 함수,
즉 서로 다른 두 키가 충돌할 확률이 1/N이 되도록 접근하기 위해 선택된다.
만약 이 키들이 무작위로 A로 균일하게 "던져졌다"면
이 좋은 동작은 우리가 했을 것과 같을 것이다.
[0,N - 1] 범위에서 상당히 균일하게 정수를 퍼뜨리는 이와 같은 압축 함수와
우리 맵의 키를 정수로 변환하는 해시 코드로
효과적인 해시 함수를 가지고 있다.
이와 같은 해시 함수와 버킷 배열은
맵 ADT의 해시 테이블 구현의 주요 구성 요소를 함께 정의한다.
그러나 put, get 및 remove와 같은 연산을 수행하는 메소드에 대한 세부 정보를 제공하기 전에
충돌을 처리하는 방법에 대한 문제를 먼저 해결해야 한다.
9.2.5 충돌 처리 방법
해시 테이블의 주된 아이디어는 버킷 배열 A와 해시 함수 h를 가져와서
"버킷" "A[h(k)]"에 각각의 엔트리(k,v)를 저장하여 맵을 구현하는 것이다.
그러나 k1과 k2, 즉 h(k1) = h(k2)와 같은 두 개의 서로 다른 키가 있으면
이 간단한 아이디어는 어렵다.
그러한 충돌이 존재하기 때문에
단순히 버킷 A[h(k)]에 새로운 엔트리(k,v)를 직접 삽입하는 것은 불가능하다.
또한 get(k), put(k,v), remove(k) 연산을 수행하는 과정을 복잡하게 만든다.
분리된 체이닝
충돌을 처리하기 위한 간단하고 효율적인 방법은
9.1.1절에 설명된 대로
각 버킷 A[i]가 리스트를 사용하여
구현된 작은 맵 Mi를 저장하고
h(k) = i와 같은 항목 (k, v)를 보유하는 것이다.
즉, 각 개별 Mi는 연결 리스트에서 i를 인덱싱하기 위해
해시되는 항목을 함께 연결한다.
이 충돌 해결(collision resolution) 규칙을 분리된 체이닝(separate chaining)이라고 한다.
각 버킷 A[i]를 빈 리스트 기반 맵으로 초기화한다고 가정하면
코드 조각 9.2와 같이 기본 맵 작업을 수행하기 위해
분리된 체이닝 규칙을 쉽게 사용할 수 있다.
코드 조각 9.2: 맵 ADT의 기본적인 방법으로,
n개의 엔트리 간의 충돌을 해결하기 위해
분리된 체이닝(chaining)을 사용하는 해시 테이블(hash table)로 구현된다.
Algorithm get(k):
Output: The value associated with the key k in the map, or null if there is no
entry with key equal to k in the map
return A[h(k)].get(k) {delegate the get to the list-based map at A[h(k)]}
Algorithm put(k,v):
Output: If there is an existing entry in our map with key equal to k, then we
return its value (replacing it with v); otherwise, we return null
t ← A[h(k)].put(k,v) {delegate the put to the list-based map at A[h(k)]}
if t = null then {k is a new key}
n ← n + 1
return t
Algorithm remove(k):
Output: The (removed) value associated with key k in the map, or null if there
is no entry with key equal to k in the map
t ← A[h(k)].remove(k,v) {delegate the remove to the list-based map at A[h(k)]}
if t ≠ null then {k was found}
n ← n - 1
return t
키 k를 포함하는 각 기본 맵 연산에 대해 별도의 체인 방식은
A [h(k)]에 저장된 축소 리스트 기반 맵에 이 작업의 처리를 위임한다.
put(k, v):
k와 같은 키를 가진 엔트리를 찾기 위해 이 리스트를 스캔한다.
만약 하나를 찾으면 값을 v로 바꾸고,
그렇지 않으면 이 리스트의 끝에 (k, v)를 넣는다.
get(k):
끝에 도달할 때까지
이 리스트를 검색하거나 k와 같은 키를 가진 엔트리를 찾을 것이다.
remove(k):
유사한 검색을 수행하지만,
발견된 후에는 추가적으로 엔트리를 제거한다.
해시 함수의 확산 속성이 각 버킷 리스트를 작게 유지하는 데 도움이 되기 때문에
이 간단한 리스트 기반 접근 방식으로 "비켜라"고 할 수 있다.
실제로 좋은 해시 함수는 충돌을 가능한 한 최소화하려고 노력할 것이며,
이는 대부분의 버킷이 비어 있거나 단일 엔트리만 저장한다는 것을 의미한다.
이 관찰을 통해 구현을 약간 변경할 수 있으므로
버킷 A[i]가 비어 있으면 널(null)을 저장하고
A[i]가 단일 항목(k,v)만 저장하면
하나의 항목만 포함하는 리스트 기반 맵이 아니라
A[i]가 항목(k,v)을 바로 가리키게 할 수 있다.
그림 9.4에서는 별도의 체인이 있는 해시 테이블의 예를 보여준다.
좋은 해시 함수를 사용하여
용량 N의 버킷 배열에 있는 맵의 n개의 항목을 색인화한다고 가정하면,
각 버킷의 크기
= n/N
= 해시 테이블의 부하율(load factor) < 1
(부하율은 δ라고 정의된다.)
예를 들어, 좋은 해시 함수가 주어졌을 때,
이 함수를 사용하는 해시 테이블로 구현된 맵에서 연산의 예상 실행 시간은 O(n/N)이다.
따라서, n이 O(N)이면 O(1) 예상 시간에 실행할 수 있다.
그림 9.4: 크기 13의 해시 테이블로,
정수 키로 10개의 항목을 저장하고 충돌은 별도의 체인 방식으로 해결된다.
압축 함수는 h(k) = k mod 13이다.
단순화를 위해 키와 관련된 값은 보여주지 않는다.
개방 주소법
분리된 체이닝 규칙은 맵 연산을 간단히 구현할 수 있는 등 많은 좋은 속성을 가지고 있지만,
그럼에도 불구하고 충돌하는 키로 엔트리를 보유하려면
보조 자료 구조(리스트)를 사용해야 한다는 한 가지 단점이 있다.
그러나 분리된 체이닝 규칙을 사용하는 것 외에도
충돌을 처리할 수 있는 다른 방법이 있다.
특히 공간이 프리미엄인 경우
(예를 들어 소형 핸드헬드 장치용 프로그램을 작성하는 경우),
항상 각 엔트리를 버킷에 직접 저장하는 대안적인 접근법을 사용할 수 있다.
이 접근법은 보조 구조를 사용하지 않기 때문에 공간을 절약하지만
충돌을 처리하려면 조금 더 복잡해야 한다.
이 접근법에는 여러 가지 변형이 있으며,
집합적으로 개방 주소법(open addressing)이라고 하며, 다음에 논의한다.
개방 주소법을 사용하려면 부하율이 항상 최대 1이어야 하며,
항목은 버킷 배열 자체의 셀에 직접 저장되어야 한다.
선형 탐사
충돌 처리를 위한 간단한 열린 주소 지정 방법은 선형 탐사(linear probing)이다.
이 방법으로, 만약 이미 사용된 버킷 A[i]에 (k, v)를 삽입하려고 하면,
i = h(k)인 다음 A[(i + 1) mod N]에서 다음을 시도한다.
A[(i + 1) mod N]도 사용되면,
새로운 입력을 수용할 수 있는 빈 버킷을 찾을 때까지
A[(i + 2) mod N]을 시도한다.
일단 버킷이 위치하면, 우리는 거기에 단순히 입력을 삽입한다.
물론 이 충돌 해결 전략은 get(k, v) 연산의 구현을 변경해야 한다.
특히 이러한 검색을 수행하고 교체 또는 삽입을 수행하려면
키가 k인 항목을 찾거나
빈 버킷을 찾을 때까지 A [h(k)]부터 연속된 버킷을 검사해야 한다.
(그림 9.5 참조) "선형 탐사"이라는 이름은
버킷 배열의 셀에 접근하는 것이
"탐사"로 볼 수 있다는 사실에서 비롯되었다.
그림 9.5: 선형 탐사를 사용하여
정수 키를 가진 해시 테이블에 삽입한다.
해시 함수는 h(k) = k mod 11이다.
키와 관련된 값은 표시되지 않는다.
remove(k)를 구현하려면
처음에는 키 k가 있는 항목이 삽입되지 않은 것처럼 보이기 위해
상당한 양의 항목 이동을 수행해야 한다고 생각할 수 있으며,
이는 매우 복잡할 것이다.
이 어려움을 해결하는 일반적인 방법은
삭제된 항목을 특수 "사용 가능한" 마커 개체로 대체하는 것이다.
해시 테이블에 이 특수 마커가 버킷을 차지할 수 있으므로
remove(k) 또는 get(k)에 대한 탐색 알고리즘을 수정하여
키 k를 검색하는 것이 사용 가능한 마커가 포함된 셀을 건너뛰고
원하는 항목이나 빈 버킷에 도달할 때까지 계속 탐색한다
(또는 시작한 곳으로 돌아갈 수 있음).
또한 put(k,v)에 대한 알고리즘은
k를 검색하는 동안 발생한 사용 가능한 셀을 기억해야 한다.
따라서 선형 탐사는 공간을 절약하지만 제거를 복잡하게 만든다.
사용 가능한 마커 객체를 사용하더라도 선형 탐사는 추가적인 단점을 겪는다.
맵의 항목을 연속 실행으로 군집화하는 경향이 있으며,
이는 심지어 겹칠 수도 있다
(특히 해시 테이블의 셀 중 절반 이상이 점유된 경우).
이렇게 점유된 해시 셀의 연속 실행은 검색 속도를 상당히 늦춘다.
이차 탐사
이차 탐사(quadratic probing)라고 알려진 또 다른 개방 주소법 전략은
빈 버킷을 찾을 때까지 버킷 A[(i + f (j)) mod N]를 j = 0,1,2,...에 대해 반복적으로 시도하는 것이다.
선형 탐사와 마찬가지로
이차 탐사 전략은 제거 연산을 복잡하게 하지만
선형 탐사에서 발생하는 클러스터링 패턴의 종류를 피한다.
그럼에도 불구하고
이차 클러스터링(secondary clustering)이라고 하는
고유한 종류의 클러스터링을 생성하는데,
여기서 채워진 배열 셀 집합은 고정된 패턴으로
배열 주위에서 "튕겨 나간다".
N이 소수로 선택되지 않으면
이차 탐사 전략은 A에 빈 버킷이 존재하더라도 찾지 못할 수 있다.
실제로 N이 소수라고 하더라도
버킷 배열이 절반 이상 차면
이 전략은 빈 슬롯을 찾지 못할 수 있다.
이중 해싱
이중 해싱(double hashing) 전략은
선형 프로빙에 의해 생성된 종류 또는
이차 프로빙에 의해 생성된 종류의 클러스터링을
야기하지 않는 또 다른 개방 주소법 전략이다.
이 방법에서는 보조 해시 함수 h ′을 선택하고,
만약 h가 일부 키 k를 버킷 A[i]에 이미 사용된 i = h(k)인 경우
버킷 A[(i + f(j)) mod N]을 반복적으로 시도한다.
다음으로 j = 1,2,3,...에 대해 f (j) = j. h ′(k)이다.
이 방식에서는 보조 해시 함수를 0으로 평가할 수 없다.
일반적인 선택은 어떤 소수 q < N에 대해 h ′(k) = q - (k mod q)이다.
또한 N은 소수여야 한다.
또한 가능한 한 클러스터링을 최소화하려고 시도하는
보조 해시 함수를 선택해야 한다.
이러한 개방 주소법 방식은 별도의 체인 방식에 비해
약간의 공간을 절약하지만 반드시 빠른 것은 아니다.
실험 및 이론 분석에서 체인 방식은
버킷 배열의 부하율에 따라
경쟁력이 있거나 다른 방식보다 빠르다.
따라서 메모리 공간이 큰 문제가 아니라면
선택한 충돌 처리 방법은 별도의 체인 방식인 것 같다.
그럼에도 불구하고,
저희의 탐색 전략이 개방 주소법에서 발생할 수 있는 클러스터링을 최소화한다면
이러한 개방 주소법 방식 중 하나를 구현할 가치가 있을 수 있다.
9.2.6 Java 해시 테이블 구현
코드 조각 9.3-9.5에서는 충돌을 해결하기 위해
선형 탐사가 있는 해시 테이블을 사용하여
맵 ADT를 구현하는 클래스인 HashTableMap을 보여준다.
이러한 코드 조각에는
연습(R-9.10)으로 남기는 메소드 values()과 entries()을 제외한
맵 ADT의 전체 구현이 포함된다.
Java 클래스 HashTableMap의 주요 설계 요소는 다음과 같다:
• 예를 들어, 우리는 지도의 크기, n, 버킷 배열, A, 그리고 A의 용량, N을 유지한다.
• 우리는 내장 HashCode 메소드과 MAD(Multi-Add-Divide) 압축 함수를 통해
키의 해시 함수를 계산하기 위해 해시 값 메소드를 사용한다.
• 저희는 비활성화된 항목에 대한 마커로 센티넬, AVAILABLE을 정의한다.
• 버킷 배열의 초기 용량을 지정할 수 있는 선택적 구성 요소를 제공한다.
• 현재 버킷 배열이 꽉 찼을 때 새 항목을 삽입하려고 하면
전체 내용을 이전 버전의 두 배 크기인 새 배열로 해시한다.
• 다음과 같은 (보호된) 보조 메소드 사용된다:
checkKey(k):
키 k가 유효한지 확인한다.
이 메소드는 현재 k가 null이 아닌 것만 확인하지만
HashTableMap을 확장하는 클래스는
더 정교한 테스트로 이 메소드를 재정의할 수 있다.
rehash():
랜덤 매개변수를 사용하여
새로운 MAD 해시 함수를 계산하고
두 배의 용량을 가진 새 배열로 항목을 다시 해시한다.
findEntry(k):
인덱스 A[h(k)]에서 시작하여 배열을 원형으로 통과하는
k와 같은 키를 가진 엔트리를 찾는다.
메소드가 그런 엔트리를 가진 셀을 찾으면
이 셀의 인덱스 i를 반환한다.
그렇지 않으면 -i-1을 반환한다.
여기서 i는 마지막 빈 셀 또는 사용 가능한 셀의 인덱스이다.
코드 조각 9.3:
선형 탐사가 있는 해시 테이블을 사용하여
맵 ADT를 구현하는 클래스 HashTableMap.
(코드 조각 9.4에서 계속)
/** A hash table with linear probing and the MAD hash function */
import java.util.Iterator;
public class HashTableMap<K,V> implements Map<K,V> {
public static class HashEntry<K,V> implements Entry<K,V> {
protected K key;
protected V value;
public HashEntry(K k,V v) { key = k; value = v; }
public V getValue() { return value; }
public K getKey() { return key;}
public V setValue(V val) {
V oldValue = value;
value = val;
return oldValue;
}
public boolean equals(Object o) {
HashEntry<K,V> ent;
try { ent = (HashEntry<K,V>) o; }
catch (ClassCastException ex) { retrun false; }
return (ent.getKey() == key) && (ent.getValue() == value);
}
}
protected Entry<K,V> AVAILABLE = new HashEntry<K,V>(null, null); // marker
protected int n = 0; // number of entries in the dictionary
protected int capicity; // capicity of the bucket array
protected Entry<K,V>[] bucket; // bucket array
protected int scale, shift; // the shift and scaling factors
/** Creates a hash table with initial capacity 1023. */
public HashTableMap() { this(1023); }
/** Creates a hash table with the given capacity. */
public HashTableMap(int cap) {
capicity = cap;
bucket = (Entry<K,V>[]) new Entry[capacity]; // safe cast
java.util.Random rand = new java.util.Random();
scale = rand.nextInt(capacity-1) + 1;
shift = rand.nextInt(capacity);
}
/** Determines wheter a key is valid */
protected void checkKey(K, k) {
if (k == null) throw new InvalidKeyException("Invalid key: null.");
}
/** Hash function applying MAD method to default hash code. */
public int hashValue(K key) {
return Math.abs(key.hashCode()*scale + shift) % capacity;
}
코드 조각 9.4:
선형 탐사가 있는 해시 테이블을 사용하여
맵 ADT를 구현하는 클래스 HashTableMap.
(코드 조각 9.5에서 계속)
/** Returns the number of entries in the hash table. */
public int size() { return n; }
/** Returns whether or not the table is empty. */
public boolean isEmpty() { return (n == 0); }
/** Returns an iterable object containing all of the keys. */
public Iterable<K> keys() {
PositionList<K> keys = new NodePositionList<K>();
for (int i = 0; i < capacity; i++)
if ((bucket[i] != null) && (bucket[i] != AVAILABLE))
keys.addLast(bucket[i].getKey());
return keys;
}
/** Helper search method - returns index of found key or -(a+1),
* where a is the index of the first empty or available slot found. */
protected int findEntry(K key) throws InvalidKeyException {
int avail = -1;
checkKey(key);
int i = hashValue(key);
int j = i;
do {
Entry<K,V> e = bucket[i];
if (e == null) {
if (avail < 0)
avail = i; // key is not in table
break;
}
if (key.equals(e.getKey())) // we have found our key
return i; // key found
if (e == AVAILABLE) { // bucket is deactivated
if (avail < 0)
avail = i; // remember that this slot is available
}
i = (i + 1) % capacity; // keep looking
} while (i != j);
return -(avail + 1); // first empty or available slot
}
/** Returns the value associated with a key. */
public V get (K key) throws InvalidKeyException {
int i = findEntry(key); // helper method for finding a key
if (i < 0) return null; // there is no value this key
return bucket[i].getValue(); //return the found value in this case
}
코드 조각 9.5:
클래스 HashTableMap 선형 탐사가 있는
해시 테이블을 사용하여 맵 ADT를 구현한다.
(코드 조각 9.4에서 계속됨)
위 목록의 values() 및 entries() 메소드는 keys()와 유사하므로 생략했다.
/** Put a key-value pair in the map, replacing previous one if it exists. */
public V put (K key, V value) throws InvalidKeyException {
int i = findEntry(key); // find the appropriate spot for this entry
if (i >= 0) // this key has a previous value
return((HashEntry<K,V>) bucket[i]).setValue(value); // set new value
if (n >= capacity/2) {
rehash(); // rehash to keep load factor <= 0.5
i = findEntry(key); // find again the appropriate spot for this entry
}
bucket[-i-1] = new HashEntry<K,V>(key, value); // convert to proper index
n++;
return null; // there was no previous value
}
/** Doubles the size of the hash table and rehashes all the entries. */
protected void rehash() {
capacity = 2*capacity;
Entry<K,V>[] old = bucket;
bucket = (Entry<K,V>[]) new Entry[capacity]; // new bucket is twice as big
java.util.Random rand = new java.util.Random();
scale = rand.nextInt(capacity-1)+1; // new hash scaling factor
shift = rand.nextInt(capacity); // new hash shifting factor
for (int i = 0; i < old.length; i++)
Entry<K,V> e = old[i];
if ((e != null) && (e != AVAILABLE)) // a valid entry
int j = -1 - findEntry(e.getKey());
bucket[j] = e;
}
}
}
/** Removes the key-value pair with a specified key. */
public V remove (K key) throws InvalidKeyException {
int i = findEntry(key); // find this key first
if (i < 0) return null; // nothing to remove
bucket[i] = AVAILABLE;
n--;
return toReturn;
}
}
9.2.7 부하율 및 재해시
위에서 설명한 해시 테이블 체계에서
부하율 X = n/N을 1 미만으로 유지해야 한다.
실험과 평균 사례 분석에 따르면
개방 주소법 체계의 경우 λ<' 0.5를 유지하고
별도의 체인 연결의 경우 X < 0.9를 유지해야 한다.
맵 ADT를 구현하는 내장 클래스 java.util.HashMap은
임계값 0.75를 기본 최대 부하율로 사용하고
부하율이 이를 초과할 때마다
(또는 선택적인 사용자 설정 부하율) 다시 해시한다.
0.75를 선택하면
별도의 체인 연결(java.util.HashMap에서 구현할 가능성이 있음)에 문제가 없지만
연습 C-9.9에서 살펴보듯이
λ ≥ 0.5에서 일부 개방 주소법 체계가 실패하기 시작할 수 있다.
해시의 평균 사례 분석에 대한 자세한 내용은 이 책의 범위를 벗어나지만
확률적 기반은 상당히 직관적이다.
해시 함수가 양호한 경우
항목이 버킷 배열의 N 셀에 균일하게 분포될 것으로 예상한다.
따라서 n개의 항목을 저장하려면
버킷에 포함된 예상 키 수는 n/N이며, n이 O(N)이면 O(1)이다.
별도의 체인을 사용하면 λ이 1에 매우 가까워짐에 따라
충돌 확률도 1에 가까워지므로
충돌이 발생할 확률은 1에 가까워지고
충돌이 발생하는 버킷의 선형 시간 리스트 기반 메소드로 되돌아가야 하기 때문에
작업에 오버헤드가 추가된다.
물론 최악의 경우 해시 함수가 좋지 않으면
모든 항목이 동일한 버킷에 매핑될 수 있으므로
모든 맵 작업에 대해 선형 시간 성능이 발생하지만 그럴 가능성은 낮다.
반면, 개방 주소법에서는
로드 팩터 λ이 0.5를 넘어 1에 가까워지기 시작하면
버킷 배열의 엔트리 클러스터도 증가하기 시작한다.
이러한 클러스터는 탐사 전략이 완료되기 전에
상당한 시간 동안 버킷 배열 "주위를 튕겨 나가게 한다".
따라서 부하율을 특정 임계값 이하로 유지하는 것은
오픈 어드레싱 방식에 매우 중요하며
별도의 체인 방식과도 관련이 있다.
해시 테이블의 부하율이 지정된 임계값을 크게 초과하면
테이블의 크기를 조정하고
(지정된 부하율을 다시 얻기 위해)
모든 객체를 이 새 테이블에 삽입해야 하는 것이 일반적이다.
새 테이블로 재해시(rehashing)할 때
새 배열의 크기는 이전 크기의 두 배 이상이어야 하는 것이 좋다.
일단 이 새로운 버킷 배열을 할당하면,
우리는 그것과 함께 사용할 새로운 해시 함수를 정의해야 하며,
아마도 새로운 매개변수를 계산할 것이다.
그런 다음 이 새로운 해시 함수를 사용하여
이전 배열의 모든 항목을 새 배열에 다시 삽입한다.
코드 조각 9.3-9.5에
주어진 선형 탐사를 포함하는 해시 테이블을 구현할 때
부하율을 0.5 이하로 유지하기 위해 재해싱을 사용한다.
주기적으로 재해시를 하더라도
해시 테이블은 맵을 구현하는 효율적인 수단이다.
실제로, 매번 재해시 작업을 할 때마다 테이블 크기를 두 배로 늘린다면,
테이블의 모든 항목을 애초에 삽입하는 데 사용된 시간에 비해
재해시하는 비용을 분할할 수 있다.
(섹션 6.1.4 참조)
각 재해시는 일반적으로 항목을 새 버킷 배열 전체에 흩뿌릴 것이다.
9.2.8 적용 : 단어 빈도 세기
해시 테이블을 사용하는 축소 사례 연구로서,
예를 들어 전문가들이 주제를 찾아
정치 연설을 연구할 때 발생하는 문서에서
서로 다른 단어의 출현 횟수를 세는 문제를 생각해 보자.
해시 테이블은 여기서 사용하기에 이상적인 자료 구조이다.
우리는 단어를 키로 사용하고
단어 수를 값으로 사용할 수 있기 때문이다.
우리는 코드 조각 9.6에서 그러한 응용을 보여준다.
코드 조각 9.6:
문서의 단어 빈도수를 세어
가장 빈도수가 높은 단어를 출력하는 프로그램이다.
Scanner 클래스를 사용하여 문서를 구문 분석하고,
토큰을 공백에서 문자가 아닌 것으로 구분하는 구분자를 변경한다.
또한 단어를 소문자로 변환한다.
import java.io.*;
import java.util.Scanner;
import net.datastructures.*;
/** A program that counts words in a document, printing th emost frequent. */
public class WordCount {
public static void main(String[] args) throws IOException {
Scanner doc = new Scanner(System.in);
doc.useDelimiter("[^a-zA-Z]"); // ignore non-letters
HashTableMap<String,Integer> h = new HashTableMap<String,Integer>();
String word;
Integer count;
while (doc.hasNext()) {
word = doc.next();
if (word.equals("")) continue; // ignore null strings between delimiters
word = word.toLowerCase(); // ignore case
count = h.get(word); // get the previous count for this word
if (count == null)
h.put(word, 1); // autoboxing allows this
else
h.put(word, ++count); // autoboxing /unboxing allows this
}
int maxCount = 0
String maxWord = "no word";
for (Entry<String,Integer> ent : h.entries()) { // find max-count word
if (ent.getValue() > maxCount) {
maxWord = ent.getKey();
maxCount = ent.getValue();
}
}
System.out.print("The most frequent word is \"" + maxWord);
System.out.println(",\" with word-count = " + maxCount + ".");
}
}'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 10장 탐색 트리(1) (1) | 2024.01.03 |
|---|---|
| 9장 맵과 딕셔너리(2) (1) | 2024.01.01 |
| 8장 우선순위 큐 (4) | 2023.12.31 |
| 7장 트리(2) (1) | 2023.12.30 |
| 7장 트리(1) (2) | 2023.12.29 |