원소 접근법
1. 순차접근
- 연결리스트에 의한.
- 선형시간
2. 직접접근
- 배열에 의한
- 상수시간
- 인덱스 관련 사전지식 필요
해시테이블
인덱스 관련 사전지식 없이, 직접접근 가능!
How?
원소 내용을 입력, 인덱스를 출력으로 하는 해시함수 이용
레코드
- 여러 컴포넌트(이름+타입) 가진 자료구조
- 일부 언어에서는 레코드가 배열같은 표준 타입으로 사용
테이블
- 동일 타입의 레코드 집합(순서 x)
키 테이블
- 기본키 역할의 "키필드"를 레코드 타입이 포함하는 테이블
맵
- 보유 레코드의 컬렉션
| 각 ADT의 연산 | 키 레코드 | 맵 |
| Initialize | 키 보유 레코드 생성(초기화) | 공백 맵 생성(초기화) |
| key | 레코드 키 객체 반환 | |
| value | 레코드 값 객체 반환 | |
| update | 레코드 값 객체 대체 | 레코드 있으면 update |
| search | 테이블에서 해당 키 가진 레코드 탐색하여 값 반환 | |
| insert | 레코드 없으면 insert | |
| delete | 레코드 있으면 삭제 후 그 값 반환 | |
| count | 테이블 레코드 수 반환 |
선형 조사
해시테이블에서 충동 해결하는 가장 단순한 방법
충돌된 레코드를 배열의 가용한 다음 셀에 저장하기.
각 조사에서 배열 인덱스를 1씩 증가시키기에 선형조사 라고 함. 맨 뒤 인덱스에서 1 증가시 맨 앞으로 이동.
또, 해당 원소가 해시값에 의해 인덱스된 슬롯에 항상 배치되지는 않고, 테이블의 임의의 장소에서 끝날 수도 있기에 개방주소법 이라고도 함.
but, 문제가 있음.
기본 집중 ( 해시 함수가 테이블 전체에 대해 레코드를 균일하게 분배하는 데 실패하면 선형 조사는 함께 묶인 레코드의 긴 체인을 만듦 ) 문제 발생
- 순서대로 9개의 레코드를 삽입하면 충돌 엄청나게 발생. 이를 해결하려면 제곱 조사를 해야함.
제곱 조사
선형 조사는 매번 1씩 증가하면서 탐색하는데, 제곱 조사는 더 점진적으로 큰 폭으로 증가시켜 충돌을 해결한다.
충돌 횟수가 반으로 줄어든다.
-> 이유 : 선형 조사는 하나씩 탐색하면서 집중이 되지만, 제곱 조사는 중간에 사용이 안 된 갭을 남겨두어서 집중이 줄어든다.
but, 얘도 문제가 있음.
만약, 11개 셀 중에 6개 셀이 점유되고 5개 셀만 남아 비어있다고 해도 put()이 실패함.
이에 대한 해결책은, 임계 적재율을 50%로 설정하면 된다.
그치만 그래도 2차 집중(동일한 값으로 해시되는 2개의 서로 다른 키가 동일한 조사 순서를 갖게 됨)문제가 발생하는데, 이에 대한 해결책으로는 "이중 해싱"이 있다.
이중 해싱
조사 순서를 결정해주는 제 2의 독립적인 해시 함수 사용
제곱 조사와 마찬가지로 이중 해싱도 조사 순서를 넓게 확대해서 기본 집중을 피할 수 있다.
재해싱
더 큰 배열로 테이블을 재구축하기에, 오버플로 문제 해결 가능!
포화 상태에 이르기 전에 rehash() 호출하는 것이 좋은 전략!
그러려면 임계 크기를 설정해줘야 하는데, 임계값을 매번 설정해줄 수는 없으니,
" 최대 비율(적재율) " 을 이용할 수 있다.
n = size, m = entries.length 일 때, r = n/m 으로 설정한다.
이 비율의 상한값을 0.75 혹은 0.8 부근으로 설정하면,
만약 배열 길이가 11일 때 적재율이 0.75이다 --> size가 8.25를 초과하면(즉, 9번째 레코드가 삽입되면) rehash() 호출!
// 기존 배열보다 크기 2배인 배열로 이동
private void rehash(){
Entry[] oldEntries = entries;
Entries = new Entry[2*oldEntries.length + 1];
for(int k=0 ; k<oldEntreis.length ; k++){
Entry entry = oldEntries[k];
if(entry == null || entry == NIL) continue;
int h = hash(entry.key);
for(int i=0 ; i<entries.length ; i++){
int j = nextProbe(h, i);
if(entries[j] == null){
entries[j] = entry
break;
}
}
}
used = size;
}
9.7 별도 체인 (36p) 부터는.. 다음에
출처 : 충남대 김경섭교수님 수업자료
