c 언어 구현 해시 표

해시 표 는 모두 데이터 구조 에서 배 웠 는데 가장 빠 른 데이터 구 조 를 찾 았 을 것 이다. 가장 좋 은 상황 에서 선형 시간 복잡 도 를 달성 할 수 있 을 것 이다.
우 리 는 c 언어 로 열 린 주 소 를 실현 하 는 해시 표, 즉 키 값 을 지정 하여 그의 해시 값 을 계산 합 니 다. 충돌 하면 다음 슬롯 (slot) 에서 찾 습 니 다.
키 키 의 상태 코드 가 VT 이면UNDEFINED 라면 이 슬롯 이 점용 되 지 않 았 거나 삭제 되 었 습 니 다.
값 value 의 상태 코드 는 VTTRUE 와 VTFALSE 두 가지, 이 슬롯 이 이미 점용 되 었 다 면 value 의 상태 코드 는 VT 입 니 다.TRUE
그래서 선형 탐 사 를 할 때
키 의 상태 코드 가 VT 이면UNDEFINED 및 value 의 상태 코드 는 VTTRUE 는 이 슬롯 정보 가 위조 삭제 되 었 음 을 나 타 냅 니 다. 하지만 탐지 체인 이 끊 어 지지 않 아 계속 탐지 할 수 있 습 니 다.
키 의 상태 코드 가 VT 이면UNDEFINED 및 value 의 상태 코드 는 VTFALSE 의 경우 이 슬롯 이 점용 되 지 않 았 고 현재 비어 있 음 을 나 타 냅 니 다.
다음은 objmap. h 코드

#ifndef _OBJECT_MAP_H
#define _OBJECT_MAP_H
#include "header_obj.h"

#define MAP_LOAD_PERCENT 0.8

typedef struct{
    Value key;
    Value value;
} Entry;    //key->value 

typedef struct{
    ObjHeader objHeader;
    uint32_t capacity;  //  Entry  
    uint32_t count;     //    Entry  
    Entry* entries;     //Entry  
} ObjMap;

ObjMap* newObjMap(VM* vm);

void mapSet(VM* vm, ObjMap* objMap, Value key, Value value);
Value mapGet(ObjMap* objMap, Value key);
void clearMap(VM* vm, ObjMap* objMap);
Value removeKey(VM* vm, ObjMap* objMap, Value key);
#endif

다음은 objmap. c 코드

//######part1 p128######
#include "obj_map.h"
#include "class.h"
#include "vm.h"
#include "obj_string.h"
#include "obj_range.h"

//   map  
ObjMap* newObjMap(VM* vm){
    ObjMap* objMap = ALLOCATE(vm, ObjMap);
    initObjHeader(vm, &objMap->objHeader, OT_MAP, vm->mapClass);
    objMap->capacity = objMap->count = 0;
    objMap->entries = NULL;
    return objMap;
}

//        
static uint32_t hashNum(double num){
    Bits64 bits64;
    bits64.num = num;
    return bits64.bits32[0] ^ bits64.bits32[1];     // 32  32   hash 
}

//        
static uint32_t hashObj(ObjHeader* objHeader){
    switch(objHeader->type){
        case OT_CLASS:  //  class    
            return hashString(((Class*)objHeader)->name->value.start,
                ((Class*)objHeader)->name->value.length);

        case OT_RANGE:  //  range     
            ObjRange* objRange = (ObjRange*)objHeader;
            return hashNum(objRange->from) ^ hashNum(objRange->to);
        case OT_STRING: //     ，     hashCode
            return ((ObjString*)objHeader)->hashCode;
        default:
            RUN_ERROR("the hashable are objstring, objrange and class.");
    }
    return 0;
}

//  value            
static uint32_t hashValue(Value value){
    switch(value.type){
        case VT_FALSE:
            return 0;
        case VT_NULL:
            return 1;
        case VT_NUM:
            return hashNum(value.num);
        case VT_TRUE:
            return 1;
        case VT_OBJ:
            return hashObj(value.objHeader);
        default:
            RUN_ERROR("unsupport type hashed!");
    }
    return 0;
}

//######part2 p129######
// entries   entry，     key   true
static bool addEntry(Entry* entries, uint32_t capacity, Value key, Value value){
    uint32_t index = hashValue(key) % capacity;

    //            slot
    while(true){
        //    slot，       key，      
        if(entries[index].key.type == VT_UNDEFINED){
            entries[index].key = key;
            entries[index].value = value;
            return true;    //  key   true
        }else if(valueIsEqual(entries[index].key, key)){    //     key，     
            entries[index].value = value;
            return false;   //     key   false
        }
        //      ，       slot
        index = (index + 1) % capacity;
    }
}

