Chapter 11 해쉬(Hash) SANGJI University Kwangman KO (kkman@sangji.ac.kr)

1. 해시의 기본 개념 해시(hash)의 특징 빠른 검색 방법의 일종 탐색시간을 줄이기 위함 자료가 저장되어 있는 위치에 한번에 접근할 수 있는 배열의 성질을 이용 자료 자체와 연관된 숫자를 만들어 낸 뒤 해시 테이블의 해당 위치에 자료를 저장 한 번에 테이블에 접근할 수 있으므로, 해시는 O(1)의 성능을 가짐

2. 해시 메소드 4, 8, 12, 16, 20, 24, 28, 32 해시 테이블 생성 해시 테이블 크기 설정. int hTableSize = 8; int[] hTable = new int[hTableSize]; 해시 메소드 구현 모듈러 연산자(%)를 적용하여 구성 data % hTableSize; data를 입력 받아 해시 테이블의 크기인 hTableSize로 모듈러 연산한 뒤 그 값을 반환 반환된 값 = 자료의 해시 값

삽입 해시 메소드 이용 해시 메소드에서 반환받은 해시 값을 이용해서 그 자료의 저장 위치를 판단 자료 20의 경우 해시 값은 20 % 8 = 4 자료가 저장되어야 할 위치에 이미 다른 자료가 저장되어 있는 현상을 충돌(collision) 이라고 함

충돌 감소 해시테이블의 크기를 소수(prime number)로 만들 수 있음 테이블의 크기를 소수로 구현한 해시 메소드 int hTableSize = 11; int[] hTable = new int[hTableSize]; int hFunc(int data, int hTableSize) {        return data % hTableSize; }

3. 자료를 숫자와 연관 특징 고유한 번호 주기 만약 자료가 숫자가 아니라면 ? 자료를 그와 관련된 숫자로 변환해야 함 자료와 관련된 숫자를 자료의 키(key). 고유한 번호 주기 주민등록번호나 학번과 같이 각 개체 당 고정된 크기의 고유한 번호를 부여할 수 있음 원하는 자료에 할당되어 있는 고유번호를 알아야만 그 자료에 접근할 수 있음

자료에서 숫자 추출 알파벳과 숫자 대응표 문자 숫자 a 1 j 10 s 19 b 2 k 11 t 20 c 3 l 12 u 21 d 4 m 13 v 22 e 5 n 14 w 23 f 6 o 15 x 24 g 7 p 16 y 25 h 8 q 17 z 26 i 9 r 18

