해시 충돌 해결 - 데이터 구조

해시 충돌 해결
해시 충돌 을 해결 하 는 방법
응용 필드:
        폐 산열 과 의 응용 에 대해 우 리 는 간단 한 실례 를 들 수 있다. 함 수 를 잉여 법 으로 하 는 해시 함 수 를 제외 하고 해시 표를 구축 하면 잉여 값 이 같은 상황 을 만 날 수 있다. (예 를 들 어 두 개의 키 워드 는 각각 2, 1002 이 고 최대 범 위 는 1000 이 며 모드 를 제외 한 나머지 값 은 모두 2 이다. 이때 충돌 이 발생 한 것 과 같다) 바로 해시 충돌 이다.이번에 우 리 는 충돌 해결 방법 중의 폐 산열 을 토론 할 것 이다.폐 산열 은 삽입 가능 한 것 을 만족 시 키 는 전제 에서 충돌 이 발생 한 값 을 뒤로 찾 아 빈 위 치 를 찾 아 값 을 넣 고 이번 삽입 을 완성 하 는 것 이다.
        삽입 가능 한 상황: 전체 스 택 의 총 수량 을 삽입 하 는 비율 을 계산 하 는 것 을 부하 인자 라 고도 합 니 다.
코드 구현:
        산열 을 닫 고 닫 는 것 에 대해 우 리 는 그 실질, 즉 삽입 할 때 발생 하 는 몇 가지 상황 을 알 아야 한다. 데이터 가 있 고 데이터 가 없 으 며 삭 제 된 데이터 가 있다.데이터 와 데이터 가 없 는 두 가지 상황 에 대해 잘 이해 할 수 있 습 니 다. 그러면 여 기 는 삭 제 된 데 이 터 를 분석 합 니 다.삭 제 된 데 이 터 를 언급 하면 우 리 는 해시 표 의 조 회 를 생각해 야 한다. 해시 표 에 대한 조회 과정 에서 검색 한 값 에 대응 하 는 주소 가 비어 있 으 면 되 돌아 오 는 화 를 해 야 한다. 그러면 우리 가 전에 한 작업 (해시 충돌 처리) 은 의미 가 없 을 것 이다. 삽입 과정 에서 우 리 는 해시 충돌 을 피하 기 위해 서 이다.충돌 데 이 터 를 상응 하 게 처리 하 였 습 니 다 (예 를 들 어 '+ 1' 조회). 따라서 우 리 는 삭 제 된 데이터 라 는 상 태 를 도입 하여 뒤의 조회, 삭제 등에 영향 을 주지 않도록 해 야 합 니 다.
구조 체 코드:

typedef enum Stat { 
Empty, 
Valid, 
Deleted //          
} Stat; 

typedef struct HashElem { 
KeyType key; 
ValType value; 
Stat stat; //      stat              
} HashElem; 

해시 초기 화:
        1. 불법 입력 판단
        2. 구조 체 내 변 수 를 초기 화

void HashInit(HashTable* ht, HashFunc hash_func){
    if(ht == NULL){
        //    
        return;
    }  
    ht->size = 0;
    ht->func = hash_func;
    int i =0;
    for(;idata[i].stat = Empty;        
    }
    return;
} 

해시 삽입:
        1. 불법 입력 을 판단 하고 불법 으로 직접 되 돌아 가 며 반대로 계속 합 니 다.
        2. '만' 여 부 를 판단 하고 만 은 직접 돌아 가 며 반대로 계속 합 니 다.
        3. 해시 함 수 를 이용 하여 키 워드 를 분석 하고 해시 주 소 를 얻어 주소 상태 검 측 을 실시한다.
                a) 상 태 는 "데이터 상태" 가 아 닌 것 으로 삽입 작업 을 직접 진행 합 니 다.
                b)  상 태 는 '데이터 상태' 로 키 워드 를 + 1 처리 하고 해시 함 수 를 계속 호출 하여 해시 주 소 를 분석 합 니 다.
코드:

void HashInsert(HashTable* ht, KeyType key, ValType value){
    if(ht ==NULL||key<0){
        //    
        return;
    }
    if(ht->size> 0.8*HashMaxSize){
        //         
        return;
    }
    size_t offset = ht->func(key);
    while(1) {
        if(ht->data[offset].stat != Valid){
            ht->data[offset].key = key;
            ht->data[offset].value = value;
            ht->data[offset].stat = Valid;
            ++ht->size;
            return;
        }else if(ht->data[offset].stat == Valid&&ht->data[offset].key == key){
            //         key 
            return;
        }else{
            offset = (offset+1)%HashMaxSize;
        }
    }//while    
} 

해시 찾기:
        1. 불법 입력 을 판단 하고 불법 으로 직접 되 돌아 가 며 반대로 계속 합 니 다.
        2. '공' 여 부 를 판단 하고 공 으로 직접 돌아 가 며 반대로 계속 합 니 다.
        3. 해시 함 수 를 호출 하여 키 워드 를 분석 하고 해시 주 소 를 얻어 주소 상태 검 측
                a) 상 태 는 '데이터 없 는 상태' 로 되 돌아 가 고 반대로 계속 합 니 다.
                b) 상 태 는 '데이터 상태 가 있 는 상태' 가 아 닙 니 다. 키 워드 를 비교 하여 찾 았 습 니 다. 해당 하 는 값 을 되 돌려 주 고 꼬리 삽입 을 찾 아 + 1 작업 을 계속 합 니 다.
                c) 상 태 는 '삭 제 된 데이터 상태' 로 + 1 작업 을 계속 진행 합 니 다.
코드:

//   key,     key value. 
int HashFind(HashTable* ht, KeyType key, ValType* value){
    if(ht == NULL){
        //    
        return 0;
    }
    if(ht->size == 0){
        //     
        return 0;
    }
    size_t offset = ht->func(key);
    while(1){
        if(ht->data[offset].stat == Valid && ht->data[offset].key == key){
            *value = ht->data[offset].value;
            return 1;
        }else if(ht->data[offset].stat == Empty){
            return 0;
        }else{
            offset = (offset+1)%HashMaxSize;
        }
    }//while   
}

해시 삭제:
        삭제 작업 은 두 단계 로 나 누 어 진행 할 수 있 습 니 다. 첫째, 찾기 (방법 은 해시 찾기), 둘째, 삭제 (해당 해시 위치 에 있 는 상태 값 을 바 꿔 야 합 니 다).
코드:

void HashRemove(HashTable* ht, KeyType key){
    if(ht == NULL){
        //    
        return;
    } 
    KeyType offset = ht->func(key);
    while(1){
        if(ht->data[offset].stat == Valid && ht->data[offset].key == key){
            ht->data[offset].stat = Deleted;
            --ht->size;
            return;
        }else if(ht->data[offset].stat == Empty){
            return;
        }else{
            offset = (offset+1)%HashMaxSize;
        }
    }
}

해시 소각:
        1. 불법 입력 판단 하기;
        2. 구조 체 내용 수정
코드:

void HashDestroy(HashTable* ht){
    if(ht == NULL){
        //    
        return;
    }
    ht->size = 0;
    ht->func = NULL;
    return;
}