//   objMap      newCapacity
static void resizeMap(VM* vm, ObjMap* objMap, uint32_t newCapacity){
    //1.      entry  
    Entry* newEntries = ALLOCATE_ARRAY(vm, Entry, newCapacity);
    uint32_t idx = 0;
    while(idx < newCapacity){
        newEntries[idx].key = VT_TO_VALUE(VT_UNDEFINED);
        newEntries[idx].value = VT_TO_VALUE(VT_FALSE);
        idx++;
    }

    //2.      ，            
    if(objMap->capacity > 0){
        Entry* entryArr = objMap->entries;
        idx = 0;
        while(idx < objMap->capacity){
            // slot  
            if(entryArr[idx].key.type != VT_UNDEFINED){
                addEntry(newEntries, newCapacity, 
                        entryArr[idx].key, entryArr[idx].value);
            }
            idx++;
        }
    }

    //3.  entry      
    DEALLOCATE_ARRAY(vm, objMap->entries, objMap->count);
    objMap->entries = newEntries;   //       entry  
    objMap->capacity = newCapacity; //    
}

//######part3 p131######
// objMap   key   entry
static Entry* findEntry(ObjMap* objMap, Value key){
    //  objMap     NULL
    if(objMap->capacity == 0){
        return NULL;
    }

    //        
    //             slot
    uint32_t index = hashValue(key) % objMap->capacity;
    Entry* entry;
    while(true){
        entry = &objMap->entries[index];

        //  slot  key      key   
        if(valueIsEqual(entry->key, key)){
            return entry;
        }

        //key VT_UNDEFINED value VT_TRUE       ，      (             )
        //key VT_UNDEFINED value VT_FALSE       ，    (        slot       )
        if(VALUE_IS_UNDEFINED(entry->key) && VALUE_IS_FALSE(entry->value)){
            return NULL;    //    
        }

        //              
        index = (index + 1) % objMap->capacity; 
    }
}

// objMap   key value   ，objMap[key]=value
void mapSet(VM* vm, ObjMap* objMap, Value key, Value value){
    //        80%   
    if(objMap->count + 1 > objMap->capacity * MAP_LOAD_PERCENT){
        uint32_t newCapacity = objMap->capacity * CAPACITY_GROW_FACTOR;
        if(newCapacity < MIN_CAPACITY){
            newCapacity = MIN_CAPACITY;
        }
        resizeMap(vm, objMap, newCapacity); //  
    }

    //      key  objMap->count 1
    if(addEntry(objMap->entries, objMap->capacity, key, value)){
        objMap->count++;
    }
}

// map   key   value map[key]
Value mapGet(ObjMap* objMap, Value key){
    Entry* entry = findEntry(objMap, key);
    if(entry == NULL){
        return VT_TO_VALUE(VT_UNDEFINED);
    }
    return entry->value;
}

//######part4 p133######
//  objMap.entries     
void clearMap(VM* vm, ObjMap* objMap){
    DEALLOCATE_ARRAY(vm, objMap->entries, objMap->count);   //    
    objMap->entries = NULL;         //      
    objMap->capacity = objMap->count = 0;   //          
}

//  objMap  key，  map[key]
Value removeKey(VM* vm, ObjMap* objMap, Value key){
    Entry* entry = findEntry(objMap, key);

    if(entry == NULL){
        return VT_TO_VALUE(VT_NULL);
    }

    //          
    Value value = entry->value;
    entry->key = VT_TO_VALUE(VT_UNDEFINED);
    entry->value = VT_TO_VALUE(VT_TRUE);    //   ，   

    objMap->count--;
    if(objMap->count == 0){ //    map        
        clearMap(vm, objMap);
    } else if(objMap->count < objMap->capacity / (CAPACITY_GROW_FACTOR) * MAP_LOAD_PERCENT){
        // map        map  
        uint32_t newCapacity = objMap->capacity * CAPACITY_GROW_FACTOR;
        if(newCapacity < MIN_CAPACITY){
            newCapacity = MIN_CAPACITY;
        }
        resizeMap(vm, objMap, newCapacity);
    }

    return value;
}

코드 출처: 저자: 정강