호너의 방법(Horner's method) Hash 8, 1, 19, 8 이라는 숫자를 얻을 수 있음 단어에 대한 하나의 키값을 얻는 방법 8 * 263 + 1 * 262 + 19 * 261 + 8 * 260 = 141,78 숫자의 범위가 너무 커지지 않게, 모듈러(%) (8 * 263 + 1 * 262 + 19 * 261 + 8 * 260 ) % hTableSize 좀 더 효율적인 연산 (((8 * 26 + 1) * 26 + 19) * 26 + 8) % hTableSize

4. 충돌 해결 방법 개방 주소법 분리 연결법 배열로 이루어진 해시 테이블의 셀에 바로 자료를 넣는 방법 구현이 간단 충돌을 해결하는 방법이 복잡하고 충돌이 많이 일어나면 성능 저하 분리 연결법 해시 테이블의 셀을 연결 리스트의 헤더로 지정 충돌이 일어날 경우 추가되는 자료를 해당 리스트에 삽입 연결 리스트 구현, 개방 주소법에 비해서 상대적으로 복잡함

순차 탐색 순차 탐색(linear probing) 삽입 충돌이 일어나면 차례로 셀을 검사하여 빈 셀에 자료를 저장 탐색 시 원하는 자료를 찾기 힘듦 삽입 해시 테이블에 삽입할 자료를 입력받아서 hFunc() 메소드를 이용하여 해시 값을 알아낸 뒤, 그 해시 값에 해당하는 해시 테이블의 셀을 찾음 빈 셀이 없으면 다른 셀 탐색 클러스터(cluster) 비어있는 셀이 없이 값을 저장하고 있는 셀로 구성된 덩어리

탐색 자료가 원래 있어야 할 셀에서부터 시작해서 비어있는 셀이 나올 때까지 해시 테이블을 순차적으로 탐색 자료를 찾기 전에 빈 셀을 만나면 그 자료를 찾는 데 실패

삭제 탐색 방법 때문에 순차 탐색의 경우 자료를 삭제할 수 없음 실제로는 삭제하지 않고 삭제했다는 표시만 함

지수 탐색 지수 탐색(quaradic probing) 순차 탐색의 한계 클러스터의 크기가 커질 경우, 처음부터 순서대로 탐색하는 것과 비슷한 성능 빈 셀을 찾기 위해 지수적으로 빈 셀을 탐색 원하는 셀이 비어 있지 않을 경우 바로 다음 셀을 검사 4(=22)번째 셀 9(=32)번째 셀 16(=42)번째 셀 25(=52)번째 셀을 차례로 검사하는 방식 1, 4, 9 등의 숫자를 탐색 단위(step size)라고 함

지수 탐색의 단점 찾기 시작하는 셀이 같은 경우엔 탐색하는 순서가 동일함

이중 해싱 이중 해싱(double hashing) 지수탐색의 탐색 단위가 고정되어 있는 단점을 보완하기 위한 방법으로 제시 첫 번째 해싱 자료를 입력할 셀을 찾는 해싱 두 번째 해싱 첫 번째 해시 값이 충돌이 일어났을 경우에 탐색 단위를 계산하는 데 사용 탐색 단위는 절대 0이 되어서는 안됨 탐색 단위로 해시 테이블을 검색했을 때 테이블의 모든 셀에 접근할 수 있어야 함

두번째 해시 메소드 public int hFunc2(int key) { int f2val;      return f2val - (key % f2val) ; } 변수 f2val이 전체 해시 테이블 크기와 서로소일 경우 테이블의 모든 셀에 접근할 수 있음이 보장됨

이중 해싱 예 키 값 첫 번째 해시 값 두 번째 해시 메소드 23 1 5 7 - (23 % 7) 34 7 - (34 % 7) 45 4 7 - (45 % 7)

삽입 순차 검색의 insert() 메소드와 유사하며, 탐색 단위가 두 번째 해시 메소드인 hFunc2 메소드로 매 자료마다 결정됨 point 변수는 탐색 단위만큼씩 증가함 원하는 자료를 찾기 전에 해시 테이블의 크기보다 커지면 탐색 단위에 맞추어 해시 테이블의 처음 부분으로 돌아가 검사를 계속함 빈 셀이나 삭제 표시가 있는 셀을 발견하면, 그 자리에 자료를 삽입

탐색 삭제 탐색 단위가 각 자료마다 다르다는 것을 제외하고는 순차 탐색과 동일 순차 탐색에서 다음 부분을 변경 point++;    =>    point += hFunc2(key); 삭제 순차 탐색의 삭제 방법과 동일

분리 연결법 분리 연결법(separate chaining) 연결 리스트를 이용하므로 별도의 충돌 해결 방법을 갖지 않음 충돌이 일어나면 충돌이 일어난 셀의 리스트에 링크 추가 리스트의 마지막에 링크를 삽입하는 방법은 원하는 자료를 찾기위해 한 셀의 모든 리스트 검색 링크를 삽입할 때 리스트의 정렬을 유지하는 자리에 링크를 삽입하여 성능을 유지함

탐색 링크 자신의 키 값 보다 큰 값을 발견하거나 리스트의 끝에 도달했을 경우에 탐색에 실패함

삭제 링크 앞에 연결되어 있는 주소를 다른 링크의 주소로 변경