자료구조 with C/해시 테이블 (3) 썸네일형 리스트형 체이닝의 성능 향상 체이닝은 원하는 데이터를 찾기 위해 순차 탐색(링크드 리스트의 단점)을 해야한다 해시 테이블과 이진 탐색 트리 결합은 아주 훌륭한 선택 개방 주소법(Open Addressing) 충돌이 일어날 때 해시 함수에 의해 만들어진 주소가 아니더라도 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘 이중 해싱 클러스터를 방지하는 방법은 탐사할 주소의 규칙성을 없애는 것뿐 고로 해시 함수를 두 개 만들어서 충돌이 발생하면 다른 해시 함수에 넣어서 이동폭을 생성 재해싱 해시 테이블의 공간 사용률이 70~80%에 이르면 성능 저하가 나타남. 재해싱은 해시 테이블의 크기를 늘리고 늘어난 해시 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱 해시 테이블 (체이닝) 자릿수 접기 숫자의 각 자릿수를 더해 해시값을 만드는 것 문자열을 키로 사용하는 해시 테이블에 잘 어울림 (아스키 코드) 문자열에 사용되는 아스키 코드는 0 ~ 127 사이 값을 가짐 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int CHT_Hash( KeyType Key, int KeyLength, int TableSize ) { int i=0; int HashValue = 0; // 문자열의 각 요소를 ASCII 코드 번호로 변환하여 더한다 for ( i=0; iTableSize ); // 해싱한 주소에 있는 링크드 리스트를 가져온다. List TheList = HT->Table[Address]; List Target = NULL; if ( TheList == NULL ) .. 해시 테이블 (나눗셈법) 데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소에 데이터를 담는 것 1. 나눗셈법 주소 = 입력값 % 테이블의 크기 테이블의 크기를 n이라 하면 나누셈법은 0부터 n-1 사이의 주소 반환을 보장 일반적으로 나눗셈법을 효율적으로 사용하기 위해서는 테이블의 크기 n을 소수로 정하는 것이 좋음 특히 2의 제곱수와 거리가 멀면 좋음 1 2 3 4 5 6 7 8 9 10 11 typedef struct tagNode { KeyType Key; ValueType Value; } Node; typedef struct tagHashTable { int TableSize; Node* Table; } HashTable; cs Key는 주소로 사용할 데이터, .. 이전 1 다음